下载文档原格式
树状数组及其应用(Binary Indexed Trees)一、什么是树状数组【引例】假设有一列数{A i}（1<=i<=n），支持如下两种操作：1.将A k的值加D。
（k，D是输入的数）2.输出A s+A s+1+…+A t（s，t都是输入的数，s<=t）分析一：线段树建立一颗线段树（线段长度1~n）。
一开始所有结点的count值等于0。
对于操作1，如果把A k的值加D，则把所有覆盖了A k的线段的count值加D。
只有log2n 条线段会受到影响，因此时间复杂度是O（log2n）。
每条线段[x..y]的count值实际上就是A x+A x+1+…+A y的值。
对于操作2，实际上就是把[s..t]这条线段分解成为线段树中的结点线段，然后把所有的结点线段的count值相加。
该操作（ADD操作）在上一讲线段树中已介绍。
时间复杂度为O （log2n）。
分析二：树状数组树状数组是一种特殊的数据结构，这种数据结构的时空复杂度和线段树相似，但是它的系数要小得多。
增加数组C，其中C[i]=a[i-2^k+1]+……+a[i](k为i在二进制形式下末尾0的个数)。
由c数组的定义可以得出：i K1(1)201-2^0+1=1…1c[1]=a[1]2(10)212-2^1+1=1…2c[2]=a[1]+a[2]=c[1]+a[2]3(11)203-2^0+1=3…3c[3]=a[3]4(100)224-2^2+1=1…4c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4] 5(101)205-2^0+1=5…5c[5]=a[5]6(110)216-2^1+1=5…6c[6]=a[5]+a[6]=c[5]+a[6]………………为了对树状数组有个形象的认识，我们先看下面这张图。
如图所示，红色矩形表示的数组C[]就是树状数组。
我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。
树状数组简单易懂的详解1 什么是树状数组树状数组（Fenwick Tree），也叫做树形数组，是一种支持单点修改、区间查询的数据结构。
这种数据结构可以在O(log n)的时间复杂度内实现单点修改和区间查询，相较于线段树，树状数组实现较为简单。
2 树状数组的实现原理树状数组的核心思想是利用二进制中的位运算来维护前缀区间和。
假设有一个数组a[]，其前缀和为sum[]，那么对于每个下标i，只需要维护[1,i]这个区间的和，即sum[i]。
这样，当需要查询区间[1,r]的和时，只需要计算sum[r]即可，不需要遍历每一个元素。
对于单点修改操作，假设我们要将数组a[]的第i个元素修改为x，我们只需要将第i个元素的值改为x，并且要将[1,i]这个区间内所有的sum数组的值都加上x-a[i]，即将差值x-a[i]加到了[1,i]区间中。
3 树状数组的实现细节3.1 树状数组的初始化树状数组需要初始化为0，因为我们需要维护的是每个元素的前缀和，如果没有初始化为0，其前缀和也就变得不可预测了。
查询区间[1,r]的和时，只需要计算sum[r]即可。
具体实现过程为：从r开始向前跳，每一个位置的前缀和都加到一个答案变量ans中，直到跳到0为止。
可以使用以下的代码实现：```C++int query(int x){int ans = 0;while(x > 0){ans += tree[x];x -= lowbit(x);}return ans;}```修改操作也很简单，只需要将第i个位置的值改为x，然后将[1,i]这个区间内所有的sum数组的值都加上x-a[i]，即将差值x-a[i]加到了[1,i]区间中，可以使用以下的代码实现：```C++void update(int x, int val){while(x <= n){tree[x] += val;x += lowbit(x);}}```4 树状数组与线段树的比较相对于线段树，树状数组的实现更为简单，而且更加省空间。
[数据结构]树状数组专题做数据结构的题真是异常的能让人感到自己在脱菜的路上迈进啊。
这一次来看看树状数组。
树状数组的基本知识已经被各种大牛和菜鸟讲到烂了，我就不多说了，下面给出基本操作的代码。
假定原数组为a[1..n]，树状数组b[1..n]，考虑灵活性的需要，代码使用int *a传数组。
#define lowbit(x) ((x)&(-(x)))int sum(int *a,int x){int s=0;for(;x;x-=lowbit(x))s+=a[x];return s;}void update(int *a,int x,int w){for(;x<=n;x+=lowbit(x))a[x]+=w;}sum(x)返回原数组[1,x]的区间和，update(x,w)将原数组下标为x的数加上w。
这两个函数使用O(logn)的时间和O(n)的空间完成单点加减，区间求和的功能。
接下来做一些升级，让树状数组完成区间加减，单点查询的功能。
考虑将原数组差分，令d[i]=a[i]-a[i-1]，特别地，d[1]=a[1]。
那么区间[l,r]整体加上k的操作就可以简单地使用d[l]+=k;d[r+1]-=k来完成了。
此时a[i]=d[1]+..+d[i]，所以单点查询a[i]实际上就是在求d数组的[1..i]区间和，很容易完成了。
下面再升级一次，完成区间加减，区间求和的功能。
仍然沿用d数组，考虑a数组[1,x]区间和的计算。
d[1]被累加了x次，d[2]被累加了x-1次，...，d[x]被累加了1次。
因此得到sigma(a[i])=sigma{d[i]*(x-i+1)}=sigma{ d[i]*(x+1) -d[i]*i }=(x+1)*sigma(d[i])-sigma(d[i]*i)所以我们再用树状数组维护一个数组d2[i]=d[i]*i，即可完成任务。
POJ 3468就是这个功能的裸题...下面给出代码：// POJ 3468 Using BIT#include <cstdio>const int fin=0,maxn=100010;__int64 a[maxn],b[maxn],c[maxn];int n,m;inline int lowbit(const int &x){return x&(-x);}__int64 query(__int64 *a,int x){__int64 sum=0;while(x){sum+=a[x];x-=lowbit(x);}return sum;}void update(__int64 *a,int x,__int64 w){ while(x<=n){a[x]+=w;x+=lowbit(x);} }int main(){int l,r,i;__int64 ans,w;char ch;if(fin){freopen("t.in","r",stdin);freopen("t.out","w",stdout);}scanf("%d%d",&n,&m);a[0]=0;for(i=1;i<=n;++i){scanf("%I64d",&a[i]);a[i]+=a[i-1];}while(m--){scanf("%c",&ch);while(ch!='Q' && ch!='C')scanf("%c",&ch);if(ch=='Q'){scanf("%d%d",&l,&r);ans=a[r]-a[l-1]+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1);printf("%I64d\n",ans);}else{scanf("%d%d%I64d",&l,&r,&w);update(b,l,w);update(b,r+1,-w);update(c,l,w*l);update(c,r+1,-(r+1)*w);}}if(fin){fclose(stdin); fclose(stdout);}return 0;}====================================一维到二维的分割线=======================================接下来到二维树状数组。
树状数组的操作树状数组的⼀些基本操作。
树状数组⽀持单点修改和查询区间和的操作，但和线段树不同，它不⽀持区间修改操作（有些题⽬可以将区间修改转化为单点修改，有些则不可以）。
下⾯介绍树状数组的预处理和基本操作。
1.求lowbit(n)上⼀篇博客介绍了lowbit的定义和使⽤定义的基本求法。
但是依据定义求lowbit未免⿇烦。
因⽽，求lowbit需要导⼊公式：lowbit(n)=n&(-n)。
求lowbit函数：int lowbit(int n){//求n的lowbitreturn n&(-n);}2.对某个元素进⾏加法操作根据树状数组的性质，对于任意⼀个结点x，只有结点c[x]及其祖先结点保存的区间和中含a[x]，所以我们只需要对x不断向上搜索即可。
代码：void update(int x,int y){//将x位置元素加上yfor(;x<=N;x+=lowbit(x){//依次寻找x的⽗节点c[x]+=y;//进⾏更新}}这⾥在寻找x的⽗节点时运⽤了上⼀篇博客中的性质③（具体的证明⽅法我也不会qwq）。
举例证明：假设我们要对A[2]进⾏加x的操作。
2的lowbit值为2，则第⼀步2变成了4，对C[4]进⾏处理。
4的lowbit值为4，则第⼆步变成了8，对C[8]进⾏处理。
此时已到达循环边界。
再假设我们要对A[5]进⾏加x的操作。
5的lowbit值为1，则第⼀步5变成了6，对C[6]进⾏处理。
6的lowbit值为2，则第⼆步变成了8，对C[8]进⾏处理。
此时已到达循环边界。
3.查询前缀和操作前缀和的求法：求出x的⼆进制表⽰中每个等于1的位，把[1,x]分成logN个⼩区间，⽽每个⼩区间的区间和已保存在数组c中。
代码（我也不会证）：int sum(int x){//求1~x的区间和int ans=0;for(;x;x-=lowbit(x);){ans+=c[x];}return ans;}举例证明：假设我们要求A[6]的前缀和。
第01讲什么是树状数组？树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。
有些同学会觉得很奇怪。
用一个数组S[i]保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？但是，如果题目的A[]会改变呢？例如：我们来定义下列问题：我们有n个盒子。
可能的操作为1.向盒子k添加石块2.查询从盒子i到盒子j总的石块数自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。
但是用树状数组，对操作1和2的时间复杂度都为O(logn)。
第02讲图解树状数组C[]现在来说明下树状数组是什么东西？假设序列为A[1]~A[8]网络上面都有这个图，但是我将这个图做了2点改进。
（1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。
（2）C[i]为A[i]对应的那一列的最高的节点。
现在告诉你：序列C[]就是树状数组。
那么C[]如何求得？C[1]=A[1];C[2]=A[1]+A[2];C[3]=A[3];C[4]=A[1]+A[2]+A[3]+A[4];C[5]=A[5];C[6]=A[5]+A[6];C[7]=A[7];C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];以上只是枚举了所有的情况，那么推广到一般情况，得到一个C[i]的抽象定义：因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C[i]=C[i]的所有叶子的和。
现在不得不引出关于二进制的一个规律：先仔细看下图：将十进制化成二进制，然后观察这些二进制数最右边1的位置：1 --> 000000012 --> 000000103 --> 000000114 --> 000001005 --> 000001016 --> 000001107 --> 000001118 --> 000010001的位置其实从我画的满二叉树中就可以看出来。
树状数组和线段树-电脑资料一、树状数组在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]，实现：对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。
Lowbit(x)=xand-x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。
具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。
如C12=A9+A10+A11+A12=C10+A11+A12如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。
预处理时先把C数组清空，然后执行n次add操作。
总时间为O（nlogn）如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。
对于query（L,R）=SR-SL-1。
代码：varb,c,f:array[0..100000]oflongint;ff,a:Array[0..100000]ofboolean; i,j,m,n,x,y,ans,l,r,tmp:longint; s:string;functiondfs(x:longint):longint; beginifx<=1thenexit;c[f[x]]:=c[f[x]]+c[x];dfs(f[x]);end;proceduredfs1(x:longint);begindec(c[x]);ifx<=1thenexit;dfs1(f[x]);end;proceduredfs2(x:longint);begininc(c[x]);ifx<=1thenexit;dfs2(f[x]);beginreadln(n);fillchar(ff,sizeof(ff),true); fori:=1ton-1dobeginreadln(x,y);f[y]:=x;inc(b[x]);end;fori:=1tondoc[i]:=1;fori:=1tondobeginifb[i]=0thendfs(i);end;readln(m);fori:=1tomdobeginx:=0;readln(s);ifs[1]='Q'thenforj:=3tolength(s)dox:=x*10+ord(s[j])-ord('0');writeln(c[x]);end;ifs[1]='C'thenbeginforj:=3tolength(s)dox:=x*10+ord(s[j])-ord('0');ifff[x]thendfs1(x)elsedfs2(x);ff[x]:=notff[x];end;end;End.二、线段树1,.线段树的结构:区间：用一对数a和b表示一个前闭后开的区间[a,b)。
树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：令这棵树的结点编号为C1，。
令每个结点的值为这棵树的值的总和，那么容易发现：C1 = A1C2 = A1 + A2C3 = A3 C4 = A1 + A2 + A3 + A4C5 = A5C6 = A5 + A6C7 = A7C8 = 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算这个2^k有一个快捷的办法，定义一个函数如下即可：int lowbit(int x){return x&(x^(x–1));}当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可：step1:令sum = 0，转第二步；step2:假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；step3: 令n = n –lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：n = n –lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。
而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。
