树状数组及其应用( 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数组的定义可以得出：为了对树状数组有个形象的认识，我们先看下面这张图。

如图所示，红色矩形表示的数组C[]就是树状数组。

我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。

【操作1】修改A[i]的值。

可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(logn)。

定理1：若a[k]所牵动的序列为C[p1]，C[p2]……C[p m]，则p1=k，而p i+1=p i+2li （l i为p i在二进制中末尾０的个数）。

例如a[1]……a[8]中，a[3] 添加x；p1=k=3 p2=3+20=4p3=4+22=8 p4=8+23=16>8由此得出，c[3]、c[4]、c[8]亦应该添加x。

定理的证明如下：【引理】若a[k]所牵动的序列为C[p1]，C[p2] ……C[p m]，且p1 <p2 < ……<p m，则有l1 <l2< ……<l m（l i为p i在二进制中末尾０的个数）。

证明：若存在某个i有l i≥l i+1，则p i-2 li +1≤k≤p i，p i+1-2li+1+1≤k≤p i+1，p i+1– 2 Li+1+1≤k≤p i，即：P i+1≤P i+2Li+1–1 (1)而由L i=L i+1、P i < P i+1可得P i+1≥P i + 2Li(2)(1) (2)矛盾，可知l1 <l2 <……<l m定理：p1=k，而p i+1=p i+2li证明：因为p1 <p2 < ……<p m且C[p1]，C[p2] ……C[p m]中包含a[k]，因此p1=k。

在p 序列中，p i+1=p i +2li是p i后最小的一个满足l i+1 >li的数（若出现P i+x比p i+1更小，则x<2li，与x在二进制中的位数小于l i相矛盾）。

P i+1=p i+2li，l i+1≥l i+1。

由p i-2li+1≤K≤P i可知，P i+1-2li+1+1≤P i+2li–2*2li+1=P i– 2li+1≤K≤P i≤P i+1 ，故P i与p i+1之间的递推关系式为P i+1=P i+2li【操作2】求数列的前n项和。

只需找到n以前的所有最大子树，把其根节点的C加起来即可。

不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数, 因此，求和操作的复杂度也是O(logn)。

根据c[k]=a[k-2l+1]+ … +a[k] (l为k在二进制数中末尾０的个数)，我们从k1=k出发，按照k i+1=k i-2lki（lk i为k i在二进制数中末尾0的个数）递推k2，k3，…，k m (k m+1=0)。

由此得出S=c[k1]+c[k2]+c[k3] + … + c[k m]例如，计算a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]k1=7k2= k1-2l1=7-20=6k3= k2-2l2=6-21=4k4= k3-2l3=4-22=0即a[1]+a[2]+ a[3]+a[4]+ a[5]+a[6]+ a[7]=c[7]+c[6]+c[4]二、树状数组的操作函数在操作1和操作2中，我们反复提到求2^K（k为i的2进制中末尾0的个数），因此我们先来定义一个求数i的低位函数，返回这个值。

求低位函数（LowBit）LowBit，即2进制数中从最低位开始连续0的位数的关于2的幂，其值LowBit(x)= x and -x。

LowBit(x)显然就是not x中最低的是0的那一位，(not x)+1的那一位则会变成1，其更低的位全部变成0，而更高的位不变。

由于更高的位就是原数取反，和原数求and的值为0，最低位就是唯一的是1的位了。

所以LowBit(x)=x and((not x)+1)。

举例说明：在x=10101000时，x=10101000not x=01010111(not x)+1=01011000和原数求and就是1000。

同时not x=-x-1，所以LowBit(x)=x and -x。

有了lowbit函数，我们就可以方便地实现树状数组的修改（modify）、求和（getsum）两个操作。

操作1：modify(i, num)modify(i, num)：对数组a[] 中的第i 个元素加上num。

为了维护c[] 数组，我就必须要把c[] 中所有“管”着a[i] 的c[i] 全部加上num，这样才能随时以O(logn) 的复杂度进行getsum(i) 的操作。

而"i:=i+ lowbit(i)" 正是依次访问所有包含a[i] 的c[i] 的过程。

修改a[i]，我们需对c[i] , c[i+lowbit(i)] , c[i+lowbit(i)+lowbit(i+lowbit(i))] ……进行修改。

复杂度O(logn) 。

pascal代码:procedure modify(x,delta:longint);beginwhile x<=n dobegininc(c[x],delta);inc(x,lowbit(x));end;end;操作2：求和（getsum）getsum(i): 求和正好反过来，每次“i:=i-l owbit(i)” 依次求a[i] 之前的某一段和。

因为c[i] 有这样一个性质：Lowbit(i) 的值即为c[i] “管”着a[i] 中元素的个数，比如i = (101100)2，那么c[i] 就是从a[i] 开始往前数(100) 2 = 4 个元素的和，也就是c[i] = a[i] + a[i - 1] + a[i - 2] + a[i - 3]。

那么每次减去lowbit(i) 就是依次跳过当前c[i] 所能管辖的范围，以便不重不漏地求出所有a[i] 之前的元素之和。

a[1]+...+a[i]=c[i]+c[i-lowbit(i)]+c[i-lowbit(i)-lowbit(i-lowbit(i))]……复杂度O(logn)pascal代码:function sum(x:longint):longint;beginsum:=0;while x>0dobegininc(sum,c[x]);dec(x,lowbit(x));end;end;三、树状数组的应用【例1】Stars（POJ2352）（时间1秒，空间64M）/JudgeOnline/problem?id=2352DescriptionAstronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.You are to write a program that will count the amounts of the stars of each level on a given map.InputThe first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.OutputThe output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.Sample Input51 15 17 13 35 5Sample Output1211HintThis problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.【题目大意】有N(1<=N<=15000)颗星星，坐标(0<=X,Y<=32000)。