# Range Sum Query - Mutable

`Segment Tree`, `Binary Indexed Tree`

Medium

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.

## Solution

#### Segment Tree

~100 lines of code; 58 ms, faster than 100.00%; 45.9 MB, less than 93.37%

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

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

class SegmentTree {
SegmentTreeNode root;

public SegmentTree (int[] nums) {
root = build(0, nums.length - 1, nums);
}

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

SegmentTreeNode root = new SegmentTreeNode(start, end, 0);

if (start == end) {
root.sum = nums[start];
} else {
int mid = start + (end - start) / 2;
root.left = build(start, mid, nums);
root.right = build(mid + 1, end, nums);
root.sum = root.left.sum + root.right.sum;
}
return root;
}

public int query (SegmentTreeNode root, int start, int end) {
if (root.start == start && root.end == end) {
return root.sum;
}

int mid = root.start + (root.end - root.start) / 2;
int leftSum = 0, rightSum = 0;

if (start <= mid) {
if (mid < end) {
leftSum = query(root.left, start, mid);
} else {
leftSum = query(root.left, start, end);
}
}

if (mid < end) {
if (start <= mid) {
rightSum = query(root.right, mid + 1, end);
} else {
rightSum = query(root.right, start, end);
}
}

return leftSum + rightSum;
}

public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == index && root.end == index) {
root.sum = value;
return;
}

int mid = root.start + (root.end - root.start) / 2;
if (index <= mid && root.start <= mid) {
modify(root.left, index, value);
} else if (index > mid && root.end >= mid) {
modify(root.right, index, value);
}

root.sum = root.left.sum + root.right.sum;
}
}

class NumArray {

SegmentTree st;

public NumArray(int[] nums) {
this.st = new SegmentTree(nums);
}

public void update(int i, int val) {
st.modify(st.root, i, val);
}

public int sumRange(int i, int j) {
return st.query(st.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);
*/
``````

#### Binary Indexed Tree

``````/**
* This reference program is provided by @jiuzhang.com
*/

public class NumArray {
private int[] arr, bit;

/**
* @return: nothing
*/
public NumArray(int[] nums) {
arr = new int[nums.length];
bit = new int[nums.length + 1];

for (int i = 0; i < nums.length; i++) {
update(i, nums[i]);
}
}

public void update(int index, int val) {
int delta = val - arr[index];
arr[index] = val;

for (int i = index + 1; i <= arr.length; i = i + lowbit(i)) {
bit[i] += delta;
}
}

public int getPrefixSum(int index) {
int sum = 0;
for (int i = index + 1; i > 0; i = i - lowbit(i)) {
sum += bit[i];
}
return sum;
}

private int lowbit(int x) {
return x & (-x);
}

public int sumRange(int left, int right) {
return getPrefixSum(right) - getPrefixSum(left - 1);
}
}
``````