树状数组


( 蓝书上的图比较形象!

lowbit(x) 可以理解为BIT[x]所管辖范围的长度

一般就用来做带修改的前缀和。

像什么区间最值是无法做的。

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
// 数组下标必须从1开始

// 单点更新区间查询
int BIT[maxn];
inline int lowbit(int x) { return x & (-x); }
inline int getsum(int l,int r){
int ret = 0;
for(int i=l-1;i>0;i-=lowbit(i)) ret -= BIT[i];
for(int i=r;r>0;i-=lowbit(i)) ret += BIT[i];
return ret;
}
inline void add(int x,int y,int n){
for(int i=x;i<=n;i+=lowbit(i)) BIT[i] += y;
}
//区间更新单点查询
int diff[maxn];
inline int lowbit(int x) {return x &(-x);}
inline int getval(int x){
int ret = 0;
for(int i=x;i>0;i-=lowbit(x)) ret += diff[i];
return ret;
}
inline void add(int l,int r,int val,int n){
for(int i=l;i<=n;i+=lowbit(i)) diff[i] += val;
for(int i=r+1;i<=n;i+=lowbit(i)) diff[i] -= val;
}
Thank you for your support!