[LeetCode] Range Sum Query - Mutable

 1 struct SegmentTreeNode {
 2     int s, e, sum;
 3     SegmentTreeNode* left;
 4     SegmentTreeNode* right;
 5     SegmentTreeNode(int _s, int _e) : s(_s), e(_e), sum(0), left(NULL), right(NULL) {}
 6 };
 7 
 8 class SegmentTree {
 9 public:
10     SegmentTree(vector<int>& nums) {
11         int n = nums.size();
12         root = buildST(nums, 0, n - 1);
13     }
14 
15     void update(int i, int val) {
16         update(root, i, val);
17     }
18 
19     int sumRange(int i, int j) {
20         return sumRange(root, i, j);
21     }
22 private:
23     SegmentTreeNode* root;
24     SegmentTreeNode* buildST(vector<int>& nums, int s, int e) {
25         if (s > e) return NULL;
26         else {
27             SegmentTreeNode* res = new SegmentTreeNode(s, e);
28             if (s == e) res->sum = nums[s];
29             else {
30                 int m = s + (e - s) / 2;
31                 res->left = buildST(nums, s, m);
32                 res->right = buildST(nums, m + 1, e);
33                 res->sum = res->left->sum + res->right->sum;
34             }
35             return res;
36         }
37     }
38     void update(SegmentTreeNode* root, int i, int val) {
39         if (root->s == root->e) root->sum = val;
40         else {
41             int m = root->s + (root->e - root->s) / 2;
42             if (i <= m) update(root->left, i, val);
43             else update(root->right, i, val);
44             root->sum = root->left->sum + root->right->sum;
45         }
46     }
47     int sumRange(SegmentTreeNode* root, int s, int e) {
48         if (root->s == s && root->e == e) return root->sum;
49         else {
50             int m = root->s + (root->e - root->s) / 2;
51             if (e <= m) return sumRange(root->left, s, e);
52             else if (s >= m + 1) return sumRange(root->right, s, e);
53             else return sumRange(root->left, s, m) + sumRange(root->right, m + 1, e);
54         }
55     }
56 };
57 
58 class NumArray {
59 public:
60     NumArray(vector<int>& nums) {
61         st = new SegmentTree(nums);
62     }
63 
64     void update(int i, int val) {
65         st->update(i, val);
66     }
67 
68     int sumRange(int i, int j) {
69         return st->sumRange(i, j);
70     }
71 private:
72     SegmentTree* st;
73 };
74 
75 
76 // Your NumArray object will be instantiated and called as such:
77 // NumArray numArray(nums);
78 // numArray.sumRange(0, 1);
79 // numArray.update(1, 10);
80 // numArray.sumRange(1, 2);