aboutsummaryrefslogtreecommitdiff
path: root/range_sum_query_mutable.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'range_sum_query_mutable.cpp')
-rw-r--r--range_sum_query_mutable.cpp61
1 files changed, 0 insertions, 61 deletions
diff --git a/range_sum_query_mutable.cpp b/range_sum_query_mutable.cpp
deleted file mode 100644
index cdc0230..0000000
--- a/range_sum_query_mutable.cpp
+++ /dev/null
@@ -1,61 +0,0 @@
-#include "leetcode.h"
-
-struct segNode {
- int start, end, sum;
- segNode *left, *right;
- segNode(int a, int b)
- : start(a), end(b), sum(0), left(nullptr), right(nullptr) {}
-};
-
-class NumArray {
-public:
- segNode *root;
- NumArray(vector<int> &nums) { root = buildTree(nums, 0, nums.size() - 1); }
- void update(int index, int val) { modifyTree(index, val, root); }
- int sumRange(int left, int right) { return queryTree(left, right, root); }
-
-private:
- segNode *buildTree(vector<int> &nums, int start, int end) {
- if (start > end)
- return nullptr;
- segNode *root = new segNode(start, end);
- if (start == end) {
- root->sum = nums[start];
- return root;
- }
- int mid = start + (end - start) / 2;
- root->left = buildTree(nums, start, mid);
- root->right = buildTree(nums, mid + 1, end);
- root->sum = root->left->sum + root->right->sum;
- return root;
- }
- int modifyTree(int i, int val, segNode *root) {
- if (root == nullptr)
- return 0;
- int diff;
- if (root->start == i && root->end == i) {
- diff = val - root->sum;
- root->sum = val;
- return diff;
- }
- int mid = (root->start + root->end) / 2;
- if (i > mid)
- diff = modifyTree(i, val, root->right);
- else
- diff = modifyTree(i, val, root->left);
- root->sum = root->sum + diff;
- return diff;
- }
- int queryTree(int i, int j, segNode *root) {
- if (root == nullptr)
- return 0;
- if (root->start == i && root->end == j)
- return root->sum;
- int mid = (root->start + root->end) / 2;
- if (i > mid)
- return queryTree(i, j, root->right);
- if (j <= mid)
- return queryTree(i, j, root->left);
- return queryTree(i, mid, root->left) + queryTree(mid + 1, j, root->right);
- }
-};