《一维与二维树状数组.docx》由会员分享，可在线阅读，更多相关《一维与二维树状数组.docx（11页珍藏版）》请在三一办公上搜索。
1、昨天学了一下树状数组，随笔都写了一大半，结果一个不小心就把他给删了，哎。 今天就当是复习吧！再写一次。如果给定一个数组，要你求里面所有数的和，一般都会想到累加。但是当那个数组很 大的时候，累加就显得太耗时了，时间复杂度为O（n），并且采用累加的方法还有一个局限， 那就是，当修改掉数组中的元素后，仍然要你求数组中某段元素的和，就显得麻烦了。所以 我们就要用到树状数组，他的时间复杂度为O（lgn），相比之下就快得多。下面就讲一下 什么是树状数组：一般讲到树状数组都会少不了下面这个图：下面来分析一下上面那个图看能得出什么规律：据图可知：c1=a1，c2=a1+a2，c3=a3，c4=a1+a2+a3
2、+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的个数）。那么，如何求a
3、Ak呢？求法如下：int lowbit(int x)(return x&(-x);lowbit （）的返回值就是2Ak次方的值。求出来2Ak之后，数组c的值就都出来了，接下来我们要求数组中所有元素的和。（二）求数组的和的算法如下：（1）首先，令sum=0，转向第二步；（2）接下来判断，如果n0的话，就令sum=sum+cn转向第三步，否则的话，终止 算法，返回sum的值；（3）n=n - lowbit（n）（将n的二进制表示的最后一个零删掉），回第二步。代码实现：int Sum（int n）（int sum=0;while（n0）（sum+=cn;n=n-lowbit（n）;return su
4、m;（三）当数组中的元素有变更时，树状数组就发挥它的优势了，算法如下（修改为给 某个节点i加上x）:（1）当i=n时，执行下一步；否则的话，算法结束；（2）ci=ci+x，i=i+lowbit（i）（在i的二进制表示的最后加零），返回第一步。代码实现：void change(int i,int x)(while(i 0)sum += inend;end -= Lowbit(end) return sum;对某个元素进行加法操作：void plus(int pos , int num)(while(pos = n)(inpos += num;pos += Lowbit(pos);当要频繁的对数组
5、元素进行修改,同时又要频繁的查询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 + A
6、8C16 = 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+lo
7、wbit(i)给Ai加上x后，更新一系列Cjupdate(int i,int x)(while(i0)(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
8、(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
9、(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) 对矩阵里的某个数加上一个整
10、数(可正可负)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,a4
11、8,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=a1
12、1+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+
13、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 0; x -= lowbit(x) (for(int y = j; y 0; y -=
14、 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;i5;
15、i+)for(int j=1;j6;j+)Modify(i,j,1);/给 A每个元素加 1for(int i=1;i5;i+)(for(int j=1;j 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 java Test111111111111111111111216
