树状数组详解NOICSP

树状数组详解NOI_CSP_ACMICPC树状数组的应用背景区间查询问题是信息学竞赛中高级别比赛的一个重要类型题。往往在一个10^6大小的区间内，进行10^4的操作（在线或离线）。这种情况下，我们很难将10^4次操作进行压缩，唯一可以考虑的压缩对象就是10^6的区间。考虑在对数时间复杂度内处理这个区间的问题，一般有两个角度：倍增或树结构。而树状数组就是倍增法在区间查询问题的体现，线段树是树结构在这个问题上的应用。树状数组树状数组又称二叉索引树（BinaryIndexedTree）多用于高效计算数列的前缀和、区间和等RMQ问题。我们知道所有的整数都可以表示成2的幂和，例如19可以表示为16+2+1，即2^4+2^1+2^0。这样一串序列可以表示成一系列子序列的和。这样，便可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和极其相似。树状数组呈如下样子：数组第一个元素的值为数列第一个元素的值；第二个元素的值为数列前两个元素值的和；第三个元素值为数列第三个元素的值；第四个元素值为数列前四个元素的值......，以此类推。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[2]+C[3]+A[4]这样如果我们知道整个数列前7个元素的累加和，只需要累加树状数组中第四，第六，第七个元素即可。基于此，利用前缀和/差分技术（详见文章《信息学竞赛中的差分技巧》）就可以求得某一个区间内的值的累加和，即区间和。上面已经解释了如何用树状数组求区间和。那么如果要更新某一个点的值呢？已知C[i]=C[i+2^k]+C[i+2^k+2^k]+...+A[i]，那么更新某A[i]的值，则会影响到所有包含有A[i]位置，如C[i+2^k]、C[(i+2^k)+2^k]...。那么构造一个树状数组的代码则为：Lowbit()技术这里需要介绍一下lowbit()技术。Lowbit()技术实在涉及到二进制位运算中普遍涉及的一种结束。在树状数组、状态压缩动态规划、数位哈希等问题都有应用。Lowbit()技术利用了负数的存储特性：负数以补码存储。对于整数运算x&(-x)有：当x为0时，即0&0，结果为0；当x为奇数时，最后一个比特位为1，取反加1没有进位，故x和-x除最后一位外前面的位正好相反，按位与结果为0。结果为1。当x为偶数，且为2的m次方时，x的二进制表示中只有一位是1即从右往左的第m+1位。其右边有m位0，故x取反加1后，从右到左第有m个0，第m+1位及其左边全是1。这样x&(-x)得到的就是x。 当x为偶数，却不为2的m次方的形式时，可以写作x=y*(2^k)。其中，y的最低位为1。实际上就是把x用一个奇数左移k位来表示。这时，x的二进制表示最右边有k个0，从右往左第k+1位为1。当对x取反时，最右边的k位0变成1，第k+1位变为0；再加1，最右边的k位就又变成了0，第k+1位因为进位的关系变成了1。左边的位因为没有进位，正好和x原来对应的位上的值相反。二者按位与，得到：第k+1位上为1，左边右边都为0。结果为2^k。简言之，x&(-x)当x为0时结果为0；x为奇数时，结果为1；x为偶数时，结果为x中2的最大次方的因子。lowbit()即取2^k。例题：单点修改+区间查询C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人。例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了。Derek对Tidy的计算速度越来越不满。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？输入第一行一个整数T，表示有T组数据。每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。接下来每行有一条命令，命令有4种形式：(1)Addij,i和j为正整数,表示第i个营地增加j个人（j不超过30）(2)Subij,i和j为正整数,表示第i个营地减少j个人（j不超过30）;(3)Queryij,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;(4)End表示结束，这条命令在每组数据最后出现;每组数据最多有40000条命令。对第i组数据,首先输出“Casei:”和回车,对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。此题是一道单点修改，区间查询的模板题。观察数据量可以看出此题为多样例题目，而且每组有4*10^4个命令，每个命令涉及的区间有5*10^4个数据。这样的数据量采用普通的数据结构是无法在有效的时间复杂度内胜任的。所以可以考虑树状数组，当然考虑线段树也是可行的。这个问题在其他相关文章中会进行讨论。题目中的调增，即加法运算可以用加法运算；调减，即减法运算可以累加一个负值。通过lowbit()技术找出在某个单点调增/调减所涉及到的所有的点，然后逐一进行增减。即完成单点修改。在区间查询，如查询[l,r]区间的区间和时，可以考虑使用前缀和技巧，用sum[r]-sum[l-1]，在O(1)的时间复杂度内解决前缀和问题。当然前缀和的查询也需要使用lowbit(）技术查出树状数组所影响到的所有点，然后进行累加。篇幅所限，题目样例及代码请发消息讨论。谢谢。例题：区间修改+单点查询：N个气球排成一排，从左到右依次编号为1,2,3....N。每次给定2个整数a，b(a<=b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第i个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？每个测试实例第一行为一个整数N,(N<=100000)。接下来的N行，每行包括2个整数a，b(1<=a<=b<=N)。当N=0，输入结束。每个测试实例输出一行，包括N个整数，第i个数代表第i个气球总共被涂色的次数。此题为区间修改（一部分气球染色）及单点查询（染色次数）的模板题目。可以定义数组a[]为气球被染色的次数。如果暴力处理N次区间修改时间复杂度为O(n^2)，这个时间复杂度时不可接受的。而采用树状数组，将区间[L,R]内的数a[x]逐一进行单点修改，时间复杂度会更差，为O(n^2*logn)。这种情况可以考虑用差分数组处理区间修改问题。（详见文章《信息学竞赛中的差分技巧》）。差分数组定义为D[k]=a[k]-a[k-1]，即原数组相邻元素的差。从定义可得，a[k]为差分数组D[k]的前缀和，即a[k]=D1+D2+...+D[k]。将求a[k]转化为求D[k]的前缀和，利用树状数组来处理。对于区间[L,R]的修改问题，作操作将D[L]加上d;将D[R+1]减去d。用树状数组sum()函数求前缀和sum[x]=D[1]+D[2]+...+D[x]。则有：1<=x<L，前缀和sum[x]不变；L<=x<=R,前缀和sum[x]增加了d；R<x<=n,前缀和sum[x]不变，被D[R+1]中减去的d抵消了。sum[x]就是a[x]，这样得到单点查询的结果。利用差分，可以将区间问题转换为单点问题。如果区间内每个元素都修改，复杂度为O(n)；用差分转换为只记录两个端点后，时间复杂度将为O(1)。篇幅所限，题目样例及代码请发消息讨论。谢谢。区间修改+区间查询当查询不再是一个单点的值，而是一个区间[l,r]的和，仅用一个树状数组是无法高效完成区间修改和区间查询的。因为树状数组tree[]已经用于区间修改了，它的sum()函数计算了单点的值，不能再用于求[l,r]的区间和。如果采用另一个树状数组做区间查询，效率也不高。因为做一次长度为k的区间修改，计算区内每一个单点的时间复杂度为O(logN)。如果继续用另一个树状数组处理这k个单点，复杂度为O(k*logN)。做n次修改查询时间复杂度为O(n^2*logN)。这个时间复杂度是难以被接受的。一般情况下，区间修改+区间查询在竞赛实践中会采用线段树+lazyTag技术解决。当然如果一定要要用树状数组解决区间修改+区间查询问题，需要用差分数组与树状数组相结合的二阶数状数组完成。例题：树状数组区间修改+区间查询已知一个数列，你需要进行下面两种操作：将某区间每一个数加上k。求出某区间每一个数的和。输入第一行包含两个整数n,m，分别表示该数列数字的个数和操作的总个数。第二行包含n个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来m行每行包含3或4个整数，表示一个操作，具体如下：1xyk：将区间[x,y]内每个数加上k。2xy：输出区间[x,y]内每个数的和。输出包含若干行整数，即为所有操作2的结果。本题求区间和，即sum(L,R)=a[L]+a[L+1]+...+a[R]=sum(1,R)-sum(1,L-1)。故，区间和问题转换为求sum(1,k)的问题。定义一个差分数组D[]。它和原数组a[]的关系仍然是D[k]=a[k]-a[k-1]。有a[k]=D[1]+D[2]+...+D[k]。推导区间和：若区间和与前缀和有关，可用树状数组求解。a1+a2+...+ak=D1+(D1+D2)+...+(D1+D2+...+Dk)=k*D1+(k-1)*D2+(k-2)*D3+...+(k-(k-1))*Dk=k*(D1+D2+...+Dk)-(D2+2*D3+...+(k-1)*Dk)公式的最后一行求两个前缀和，用两个树状数组分别处理，一个实现Di，一个实现(i-1)*Di。代码时间复杂度为O(m*logN)。时间复杂度可以被接受。篇幅所限，题目样例及代码请发消息讨论。谢谢。例题：二维区间修改+区间查询第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n*m矩阵。第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。第五分钟，和雪说，要有耐心，于是便有了时间限制。第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。——《上帝造裸题的七分钟》。所以这个神圣的任务就交给你了。输入数据的第一行为X，n，m，代表矩阵大小为n*m。从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：Labcddelta——代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。kabcd——代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。请注意，k为小写。针对每个k操作，输出一行答案。此题明显为二维区间问题。解决二维区间问题，需要用二维差分数组。定义二维差分数组D[][]，它与矩阵元素a[][]的关系：D[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]。a[c][d]可以看作是(1,1)(c,d)为顶点的矩阵内的D[i][j