一维与二维树状数组.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