• ㊗️
• 大家
• offer
• 多多！

## Problem

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

Update the value of an element in nums. 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


## Code

binary index tree 解法 解决问题 - 求前 N 项和 （The sum of the first n terms）

1. 求前 n 项和：O(N)
2. 更新数组：O(1)
3. 再求和：O(N) 复杂度：如果上边的操作进行 m 次的话，O(M * N)

1. 求前 n 项和：O(log(N))
2. 更新数组：O(log(N))
3. 再求和：O(log(N)) 复杂度，操作 m 次：O(M * log(N))

i & -i 求最右边的 1 在哪儿，并返回那个数字 例如 1100 -> 100

class NumArray {
// index tree initialization
class IndexTree{
int[] sums;
public IndexTree(int n){
sums = new int[n + 1];
}

public void update(int i, int delta){
while(i < sums.length){
sums[i] += delta;
// 每次给末尾的1再加1
i += i & -i;
}
}

public int query(int i){
int sum = 0;
while(i > 0){
sum += sums[i];
// 每次去掉最后一位的1, 找到对应的sums
i -= i & -i;
}
return sum;
}
}

// code
IndexTree tree;
int[] nums_;
public NumArray(int[] nums) {
nums_ = nums;
tree = new IndexTree(nums.length);

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

public void update(int i, int val) {
tree.update(i + 1, val - nums_[i]);
nums_[i] = val;
}

public int sumRange(int i, int j) {
return tree.query(j + 1) - tree.query(i);
}
}

/**
* 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);
*/