/**
* 这题可以用segment tree或binary index tree(bit)，两者时间复杂度都是lgn，不过segment tree因为用到树，
* 而bit用的是数组，所以bit更省空间。
*
* 关于BIT，可以参考http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
* 关于Segment Tree，可以参考 https://discuss.leetcode.com/topic/29918/17-ms-java-solution-with-segment-tree
*
* https://leetcode.com/articles/range-sum-query-mutable/
*/
public class NumArrayII {
private int[] bit;
private int[] nums;
public NumArrayII(int[] nums) {
this.nums = nums;
bit = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
init(i, nums[i]);
}
}
public void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
init(i, diff);
}
private void init(int i, int val) {
i++;
while (i < bit.length) {
bit[i] += val;
i += i & (-i);
}
}
private int getSum(int i) {
i++;
int sum = 0;
while (i > 0) {
sum += bit[i];
i -= i & (-i);
}
return sum;
}
public int sumRange(int i, int j) {
return getSum(j) - getSum(i - 1);
}
/**
private SegmentTreeNode mRoot;
public NumArrayII(int[] nums) {
mRoot = buildTree(nums, 0, nums.length - 1);
}
private SegmentTreeNode buildTree(int[] nums, int start, int end) {
if (start > end) {
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start, end);
if (start == end) {
root.sum = nums[start];
return root;
}
int mid = start + ((end - start) >>> 1);
root.left = buildTree(nums, start, mid);
root.right = buildTree(nums, mid + 1, end);
root.sum = root.left.sum + root.right.sum;
return root;
}
public void update(int i, int val) {
update(mRoot, i, val);
}
private void update(SegmentTreeNode root, int i, int val) {
int start = root.start, end = root.end;
if (start == end) {
root.sum = val;
return;
}
int mid = start + ((end - start) >>> 1);
if (i <= mid) {
update(root.left, i, val);
} else {
update(root.right, i, val);
}
root.sum = root.left.sum + root.right.sum;
}
public int sumRange(int i, int j) {
return sumRange(mRoot, i, j);
}
public int sumRange(SegmentTreeNode root, int i, int j) {
int start = root.start, end = root.end;
if (start == i && end == j) {
return root.sum;
}
int mid = start + ((end - start) >>> 1);
if (j <= mid) {
return sumRange(root.left, i, j);
} else if (i > mid) {
return sumRange(root.right, i, j);
} else {
return sumRange(root.left, i, mid) + sumRange(root.right, mid + 1, 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);