是一种非常容易编写的数据结构。
单次修改查询$O(logn)$,下标 1..n

区间查询,单点更新

B[i]表示A[1..i]的前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
memset(B,0,sizeof B);

int lowbit(int x){
return x&(-x);
}

void add(int x,int d){
for(int i=x;i<=n;i+=lowbit(i)){
B[i]+=d;
}
}

int query(int x){ //返回前缀和
int res=0;
for(int i=x;i>0;i-=lowbit(i)){
res+=B[i];
}
return res;
}

add(x,d);
ans=query(r)-query(l-1);

单点查询,区间更新

B[i]表示A[1..i]的加法次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void add(int x,int d){			
for(int i=x;i>0;i-=lowbit(i)){
B[i]+=d;
}
}

int query(int x){ //x加法次数
int res=0;
for(int i=x;i<=n;i+=lowbit(i)){
res+=B[i];
}
return res;
}

add(l-1,-c);add(r,c); // 区间[1..r]加c,[1..l-1]减c
ans=query(x); // 单点查询

区间查询,区间更新

略复杂,B[i]表示A[1..i]加法次数,C[i]表示A[1..i]的和(C[i]=i*B[i])

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
29
30
31
32
33
34
35
void add_b(int x,int d){
for(int i=x;i>0;i-=lowbit(i)) B[i]+=c
}

void add_c(int x,int d){
for(int i=x;i<=n;i+=lowbit(i)) C[i]+=x*d;
}

int query_b(int x){
int res=0;
for(int i=x;i<=n;i+=lowbit(i)) res+=B[i];
return res;
}

int query_c(int x){
int res=0;
for(int i=x;i>0;i-=lowbit(i)) res+=C[i];
return res;
}

void add(int l,int r,int d){
add_b(r,d); add_c(r,d);
if(l>1){
add_b(l-1,-d);
add_c(l-1,-d);
}
}

int query(int x){
if(x) return query_b(x)*x+query_c(x-1);
else return 0;
}

add(l,r,c);
ans=query(r)-query(l-1);

二维树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//单点修改,区间查询,另一个同理
void add(int x,int y,int d){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
B[i][j]+=d;
}

int query(int x,int y){
int res=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
res+=B[i][j];
return res;
}

add(x,y,d);
ans=query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);

应用

求逆序对

单点查询,区间更新

1
2
3
4
5
6
for(int i=1;i<n;++i) scanf(“%d”,a+i)
int inv=0;
for(int i=n;i>=1;--i){
inv+=query(a[i]);
add(a[i],1);
}
  • 若a[i]范围比较大,则需要离散化