树状数组学习

树状数组简介

树状数组，用于维护和查询前缀和，与线段树功能类似。树状数组代码短，常数和空间小，时间复杂度小，所以这也是一个十分优秀的算法。

设$a[i]$为原数组上的点，$s[i]$为树状数组中各点，则

$s[1]=a[1]$
$s[2]=a[1]+a[2]$
$s[3]=a[3]$
$s[4]=a[1]+a[2]+a[3]+a[4]$
$s[5]=a[5]$
$s[6]=a[5]+a[6]$

可以发现，$s[x]=\sum _{i=x-2^k+1}^{x}a[i]$，其中$k$表示$x$的二进制中末尾连续的0的个数。

树状数组的操作

lowbit(i)

根据上文，$s[x]=\sum _{i=x-2^k+1}^{x}a[i]$，其中$k$表示$x$的二进制中末尾连续的0的个数。那应该如何求$2^k$呢？

我们可以用$lowbit$来求，$lowbit(n)$的值为$n$的二进制中最后一个1的权值，也就是$2^k$。而$lowbit(n)$可以由n&(-n)得出。

为什么呢？我们可以得出$n-1$是将$n$的二进制从末尾到最后一个1全部取反，然后将$n-1$的各位取反得 ~n+1。n与 ~n+1 在$n$末尾最后一个1之前都为0，在末尾最后一个1之前都不相等。所以n&(~n+1)即为n的二进制中最后一个1的权值。
因为在补码中，~ n=-n-1。所以n&(~n+1)=n&(-n)

code

int lowbit(int n){
	return n&(-n);
}
1
2
3

单点修改

将$a[i]$增加$v$。由于$s[x]=\sum _{i=x-2^k+1}^{x}a[i]$，所以$s[i],s[i+2^k],\dots$都要修改。

code

void add(int i,int v){
	while(i<=n){
		s[i]+=v;i+=lowbit(i);
	}
}
1
2
3
4
5

时间复杂度为$O(\log n)$

区间查询

求前$i$个数的前缀和，可以画图理解。

code

int sum(int i){
	int re=0;
	while(i){
		re+=s[i];i-=lowbit(i);
	}
	return re;
}
1
2
3
4
5
6
7

若要求区间$[l,r]$的和，则答案为$sum(r)-sum(l-1)$。

时间复杂度为$O(\log n)$

例题

洛谷 P3374 【模板】树状数组

单点修改+区间查询

code

#include
using namespace std;
int n,m,tp,x,y,tr[500005];
int lb(int i){
	return i&(-i);
}
void add(int i,int v){
	while(i<=n){
		tr[i]+=v;i+=lb(i);
	}
}
int find(int i){
	int re=0;
	while(i){
		re+=tr[i];i-=lb(i);
	}
	return re;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		add(i,x);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&tp,&x,&y);
		if(tp==1) add(x,y);
		else printf("%d\n",find(y)-find(x-1));
	}
	return 0;
}
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

洛谷 P3372

区间修改+区间查询

我们可以用差分的思想，设$d_i=a_i-a_{i-1}$，则$a_i=\sum _{j=1}^i{a}_j$

对于区间修改，设将区间$[l,r]$都增加$v$，则$d_l+=v,d_{r+1}-=v$即可，这样就变成了单点修改。

对于区间查询，$su{m}_i=\sum _{j=1}^i{a}_j=\sum _{j=1}^i\sum _{k=1}^j{d}_k=\sum _{j=1}^i{d}_j\ast (i-j+1)=(i+1)\sum _{j=1}^i{d}_j-\sum _{j=1}^i(j\ast d_j)$

也就是说，我们只要用两个树状数组维护$d_i$和$i\ast d_i$的前缀和，就能求出$a_i$的和。

code

#include
using namespace std;
int n,m,tp,x,y,a[100005];
long long k,tr[100005][2];
int lb(int i){
	return i&(-i);
}
void add(int i,long long v,int z){
	while(i<=n){
		tr[i][z]+=v;i+=lb(i);
	}
}
long long find(int i,int z){
	long long re=0;
	while(i){
		re+=tr[i][z];i-=lb(i);
	}
	return re;
}
long long sum(int i){
	return (i+1)*find(i,0)-find(i,1);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		x=a[i]-a[i-1];
		add(i,x,0);
		add(i,x*i,1);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&tp,&x,&y);
		if(tp==1){
			scanf("%lld",&k);
			add(x,k,0);
			add(y+1,-k,0);
			add(x,k*x,1);
			add(y+1,-k*(y+1),1);
		}
		else printf("%lld\n",sum(y)-sum(x-1));
	}
	return 0;
}
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
36
37
38
39
40
41
42
43
44