一维与二维树状数组.docx

昨天学了一下树状数组，随笔都写了一大半，结果一个不小心就把他给删了，哎。 今天就当是复习吧！再写一次。如果给定一个数组，要你求里面所有数的和，一般都会想到累加。但是当那个数组很 大的时候，累加就显得太耗时了，时间复杂度为O（n），并且采用累加的方法还有一个局限， 那就是，当修改掉数组中的元素后，仍然要你求数组中某段元素的和，就显得麻烦了。所以 我们就要用到树状数组，他的时间复杂度为O（lgn），相比之下就快得多。下面就讲一下 什么是树状数组：一般讲到树状数组都会少不了下面这个图：下面来分析一下上面那个图看能得出什么规律：据图可知：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，c9=a9，c10=a9+a10， c11=a11c16=a1+a2+a3+a4+a5+a16。分析上面的几组式子可知，当i为奇数时，ci=ai ；当i为偶数时，就要看i的因子 中最多有二的多少次幕，例如，6的因子中有2的一次幕，等于2，所以c6=a5+a6 （由 六向前数两个数的和），4的因子中有2的两次幕，等于4，所以c4=a1+a2+a3+a4 （由 四向前数四个数的和）。（一）有公式：cn=a（n-aAk+1）+an （其中k为n的二进制表示中从右往左数的0的个数）。那么，如何求aAk呢？求法如下：int lowbit(int x)(return x&(-x);lowbit （）的返回值就是2Ak次方的值。求出来2Ak之后，数组c的值就都出来了，接下来我们要求数组中所有元素的和。（二）求数组的和的算法如下：（1）首先，令sum=0，转向第二步；（2）接下来判断，如果n>0的话，就令sum=sum+cn转向第三步，否则的话，终止 算法，返回sum的值；（3）n=n - lowbit（n）（将n的二进制表示的最后一个零删掉），回第二步。代码实现：int Sum（int n）（int sum=0;while（n>0）（sum+=cn;n=n-lowbit（n）;return sum;（三）当数组中的元素有变更时，树状数组就发挥它的优势了，算法如下（修改为给 某个节点i加上x）:（1）当i<=n时，执行下一步；否则的话，算法结束；（2）ci=ci+x，i=i+lowbit（i）（在i的二进制表示的最后加零），返回第一步。代码实现：void change(int i,int x)(while(i<=n)(ci=ci+x;i=i+lowbit(i);树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。在解题过程中，我们有时需要维护一个数组的前缀和Si=A1+A2+.+Ai。但是不难发现，如果我们修改了任意一个Ai,Si、Si+1.Sn都会发生变化。可以说，每次修改Ai后，调整前缀和S在最坏情况下会需要O(n)的时间。当n非常大时，程序会运行得非常缓慢。因此，这里我们引入''树状数组”，它的修改与求和都是O(logn)的，效率非常高。【理论】为了对树状数组有个形象的认识，我们先看下面这张图。如图所示，红色矩形表示的数组C口就是树状数组。这里，Ci表示Ai-2人k+1到Ai的和，而k则是i在二进制时末尾0的个数，或者说是i用2的幂方和表示时的最小指数。(当然，利用位运算，我们可以直接计算出2*=i&(n(i-1)同时，我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过 logn。所以，当我们修改Ai的值时，可以从Ci往根节点一路上溯，调整这条路上的所有C口 即可，这个操作的复杂度在最坏情况下就是树的高度即O(logn)。另外，对于求数列的前 n项和，只需找到n以前的所 有最大子树，把其根节点的C 加起来即可。不难发现，这些子树的 数目是n在二进制时1的个 数，或者说是把n展开成2的 幂方和时的项数，因此，求和操作的复杂 度也是O(logn)。接着，我们考察这两种操作下标变化的规律：首先看修改操作：已知下标i，求其父节点的下标。我们可以考虑对树从逻辑上转化：如图，我们将子树向右对称翻折，虚拟出一些空白结点(图中白色)，将原树转化成完全 二叉树。有图可知，对于节点i，其父节点的下标与翻折出的空白节点下标相同。因而父节点下标p=i+2人k (2人k是i用2的幂方和展开式中的最小幂，即i为根节点子 树的规模)即 p = i + i&(i人(i-1)。接着对于求和操作：因为每棵子树覆盖的范围都是2的幂，所以我们要求子树i的前一棵树，只需让i减去2 的最小幂即可。即 p = i - i&(i人(i-1)。至此，我们已经比较详细的分析了树状数组的复杂度和原理。在最后，我们将给出一些树状数组的实现代码，希望读者能够仔细体会其中的细节。【代码】求最小幂2人k:int Lowbit(int t)return t & ( t 八(t - 1 );求前n项和：int Sum(int end)int sum = 0;while(end > 0)sum += inend;end -= Lowbit(end) return sum;对某个元素进行加法操作：void plus(int pos , int num)(while(pos <= n)(inpos += num;pos += Lowbit(pos);当要频繁的对数组元素进行修改,同时又要频繁的查询Q访 数组内任一区间元素之和的时候,可以考虑使用树状数 组.通常对一维数组最直接的算法可以在0(1 )时间内完 成一次修改，但是需要0(n)时间来进行一次查询.而树 状数组的修改和查询均可在O(log(n)的时间内完成.一、回顾一维树状数组假设一维数组为Ai(i=1,2,.n),则与它对应的树状数组Ci(i=1,2,.n)是这样定义的：C1 = A1C2 = A1 + A2C3 = A3C4 = A1 + A2 + A3 + A4C5 = A5C6 = A5 + A6C7 = A7C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16(1)Ct展开以后有多少项？由下面公式计算：int lowbit(int t)(/计算 ct展开的项数return t&(-t);)Ct展开的项数就是lowbit(t),Ct就是从At开始往左连续求lowbit(t)个数的和.(2)修改比如修改了 A3,必须修改 C3,C4,C8,C16,C32,C64.当我们修改Ai的值时，可以从Ci往根节点一路上溯，调整这条路上的所有C即可，对于节点i，父节点下标 p=i+lowbit(i)给Ai加上x后，更新一系列Cjupdate(int i,int x)(while(i<=n)(ci=ci+x;i=i+lowbit(i);(3)求数列A的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。如：Sun=C1=A1;Sun(2)=C2=A1+A2;Sun(3)=C3+C2=A1+A2+A3;Sun(4)=C4=A1+A2+A3+A4;Sun(5)=C5+C4;Sun(6)=C6+C4;Sun(7)=C7+C6+C4;Sun(8)=C8;int Sum(int n) /求前 n 项的和.(int sum=0;while(n>0)(sum+=Cn;n=n-lowbit(n);return sum;lowbit(1)=1lowbit(5)=1lowbit(9)=1lowbit(13)=1lowbit(17)=1lowbit(21)=1lowbit(25)=1lowbit(29)=1lowbit(2)=2lowbit(6)=2lowbit(10)=2lowbit(14)=2lowbit(18)=2lowbit(22)=2lowbit(26)=2lowbit(30)=2lowbit(3)=1lowbit(7)=1lowbit(11)=1lowbit(15)=1lowbit(19)=1lowbit(23)=1lowbit(27)=1lowbit(31)=1lowbit(4)=4lowbit(8)=8lowbit(12)=4lowbit(16)=16lowbit(20)=4lowbit(24)=8lowbit(28)=4lowbit(32)=32lowbit(33)=1lowbit(34)=2lowbit(35)=1lowbit(36)=4lowbit(37)=1lowbit(38)=2lowbit(39)=1lowbit(40)=8lowbit(41)=1lowbit(42)=2lowbit(43)=1lowbit(44)=4lowbit(45)=1lowbit(46)=2lowbit(47)=1lowbit(48)=16lowbit(49)=1lowbit(50)=2lowbit(51)=1lowbit(52)=4lowbit(53)=1lowbit(54)=2lowbit(55)=1lowbit(56)=8lowbit(57)=1lowbit(58)=2lowbit(59)=1lowbit(60)=4lowbit(61)=1lowbit(62)=2lowbit(63)=1lowbit(64)=64二、树状数组可以扩充到二维。问题：一个由数字构成的大矩阵，能进行两种操作1) 对矩阵里的某个数加上一个整数(可正可负)2) 查询某个子矩阵里所有数字的和，要求对每次查询，输出结果。一维树状数组很容易扩展到二维，在二维情况下:数组A的树状数组定义为：Cxy = Z ai其中，x-lowbit(x) + 1 <= i <= x,y-lowbit(y) + 1 <= j <= y.例：举个例子来看看C的组成。设原始二维数组为：A=a11,a12,a13,a14,a15,a16,a17,a18,a19),(a21,a22,a23,a24,a25,a26,a27,a28,a29),a31,a32,a33,a34,a35,a36,a37,a38,a39， a41,a42,a43,a44,a45,a46,a47,a48,a49;那么它对应的二维树状数组C呢？记：B1=a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,.这是第一行的一维树状数组B2=a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,.这是第二行的一维树状数组B3=a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,.这是第三行的一维树状数组B4=a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,.这是第四行的一维树状数组那么：C11=a11,C12=a11+a12,C13=a13,C14=a11+a12+a13+a14,c15=a15,C16=a15+a16,. .这是A第一行的一维树状数组C21=a11+a21,C22=a11+a12+a21+a22,C23=a13+a23,C24=a11+a12+a13+a14+a21+a2 2+a23+a24,C25=a15+a25,C26=a15+a16+a25+a26,.这是A数组第一行与第二行相加后的树状数组C31=a31,C32=a31+a32,C33=a33,C34=a31+a32+a33+a34,C35=a35,C36=a35+a36,. .这是A第三行的一维树状数组C41=a11+a21+a31+a41,C42=a11+a12+a21+a22+a31+a32+a41+a42,C43=a13+a23+a33 +a43,.这是A数组第一行+第二行+第三行+第四行后的树状数组搞清楚了二维树状数组C的规律了吗？仔细研究一下，会发现:(1)在二维情况下，如果修改了 Aij=delta测对应的二维树状数组更新函数为：private void Modify(int i, int j, int delta)( Aij+=delta;for(int x = i; x< A.length; x += lowbit(x) for(int y = j; y <Ai.length; y += lowbit(y)(Cxy += delta;(2)在二维情况下，求子矩阵元素之和E ai前(行和前j歹。)的函数为int Sum(int i, int j)(int result = 0;for(int x = i; x > 0; x -= lowbit(x) (for(int y = j; y > 0; y -= lowbit(y) (result += Cxy;return result;比如：Sun(1,1)=C11; Sun(1,2)=C12; Sun(1,3)=C13+C12;.Sun(2,1)=C21; Sun(2,2)=C22; Sun(2,3)=C23+C22;.Sun(3,1)=C31+C21; Sun(3,2)=C32+C22;例：测试一下:import java.util.Arrays;public class Test(int A;/原二维数组int C;/对应的二维树状数组public Test()(A=new int56;C=new int56;for(int i=1;i<5;i+)for(int j=1;j<6;j+)Modify(i,j,1);/给 A每个元素加 1for(int i=1;i<5;i+)(for(int j=1;j<6;j+)System.out.print(Aij+" ");/输出 A System.out.println();System.out.println(Sum(3,4);/求子二维数组的和Modify(2,3,4);/将 A23加 4System.out.println(Sum(3,4);/显示修改后的和private int lowbit(int t)( return t&(-t);int Sum(int i, int j)(int result = 0;for(int x = i; x > 0; x -= lowbit(x) (for(int y = j; y > 0; y -= lowbit(y) ( result += Cxy;return result;private void Modify(int i, int j, int delta)(Aij+=delta;for(int x = i; x< A.length; x += lowbit(x) for(int y = j; y <Ai.length; y += lowbit(y)( Cxy += delta;public static void main(String args)( Test t=new Test();C:java>java Test111111111111111111111216