# [leetcode]Range Sum Query – Mutable

Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

```Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
```

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

Segment tree.

```class SegTreeNode{
public:
SegTreeNode * left, * right;
int sum;
int leftidx, rightidx;
SegTreeNode():sum(0), leftidx(0), rightidx(0), left(nullptr), right(nullptr){}
};

class NumArray {
public:
SegTreeNode * root;
NumArray(vector<int> &nums) {
if(nums.size() == 0) return ;
root = buildSegmentTree(nums, 0, nums.size() - 1);
}
SegTreeNode* buildSegmentTree(vector<int>& nums, int start, int end){
SegTreeNode * node = new SegTreeNode();
node->leftidx = start;
node->rightidx = end;
int mid = (start + end) / 2;
if(start == end){
node->sum = nums[start];
}else{
node->left = buildSegmentTree(nums, start, mid);
node->right = buildSegmentTree(nums, mid + 1, end);
node->sum = node->left->sum + node->right->sum;
}
return node;
}
void update(int i, int val) {
_update(root, i, val);
}
void _update(SegTreeNode* node, int i, int val){
if(node->leftidx == node->rightidx && node->leftidx == i){
node->sum = val;
}else{
int mid = (node->leftidx + node->rightidx) / 2;
if(i <= mid){
_update(node->left, i, val);
}else{
_update(node->right, i, val);
}
node->sum = node->left->sum + node->right->sum;
}
}

int sumRange(int i, int j) {
return _sumRange(root, i, j);
}
int _sumRange(SegTreeNode* node, int i, int j){
if(node->leftidx > j || node->rightidx < i){
return 0;
}
else if(node->leftidx >= i && node->rightidx <= j){
return node->sum;
}else{
return _sumRange(node->left, i, j) + _sumRange(node->right, i, j);
}
}
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);```

This site uses Akismet to reduce spam. Learn how your comment data is processed.