1. 基本用法
- 单点修改,区间查询
- 区间修改,单点查询
- 区间修改,区间查询
2.模板代码
- 结构体版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
class :vector<int> { public: explicit (int k=0) { assign(k+1,0); } int lowbit(int k) { return k&-k; } int sum(int k) { return k>0?sum(k-lowbit(k))+(*this)[k]:0; } int last() { return size()-1; } void add(int k,int w) { if(k>last())return; (*this)[k]+=w; add(k+lowbit(k),w); } };
|
- 函数版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
int n,m,i,num[100001],t[200001],l,r; int lowbit(int x) { return x&(-x); } void change(int x,int p) { while(x<=n) { t[x]+=p; x+=lowbit(x); } return; } int sum(int k) { int ans=0; while(k>0) { ans+=t[k]; k-=lowbit(k); } return ans; } int ask(int l,int r) { return sum(r)-sum(l-1); }
|
- 注意事项
树状数组下标从1开始,不要忘了初始化数组,原数组和树状数组的关系要分清楚;
3. 扩展
- 二维树状数组
- 求逆序对
- 树形树状数组
- 求指定长度单调子序列
- 树状数组求区间最值
4. 参考
- https://blog.csdn.net/qq_39553725/article/details/76696168
- https://blog.csdn.net/u010598215/article/details/48206959
- https://baike.baidu.com/item/树状数组
近期评论