## Algorithm

Problem Name: 307. Range Sum Query - Mutable

Given an integer array `nums`, handle multiple queries of the following types:

1. Update the value of an element in `nums`.
2. Calculate the sum of the elements of `nums` between indices `left` and `right` inclusive where `left <= right`.

Implement the `NumArray` class:

• `NumArray(int[] nums)` Initializes the object with the integer array `nums`.
• `void update(int index, int val)` Updates the value of `nums[index]` to be `val`.
• `int sumRange(int left, int right)` Returns the sum of the elements of `nums` between indices `left` and `right` inclusive (i.e. `nums[left] + nums[left + 1] + ... + nums[right]`).

Example 1:

```Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
```

Constraints:

• `1 <= nums.length <= 3 * 104`
• `-100 <= nums[i] <= 100`
• `0 <= index < nums.length`
• `-100 <= val <= 100`
• `0 <= left <= right < nums.length`
• At most `3 * 104` calls will be made to `update` and `sumRange`.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class NumArray {
public:
NumArray(vector<int> nums) {
this->nums = nums;
}

void update(int i, int val) {
nums[i] = val;
}

int sumRange(int i, int j) {
int sum = 0;
for(int a = i; a  < = j; a++) sum += nums[a];
return sum;
}

private:
vector<int> nums;
};

// Segment Tree
class NumArray {
struct SegmentTreeNode{
int start;
int end;
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int l, int r):start(l), end(r), sum(0), left(NULL), right(NULL){}
};
SegmentTreeNode* root;

SegmentTreeNode* buildTree(vector<int>& nums, int start, int end){
if(start > end) return NULL;
SegmentTreeNode* p = new SegmentTreeNode(start, end);
if(start == end){
p->sum = nums[start];
}
else{
int mid = start + (end - start) / 2;
p->left = buildTree(nums, start, mid);
p->right = buildTree(nums, mid + 1, end);
p->sum = p->left->sum + p->right->sum;
}
return p;
}

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

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

public:
NumArray(vector<int> nums) {
root = buildTree(nums, 0, nums.size() - 1);
}

void update(int i, int val) {
update(root, i, val);
}

int sumRange(int i, int j) {
return sumRange(root, i, j);
}
};

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/

class NumArray {
struct TreeNode {
int start;
int end;
int sum;
TreeNode* left;
TreeNode* right;
TreeNode(int x, int y):start(x), end(y), sum(0), left(NULL), right(NULL) {}
};
public:
NumArray(vector<int> nums) {
root = buildTree(nums, 0, nums.size() - 1);
}

void update(int i, int val) {
dfs(root, i, val);
}

int sumRange(int i, int j) {
return i == 0 ? getSum(root, j) : getSum(root, j) - getSum(root, i - 1);
}

int getSum(TreeNode* root, int idx) {
if (root->end == idx) {
return root->sum;
}
int mid = root->start + (root->end - root->start)/2;
if (idx <= mid> {
return getSum(root->left, idx);
} else {
return root->left->sum + getSum(root->right, idx);
}
}

void dfs(TreeNode* root, int i, int val) {
if (root->start == i && root->end == i) {
root->sum = val;
return;
}

int mid = root->start + (root->end - root->start)/2;

if (i  < = mid) {
dfs(root->left, i, val);
} else {
dfs(root->right, i, val);
}
root->sum = root->left->sum + root->right->sum;
}

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

private:
TreeNode* root;
};
``````
Copy The Code &

Input

cmd
["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output

cmd
[null, 9, null, 8]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class NumArray {

private BIT bit;
private int[] nums;

public NumArray(int[] nums) {
this.bit = new BIT(nums.length);
this.nums = nums;
for (int i = 0; i  <  nums.length; i++) {
this.bit.update(i + 1, nums[i]);
}
}

public void update(int index, int val) {
int delta = val - nums[index];
this.bit.update(index + 1, delta);
this.nums[index] = val;
}

public int sumRange(int left, int right) {
return this.bit.query(right + 1) - this.bit.query(left);
}

private static class BIT {

private int[] sum;

public BIT(int n) {
this.sum = new int[n + 1];
}

private void update(int idx, int delta) {
while (idx  <  sum.length) {
sum[idx] += delta;
idx += (idx & -idx);
}
}

private int query(int idx) {
int result = 0;
while (idx > 0) {
result += sum[idx];
idx -= (idx & -idx);
}
return result;
}
}
}
``````
Copy The Code &

Input

cmd
["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output

cmd
[null, 9, null, 8]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const NumArray = function(nums) {
this.arr = nums
};

NumArray.prototype.update = function(i, val) {
this.arr[i] = val
};

NumArray.prototype.sumRange = function(i, j) {
let sum = 0;
for (let k = i; k  < = j; k++) {
sum += this.arr[k];
}
return sum;
};
``````
Copy The Code &

Input

cmd
["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output

cmd
[null, 9, null, 8]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class NumArray:
def __init__(self, nums):
if nums:
self.n = len(nums)
self.tree = [0] * (2 * (2 ** int(math.ceil(math.log(self.n, 2)))) - 1)
def dfs(node, s, e):
if s == e: self.tree[node] = nums[s]
else:
m = (s + e) // 2
dfs(2 * node + 1, s, m)
dfs(2 * node + 2, m + 1, e)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
dfs(0, 0, self.n - 1)
def update(self, i, val):
def dfs(node, s, e, idx, val):
if s == e: self.tree[node] = val
else:
m = (s + e) // 2
if s <= idx <= m: dfs(2 * node + 1, s, m, idx, val)
else: dfs(2 * node + 2, m + 1, e, idx, val)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
dfs(0, 0, self.n - 1, i, val)
def sumRange(self, i, j):
def dfs(node, s, e, l, r):
if r < s or l > e: return 0
if l <= s and e <= r: return self.tree[node]
m = (s + e) // 2
return dfs(2 * node + 1, s, m, l, r) + dfs(2 * node + 2, m + 1, e, l, r)
return dfs(0, 0, self.n - 1, i, j)
``````
Copy The Code &

Input

cmd
["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output

cmd
[null, 9, null, 8]