树状数组学习笔记

发布于 2019-09-21  487 次阅读


先引用一下定义

树状数组(Binary Indexed Tree(B.I.T))是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)

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

要明确的一点是树状数组只是线段树的阉割版,我们使用树状数组很大的一个原因是树状数组十分好写,而且它非常好维护。但是它只能处理可以用前缀和或差分来解决的题目,像是求(l,r)之间的最大值,树状数组就失去了用勇武之地。

上个经典的图

img

树状数组是基于前缀和和差分的,他的每个节点如图所示。

  • 图中有一棵满二叉树,满二叉树的每一个结点对应A[]中的一些元素。

  • 设树状数组为C[]

观察一下每个C代表了哪些A

img

如果我们要求A[6]怎么办呢?很简单,用C[6]-C[5]就可以了,这就是我们所说的前缀和。

那我们怎么知道这个数组里存的是什么呢?接下来就是树状数组的一个关键操作——lowbit。因为C数组里存的东西和它的二进制有着不可分割的关系,C数组的下标 i 如果以 x 个 0 结尾,它就存了img 到 $latex A[i] $的和的值,而而lowbet可以快速的求出$latex 2^x $的值。

lowbit求法 lowbit=i & -i

树状数组所支持的操作:

在信息可减的情况下,可以各种差分:

  • 单点加,区间查询
  • 区间加,单点查询
  • 区间加,区间查询(抱歉我不会)

单点加,区间查询

查询区间为[l,r]的时候,差分为前r个数的和减去前l-1个数的和即可

区间加,单点查询

不妨换个思路,把区间[l,r]加x差分为前缀[1,r]加x,前缀[1,l-1]减x,查询单点的时候只需要查询包含这个点的所有前缀修改即可

例一:

题目地址

上代码

  • lowbit

#define lb() i&-i
  • 查找单点值

int find(int x)
{
int sum=0;
for(int i=x;i;i-=lb())
  sum+=tree[i];
return sum;
}
  • 单点修改+建树

void add(int x,int k)
{
for(int i=x;i<=n;i+=lb())
  tree[i]+=k;
}

完整代码

#include<iostream>

using namespace std;

int n,m,tree[500001];

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

void add(int x,int k)
{
	for(int i=x;i<=n;i+=lb(i))
		tree[i]+=k;
}

int find(int x)
{
	int sum=0;
	for(int i=x;i;i-=lb(i))
		sum+=tree[i];
	return sum;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		add(i,a);
	}
	for(int i=1;i<=m;i++)
	{
		int t,x,y;
		cin>>t>>x>>y;
		if(t==1)
		add(x,y);
		else
			cout<<find(y)-find(x-1)<<endl;
	}
	return 0;
}

例二

题目地址

代码如下:

#include<iostream>
#define N 500010

using namespace std;

int n,m,tree[N],a[N];

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

void add(int x,int k)
{
	for(int i=x;i<=n;i+=lb(i))
		tree[i]+=k;
}

int find(int x)
{
	int sum=0;
	for(int i=x;i;i-=lb(i))
		sum+=tree[i];
	return sum;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int t,x,y,k;
		cin>>t;
		if (t==1)
		{
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else
		{
			cin>>x;
			cout<<a[x]+find(x)<<endl;
		}
	}
	return 0;
}

最美好的事情就是和OI一起成长呢。