LeetCode 307. 区域和检索 - 数组可修改 (树桩数组
原题链接
中等
作者:
JustDoIt11
,
2024-03-18 08:49:24
,
所有人可见
,
阅读 9
class NumArray {
private int[] tri;
private int[] nums;
public static int lowbit(int x) { return (x & (-x)); }
public NumArray(int[] nums) {
tri = new int[nums.length + 1];
this.nums = new int[nums.length];
for (int i = 0; i < nums.length; i ++ ) {
update(i, nums[i]);
this.nums[i] = nums[i];
}
// System.out.println("[构造函数] tri = " + Arrays.toString(tri));
}
public void update(int index, int val) {
// 注意, 本题是修改为对应val, 而不是修改多少val, 所以把问题转化为学过的知识
// 得到需要调整的al
val = val - nums[index];
// nums也要修改
nums[index] += val;
index ++ ;
for (int i = index; i < tri.length; i += lowbit(i)) {
tri[i] += val;
}
// System.out.println("[修改后] tri = " + Arrays.toString(tri));
}
public int query(int index) {
index ++ ;
int ret = 0;
for (int i = index; i > 0; i -= lowbit(i)) {
ret += tri[i];
}
return ret;
}
public int sumRange(int left, int right) {
return query(right) - query(left - 1);
}
}
/**
* 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);
*/