树状数组
树状数组,顾名思义,树状的数组,其目的是优化区间查询和区间修改的复杂度。
看图
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,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,所以很明显:Cn = A(n – 2^k + 1) + ... + An
以9为例,C[9]=A[9]+C[8]即可;
而其中的k用了一个巧妙的方式,lowbit()
int lowbit(int x){
return x&(x^(x–1));
}
如:
x =1: 1 &-1(设位数为8)0000 0001 & 1111 1111 = 1
x = 6:6 & -6 0000 0110 &1111 1010 = 2 //补码&运算
总结一下,其实就是:
求出2^p(其中p: x 的二进制表示数中, 右向左数第一个1的位置),如6的二进制表示为110,向左数第零个为0,第一个为1,则p=1,故Lowbit(6) = 2^1 = 2。
其中最不好理解的就是数组的更新初始化(困扰快两天了,,,)当时一直不明白A[]数组如何储存的,如何转化成C[]数组的,其实根本不用储存A[]数组
用的是他的修改功能
void add(int x,int value)
{
while(x<Max)
{
c[x]+=val;
x+=lowbit;
}
}
其中value就是对应的A[]数组
举个例子,数组1~10;如何将其储存在C数组中呢,只需要将1~10赋值给value即可
那么如何求和呢,下面是树状数组的第二个功能代码
int getsum(int k)
{
int sum=0;
while(k>0){
sum+=d[k];
k-=lowbit(k);
}
return sum;
}
这个就非常好理解啦!如果我想求1~10的和,只需传入10既可以啦~
那么如果我想求的区间不是从1开始呢
也非常简单,例如我要求区间[r,l]的区间和,那么就是getsum(l)-getsum(r-1);这里r一定要减一,不然就不包含r本身了。
其实就是那么简单啦,完整代码如下(例求1~10)的和
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int d[32005],l[32005];
int lowbit(int k)
{
return (k&(-k));
}
void add(int pos,int v)
{
while (pos <= 100 + 1)
{
d[pos]+=v;
pos += lowbit(pos);
}
}
int getsum(int k)
{
int sum=0;
while(k>0){
sum+=d[k];
k-=lowbit(k);
}
return sum;
}
int main(){
memset(d,0,sizeof(d));
for(int i=1;i<=100;i++)
{
int t;
t=i;
add(i,t);
}
cout<<getsum(10)<<endl;
return 0;
}