: 树状数组
BIT
首先来看一道例题:(Link)
已知一个数列,你需要进行下面两种操作:
1.将某一个数加上x
2.求出某区间每一个数的和
首先按照暴力思路解决,我们用输入,更改的时候是,求区间和的时候是,然后就会导致程序运行时间非常长,这里我们引用树状数组( ),简称,是一种非常高效的高级数据结构( ),它的查询和修改的时间复杂度都是。
.基本思想
我们知道,每一个整数都可以分成若干个的幂次之和,就好像可以分解为++一样,我们希望每一次求前缀和也能够分解为一系列恰当的、不相交的“子集”,分解成了三块,那么我们希望的前缀和也能够分解为个子集。根据这种思想我们可以汇出这样的一个表格:
这里的“内容”指的就是所包含的子集,就比如3只包含3本身,而4包含1~4所有,那么我们为什么要这样划分呢?
在这里我们用来表示的所有子集的 的和,然后我们来进行检验,这种求和方案是不是满足我们一开始的初衷,比如,求前缀和,我们就只需要计算,正好是三个子集,也就是++=,所以我们知道这种方法看似是成立的。
下面,我们用另一种图来表示“子集和”的含义。
![picture1](http://www.pic68.com/uploads/2018/08/1.PNG)
我们按照上面的表格在这里建立了一个方块图,每一个长方形代表的是每个子集对应的部分和,而被框起来的部分就是子集下表对应的值,没有被框起来的部分代表的是还需要维护的其他的下标对应的值。我们首先来看节点,它的维护路径是这样的:
![picture2](http://www.pic68.com/uploads/2018/08/2.PNG)
然后对于的维护是这样的路径:
![picture3](http://www.pic68.com/uploads/2018/08/3.PNG)
由此,我们还可以构造出一种更一般的形式:查询树。
![picture4](http://www.pic68.com/uploads/2018/08/4.PNG)
对于每一个查询,我们在查询树中找到对应标号的节点,然后顺着父边一直向根节点方向走一直到,依次累加路径上每一个标号所对应的子集和,到根节点的时候,我们就得到了。比如,我们沿路就要加上,,的值。而节点的深度就是对应数字的二进制表示当中的个数。比如的二进制拆分是,含有个“”,那么对应的深度就是。另外还有一个十分重要的规律,(除了节点之外)
每一个节点的儿子个数都是这个点的二进制表示中末尾的个数。
比如的二进制拆分,末尾有个,那么它的儿子个数就有,一共两个。而树状数组的名字 也就是这么来的。
.实现
现在我们就是要考虑怎么实现这种子集划分。我们再来看一个表格。
那么我们可以知道,所含元素的个数就是的二进制拆分的最低位的1所在的位置的十进制数。 那么这个位置又该怎么算呢?
下面要讲的是树状数组中最重要的一个技术:低位技术,即,对于一个下标,我们知道是用的有符号的整形数进行存储的,其次,我们还知道计算机存储整形数是用补码的形式,正数的补码就是本身的二进制码,而其相反数则是用的其反码+来表示。假设的二进制数为,其中为若干个,那么和中间的就是最低位的,那么-就是~ (~表示对取非,~),那么两者之后就得到了,那么我们不难得知的是怎么算出来的。
int lowbit(int now){
return now&(-now);
}
然后我们还要知道一个定律:在我们所建的树状数组中,儿子加上就是其父亲的编号,这个也不难想。那么对于前缀和的查询我们就有头绪了,对于下标为的前缀和,我们需要加的项的个数是的二进制拆分中所包含的1的个数,也就是在查询树的深度,这个个数最多是,所以查询复杂度是的。
int query(int now){//询问now的前缀和
int ans=0;
while(now){
ans+=sum[now];
now-=l
}
return ans;
}
然后对于单点修改就很简单了,我们可以类比线段树,由于我们的节点存储的是一种和的形式,所以当任意一个子节点发生改变的时候,父节点也要发生改变,所以我们的单点修改也是一个while()形式。
void add(int now,int k){//将下标为now的数加上k
while(now<=n){
sum[now]+=k;
now+=lowbit(now);
}
}
至此,是树状数组的基本部分,下面是开头的题的代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500010
using namespace std;
int sum[MAXN],n,m;
int lowbit(int now){
return now & (-now);
}
void add(int now,int k){
while(now<=n){
sum[now]+=k;
now+=lowbit(now);
}
}
int query(int now){
int ans=0;
while(now!=0){
ans+=sum[now];
now-=lowbit(now);
} return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x; scanf("%d",&x);
add(i,x);
//我们可以把输入也理解为一种单点修改
}
for(int i=1;i<=m;i++){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt==1) add(x,y);
else printf("%d\n",query(y)-query(x-1));
} return 0;
}
然后是第二道例题,涵盖了树状数组的另外两种功能:区间修改和单点询问。
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数数加上x
2.求出某一个数的和、
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x 含义:输出第x个数的值
输出格式:
输出包含若干行整数,即为所有操作2的结果。
在这里我们介绍一种利用查分数组解决问题的方法,首先我们要知道什么叫做差分数组,简而言之,就是原序列中相邻元素之间两两相减,得到的一串数组。举个例子,假设={},那么的差分数组={}。也就是说=-,从而可以得到=。
接下来,假设我们需要将~之间的所有数加上,那么原序列变为:={},b[9]={}。
,那么我们现在就可以发现规律了,数组对~加上之后,数组只是在位置加上,在+位置减去,即; 那么在修改的时候我们就由一串区间修改变为了两个单点修改。而单点查询就变为了区间查询,那么这个区间查询我们就可以在此利用树状数组维护了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500010
using namespace std;
int a[MAXN],sum[MAXN],n,m;
int lowbit(int now){
return now&(-now);
}
void add(int now,int k){
while(now<=n){
sum[now]+=k;
now+=lowbit(now);
}
}
int query(int now){
int ans=0;
while(now!=0){
ans+=sum[now];
now-=lowbit(now);
} return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
int b=a[i]-a[i-1];//差分
add(i,b);
}
for(int i=1;i<=m;i++){
int opt; cin>>opt;
if(opt==1){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
add(x,k); add(y+1,-k);//两个单点修改
} else{
int x; scanf("%d",&x);
printf("%d\n",query(x));//前缀和查询
}
} return 0;
}