BIT(树状数组)

树状数组

今天听老刘讲了下树状数组,再结合自己的理解。补一篇学习笔记。

树状数组的用处:

1.单点修改+区间查询(本质)

2.区间修改+单点查询

3.区间修改+区间查询

当我们需要频繁的修改查询时,借用树状数组可以大大降低复杂度。(o(logn))

而且树状数组较线段树的好处就是:代码简洁。(能让你深切感受到二进制之美)

下面就来介绍一下如何构造使用树状数组。

预备知识(lowbit)

给你一个数,其转化为二进制从右往左到第1个1的值就是这个数的lowbit值。

eg:12(1100)的lowbit值即为4(100)

那么,lowbit(x)要怎么去计算呢?

首先我们把x取反+1,这样得到的(~x+1)与之前的x相比只有第一个1(从右往左)的后面的数相同了。

所以lowbit(x)=x&(~x+1)

由于计算机存储的采用是补码,所以~x+1=-x,那么lowbit(x)=x&-x

单点修改+区间查询

给出一个长度为n的数组,完成以下操作:

1.将第x个数加上k

2.输出区间[l,r]内每个数的和

如上图所示,原数组设为a,树状数组设为t。

t[1] (0001)=a[1] (0001);

t[2] (0010)=a[1] (0001)+a[2] (0010);

t[3] (0011)=a[3] (0011);

t[4] (0100)=a[1] (0001)+a[2] (0010)+a[3] (0011)+a[4] (0100);

以此类推。

以这样的方式来存储数组的数据结构其实就是树状数组了。

可以发现,t[x]管理的a[x]的数量取决于lowbit(x)

而现在我们要求sum(4),其实就是t[4]的值。

sum(6)(0110)=t[6](0110)+t[4] (0010)

sum (7)(0111)= t[7] (0111) + t[6](0110)+t[4] (0010)

又可以发现,我们要求sum(x),只要从x开始不断减去lowbit(x),就能还原整个管理区域。这样就保证了

sum(x)的复杂度最多是logx。也是为什么使用树状数组的原因。

那么当我们要进行单点更新时,不光要将t[x]+k,还要将管理x的t都加上k,也就是sum的逆向,不断加上lowbit(x)就行了。

贴下板子(非常的简洁哟):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn=2e6+10;
//[1,n]
int bit[maxn+1],n;
int sum(int i)
{
	int s=0;
	while(i>0)
	{
		s+=bit[i];
		i-=i&-i;
	}
	return s;
}
void add(int i,int x)
{
	while(i<=n)
	{
		bit[i]+=x;
		i+=i&-i;
	}
}

tip:树状数组下标不能从0开始,会陷入死循环)

区间修改+单点查询

在这里要引入差分数组d。(即a[]每个元素的增量)

eg:a[1]=1,a[2]=2,a[3]=0

d[1]=a[1]=1, d[2]=a[2]-a[1]=1 ,d[3]=a[3]-a[2]=-2;

那么当我们要做区间[l,r]修改+k时,由于这个区间内的差量是不发生变化的,变化的仅有边界的地方。

因此只要对b[l]+k,b[r+1]-k就能维护区间了。

当我们要查询单点时,可以发现a[x]= $\sum_{i=1}^x {d[i]} \quad$

这样就把单点查询变回上面的区间查询了。

因此我们只需要用树状数组来维护d这个差分数组就行了。

代码就不贴了,因为和上面的那一份是一模一样的。只要刚开始把bit[n]初始化为差分数组即可。

区间修改:对[l,r]的区间+k add(l,k) ,add(r+1,-k);

单点查询(x):a[x]=sum(x);

区间修改+区间查询

区间修改的方式还是可以参照上面差分数组的方法。

区间修改:对[l,r]的区间+k add(l,k) ,add(r+1,-k);

着重来讲一下如何进行区间查询

上面讲了单点查询的方法。

那么不难想到位置p的前缀和:$\sum_{i=1}^p {a[i]} \quad=\sum_{i=1}^p {\sum_{j=1}^i {d[j]} \quad} \quad$

在等式右侧,d[1]被用了p次,d[2]被用了p-1次;

于是可知:

$\sum_{i=1}^p {\sum_{j=1}^i {d[j]} \quad} \quad=\sum_{i=1}^p {d[i]} \quad*(p-i+1) =(p+1)*\sum_{i=1}^p {d[i]} \quad-\sum_{i=1}^p {d[i]*i} \quad$

那么我们接下来只要用两个树状数组去维护d[i]和 d[i]*i 就好了。

c1[i]=d[i];

*c2[i]=d[i]i;

区间查询(l,r):sum(r)- sum(l-1)

贴下代码吧:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn=2e6+10;
//[1,n]
int c1[maxn+1],c2[maxn+1],n;
int sum(int p)
{	
	int s=0,i=p;
	while(i>0)
	{
		s+=(p+1)*c1[i]-c2[i];
		i-=i&-i;
	}
	return s;
}
void add(int p,int x)
{	int i=p;
	while(i<=n)
	{
		c1[i]+=x,c2[i]+=x*p;
		i+=i&-i;
	}
}