Range Sum Query – Mutable
求range sum, fenwick tree.
class NumArray {
int[] nums;
int[] BIT;
public int lowbit(int x) {
return x&(-x);
}
public void set(int i, int val){
i++;
while(i <= nums.length){
BIT[i] += val;
i += lowbit(i);
}
}
public NumArray(int[] nums) {
this.nums = nums;
this.BIT = new int[nums.length + 5];
for(int i = 0; i < nums.length; i++)
set(i, nums[i]);
}
public void update(int index, int val) {
int diff = val - nums[index];
nums[index] = val;
set(index, diff);
}
public int sumRange(int left, int right) {
return sum(right) - sum(left - 1);
}
public int sum(int i){
int s = 0;
i++;
while(i > 0){
s += BIT[i];
i -= lowbit(i);
}
return s;
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(index,val);
* int param_2 = obj.sumRange(left,right);
*/