# LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), 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.

```class NumArray {
private:
struct Node {
int start, end, sum;
Node *left, *right;
Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
};
Node *root;

Node* constructTree(vector<int> &nums, int start, int end) {
Node* node = new Node(start, end);
if (start == end) {
node->sum = nums[start];
return node;
}
int mid = start + (end - start) / 2;
node->left = constructTree(nums, start, mid);
node->right = constructTree(nums, mid + 1, end);
node->sum = node->left->sum + node->right->sum;
return node;
}

int sumRange(int i, int j, Node *root) {
if (root == NULL)return 0;
if (i == root->start&&j == root->end)return root->sum;
int mid = root->start + (root->end - root->start) / 2;
if (j <= mid)return sumRange(i, j, root->left);
else if (i > mid)return sumRange(i, j, root->right);
else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
}

void update(int i, int val, Node *root) {
if (root->start == root->end && root->start == i) {
root->sum = val;
return;
}
int mid = root->start + (root->end - root->start) / 2;
if (i <= mid)update(i, val, root->left);
else update(i, val, root->right);
root->sum = root->left->sum + root->right->sum;
}

public:
NumArray(vector<int> nums) {
root = NULL;
if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
}

void update(int i, int val) {
if (root == NULL)return;
update(i, val, root);
}

int sumRange(int i, int j) {
if (root == NULL)return 0;
return sumRange(i, j, root);
}
};
```