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.
一刷
题解：BinaryIndexTree
注意，在binaryIndexTree中，0是不用的,否则0get parent会一直停在0，陷入死循环，从1开始。所以int[] dp = new int[len+1]
class NumArray {
int[] dp;
int[] nums;
int n;
public NumArray(int[] nums) {
this.nums = nums;
this.n = nums.length;
dp = new int[this.n+1];
for(int i=0; i<nums.length; i++){
init(i+1, nums[i]);
}
}
private void init(int i, int val){
while(i<=n){
dp[i] += val;
i += (i&-i);
}
}
public void update(int i, int val) {
int delta = val - nums[i];
nums[i] = val;
for(int j=i+1; j<dp.length; j+= j&(-j)){
dp[j] += delta;
}
}
public int sumRange(int i, int j) {
return getSum(j+1) - getSum(i);
}
private int getSum(int index){
int res = 0;
while(index>=1){
res += dp[index];
index -= index & (-index);
}
return res;
}
}
/**
* 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);
*/
