307.区域与检索--数组可修改
标签：vat tag ast tom ++ one http tps 描述
区域与检索--数组可修改
线段树
代码
class NumArray {
private ArrayList sumSegmentTree;
private int n;
public NumArray(int[] nums) {
n = nums.length;
sumSegmentTree = new ArrayList(2 * n + 1);
for (int i = 0; i 0; i--) {
sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));
}
}
public void update(int i, int val) {
i += n;
sumSegmentTree.set(i, val);
while (i > 1) {
i /= 2;
sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));
}
}
/** 原算法描述为range[left,right)
* range[i,j]
* @param i 左下标
* @param j 右下标
* @return 总和
*/
public int sumRange(int i, int j) {
int sum = 0;
i += n;
j += n+1;
while (i >= 1;
j >>= 1;
}
return sum;
}
}
/**
* 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);
*/
307.区域与检索--数组可修改
标签：vat tag ast tom ++ one http tps 描述
原文地址：https://www.cnblogs.com/hh09cnblogs/p/11614386.html
评论