参考文献
树状数组模板题
ref{:target=”_blank”}
ref中包含O(n)的初始化时间复杂度
C++ 代码
class NumArray {
public:
// 树状数组的应用,查询和updata都是 log(n)的
vector<int> tree_;
vector<int> nums_; // 原nums的copy
int lowbit(int n){
return n&-n;
}
// 给位置id的数字加上c
void add(int id, int c){
// 每个包含 id 的seg都需要update
for(int i=id; i<=nums_.size(); i+=lowbit(i)) tree_[i] += c;
}
int query(int id){
int sum = 0;
for(int i=id; i>0; i-=lowbit(i))sum += tree_[i];
return sum;
}
NumArray(vector<int>& nums) {
// 树状数组范围 [1,n]
tree_.resize(nums.size()+1);
nums_ = nums;
for(int i=0; i<nums.size(); ++i)add(i+1, nums[i]);
}
void update(int index, int val) {
add(index+1, val - nums_[index]); // 增量
nums_[index] = val;
}
int sumRange(int left, int right) {
return query(right+1) - query(left);
}
};
/**
* 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);
*/