树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。

四.题集

一.概念

树状数组主要是维护一段区间的修改和查询；

经过简单修改可以在log(n)的复杂度下进行范围修改，但是一般只能修改一个元素的值，处理后可以实现区间修改；

以及查询任意两位之间的所有元素之和，但是一般只能查询其中一个元素的值，处理后也可实现区间查询。

一般来说，树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。

所以比起线段树冗长的代码，树状数组真是我的心头好……

先来看这张图(百科上盗的)：

树状数组

令这棵树的结点编号为C1，C2...Cn，每个结点的值为这棵树的值的总和，那么容易发现：

C1 = A1；

C2 = A1 + A2；

C3 = A3；

C4 = A1 + A2 + A3 + A4；

C5 = A5；

C6 = A5 + A6；

C7 = A7；

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8；

...

C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15+ A16；

我们就会得到一个有趣的东西：

即，设节点编号为x，那么这个节点管辖的区间为树状数组（其中k为x二进制末尾0的个数）个元素，因为这个区间最后一个元素必然为Ax，

所以易知：

而根据计算机补码知识，易得计算树状数组的简便方法：x & (-x);

证明方法就不在此赘述了QAQ；

然后根据这个我们就能在树状数组的复杂度中搞事情了√；

二.操作

单点修改和查询，这个比较容易，就不解释了

1.计算

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

2.单点修改

void add(int x,int y)
{
	for(int i=x;i<maxn;i+=lowbit(i))
	{
		tree[i]+=y;
	}
}

3.单点查询

int getsum(int x)
{
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		sum+=tree[i];
	}
	return sum;
}

然后就是区间查询，区间修改~~（港道理，比起线段树的操作，树状数组简直是人间瑰宝）~~

【一点需要提前知道的小东西：

我们假设sigma(r，i)表示r数组的前i项和，设原数组是a[n]，差分数组c[n]，c[i]=a[i]-a[i-1]；

那么明显地a[i]=sigma(c,i)，如果想要修改a[i]到a[j](比如+v)，只需令c[i]+=v,c[j+1]-=v；】

然后，

观察式子：

a[1]+a[2]+...+a[n]

= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])

= n*c[1] + (n-1)*c[2] +... +c[n]

= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n]) (式子①)

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c1[i]，每当修改c1的时候，就同步修改一下c2，这样复杂度就不会改变；

于是，式子①=n*sigma(c,n) - sigma(c2,n)。

So：

4.区间修改

int s,t,v;
scanf("%d%d%d",&s,&t,&v);
add(c1,s,v);
add(c1,t+1,-v);
add(c2,s,s*v);
add(c2,t+1,-v*(t+1));

5.区间查询

int s,t;
scanf("%d%d",&s,&t);
ans=sum[t]-sum[s-1];
ans+=(t+1)*getsum(t,c1)-getsum(t,c2);
ans-=(s*getsum(s-1,c1)-getsum(s-1,c2));

三.二维树状数组

这也是个奇妙好玩的东西

大概就是酱紫：

问题：一个由数字构成的大矩阵，能进行两种操作

1) 对矩阵里的某个数加上一个整数（可正可负）

2) 查询某个子矩阵里所有数字的和,要求对每次查询，输出结果。

一维的树状数组很容易扩展到二维；

随便搞一搞就好了：

在二维情况下:数组a[ ][ ]的树状数组定义为：

C[x][y] = ∑ a[i][j];

其中:

x-lowbit(x) + 1 <= i <= x;

y-lowbit(y) + 1 <= j <= y.

举个栗子：

设原始二维数组为：

A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},

{a21,a22,a23,a24,a25,a26,a27,a28,a29},

{a31,a32,a33,a34,a35,a36,a37,a38,a39}，

{a41,a42,a43,a44,a45,a46,a47,a48,a49}};

记B[i]为第i行的一维树状数组：

B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...}

B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...}

B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...}

B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...}
那么，对于C[ ][ ]：

一：C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a16,...

二：C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a22+a23+a24,

C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,...

三：C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a36,...

四：C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,...

然后翻译成代码就是：

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

void add(int x,int y,int value)
{
	for(int i=x;i<=maxn;i+=lowbit(i))
	{
		for(int j=y;j<=maxn;j+=lowbit(j))
		{
			tree[i][j]+=value;
		}
	}
}

int getsum(int x,int y)
{
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		for(int j=y;j>0;j-=lowbit(j))
		{
			sum+=tree[i][j];
		}
	}
	return sum;
}

是不是贼简单？

需要注意的是，矩阵修改调用函数时要介个样子：

add(x1,y1,1);
add(x2,y2,1);
add(x2,y1,-1);
add(x1,y2,-1);

最后放个完整的模板：poj 2155 Matrix 楼教主的题，中等难度

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<deque>
#include<cmath>
#include<cctype>
#define LL long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

using namespace std;
//PE一次 

const int maxn=1000+10;

int n,m;
int tree[maxn][maxn];

int read()
{
	char c=getchar();int x=0,f=1;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}

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

void add(int x,int y,int value)
{
	for(int i=x;i<=maxn;i+=lowbit(i))
	{
		for(int j=y;j<=maxn;j+=lowbit(j))
		{
			tree[i][j]+=value;
		}
	}
}

int getsum(int x,int y)
{
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		for(int j=y;j>0;j-=lowbit(j))
		{
			sum+=tree[i][j];
		}
	}
	return sum;
}

int main()
{
	int t=read();
	while(t--)
	{
		memset(tree,0,sizeof(tree));
		char op[2];
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%s",op);
			if(op[0]=='C')
			{
				int x1=read(),y1=read();
				int x2=read(),y2=read();
				x2++,y2++;
				add(x1,y1,1);
				add(x2,y2,1);
				add(x2,y1,-1);
				add(x1,y2,-1);
			}
			else
			{
				int x=read(),y=read();
				printf("%d\n",getsum(x,y)%2);
			}
		}
		cout<<endl;//高亮 
	}

	return 0;
}

四.题集

甩个隔壁链接，今天码的树状数组题集：点击就送屠龙大宝刀

树状数组

一.概念

二.操作

三.二维树状数组

举个栗子：

四.题集

相关推荐