# Range Sum Query - Mutable

307. 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:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

``````class SegmentTreeNode {
public int start, end;
public int sum;
public SegmentTreeNode left;
public SegmentTreeNode right;

public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.sum = 0;
this.left = null;
this.right = null;
}
}

public class NumArray {
SegmentTreeNode root;

public NumArray(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

root = buildTree(nums, 0, nums.length - 1);
}

SegmentTreeNode buildTree(int[] nums, int start, int end) {
if (start > end) {
return null;
}

SegmentTreeNode node = new SegmentTreeNode(start, end);

if (start == end) {
node.sum = nums[start];
} else {
int middle = start + (end - start) / 2;

node.left = buildTree(nums, start, middle);
node.right = buildTree(nums, middle + 1, end);
node.sum = node.left.sum + node.right.sum;
}

return node;
}

void update(SegmentTreeNode node, int i, int val) {
if (node == null) {
return;
}

if (i < node.start || i > node.end) {
return;
}

if (node.start == i && node.end == i) {
node.sum = val;
return;
}

int middle = node.start + (node.end - node.start) / 2;
if (i <= middle) {
update(node.left, i, val);
} else {
update(node.right, i, val);
}
node.sum = node.left.sum + node.right.sum;
}

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

int query(SegmentTreeNode node, int start, int end) {
if (node == null) {
return 0;
}

if (start <= node.start && end >= node.end) {
return node.sum;
}

int middle = node.start + (node.end - node.start) / 2;

if (end <= middle) {
return query(node.left, start, end);
} else if (start > middle) {
return query(node.right, start, end);
} else {
return query(node.left, start, middle) + query(node.right, middle + 1, end);
}
}

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

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

Hope this helps,
Michael