初步搞懂树状数组
树状数组用来求区间元素和,求一次区间元素和的时间效率为O(logn)。
有些同学会觉得很奇怪。用一个数组S[i]保存序列A[]的前i个元素和,那么求区间i,j的元素和不就为S[j]-S[i-1],那么时间效率为O(1),岂不是更快?
但是,如果题目的A[]会改变呢?例如:
我们来定义下列问题,我们有n个盒子。可能的两个操作为:
1.向盒子k添加石块
2.查询从盒子i到盒子j总的石块数
自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。但是用树状数组,对操作1和2的时间复杂度都为O(logn)。
终于,我们得到了一个C[i]的具体定义:
C[i]=A[i-2^x+1]+…+A[i],其中x为i 的二进制数中的从右往左数有连续“0”的个数。(i>=1)
http://www.cnblogs.com/huangxincheng/archive/2012/12/05/2802858.html
展现了位运算与数组结合的神奇魅力
2 二维树状数组
树状数组用来求区间元素和,求一次区间元素和的时间效率为O(logn)。
有些同学会觉得很奇怪。用一个数组S[i]保存序列A[]的前i个元素和,那么求区间i,j的元素和不就为S[j]-S[i-1],那么时间效率为O(1),岂不是更快?
但是,如果题目的A[]会改变呢?例如:
我们来定义下列问题,我们有n个盒子。可能的两个操作为:
1.向盒子k添加石块
2.查询从盒子i到盒子j总的石块数
自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。但是用树状数组,对操作1和2的时间复杂度都为O(logn)。
网络上面都有上图,但是我将这个图做了2点改进。
(1)图中有一棵满二叉树,满二叉树的每一个结点对应A[]中的一个元素。
(2)C[i]为A[i]对应的那一列的最高的节点。
(2)C[i]为A[i]对应的那一列的最高的节点。
现在告诉你:序列C[]就是树状数组。那么C[]如何求得?
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[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
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[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
现在不得不引出关于二进制的一个规律:先仔细看下图:
将十进制化成二进制,然后观察这些二进制数最右边1的位置:
1 --> 00000001
2 --> 00000010
3 --> 00000011
4 --> 00000100
5 --> 00000101
6 --> 00000110
7 --> 00000111
8 --> 00001000
1 --> 00000001
2 --> 00000010
3 --> 00000011
4 --> 00000100
5 --> 00000101
6 --> 00000110
7 --> 00000111
8 --> 00001000
1的位置其实从我画的满二叉树中就可以看出来。但是这与C[]有什么关系呢?接下来的这部分内容很重要:
在满二叉树中,
以1结尾的那些结点(C[1],C[3],C[5],C[7]),其叶子数有1个,所以这些结点C[i]代表区间范围为1的元素和;
以10结尾的那些结点(C[2],C[6]),其叶子数为2个,所以这些结点C[i]代表区间范围为2的元素和;
以100结尾的那些结点(C[4]),其叶子数为4个,所以这些结点C[i]代表区间范围为4的元素和;
以1000结尾的那些结点(C[8]),其叶子数为8个,所以这些结点C[i]代表区间范围为8的元素和。
扩展到一般情况:
i 的二进制中的从右往左数有连续的x个“0”,那么拥有2^x个叶子,为序列A[]中的第i-2^x+1到第i个元素的和。以1结尾的那些结点(C[1],C[3],C[5],C[7]),其叶子数有1个,所以这些结点C[i]代表区间范围为1的元素和;
以10结尾的那些结点(C[2],C[6]),其叶子数为2个,所以这些结点C[i]代表区间范围为2的元素和;
以100结尾的那些结点(C[4]),其叶子数为4个,所以这些结点C[i]代表区间范围为4的元素和;
以1000结尾的那些结点(C[8]),其叶子数为8个,所以这些结点C[i]代表区间范围为8的元素和。
扩展到一般情况:
终于,我们得到了一个C[i]的具体定义:
C[i]=A[i-2^x+1]+…+A[i],其中x为i 的二进制数中的从右往左数有连续“0”的个数。(i>=1)
http://www.cnblogs.com/huangxincheng/archive/2012/12/05/2802858.html
展现了位运算与数组结合的神奇魅力
之所以采用这样的分布方式,是因为我们使用的是这样的一个公式:S[i]=a[i-2k+1]+....+a[i]。
其中:2k 中的k表示当前S[i]在树中的层数,它的值就是i的二进制中末尾连续0的个数,2k也就是表示S[i]中包含了哪些a[],
举个例子: i=610=01102 ;可以发现末尾连续的0有一个,即k=1,则说明S[6]是在树中的第二层,并且S[6]中有21项,随后我们求出了起始项:
a[6-21+1]=a[5],但是在编码中求出k的值还是有点麻烦的,所以我们采用更灵巧的Lowbit技术,即:2k=i&-i 。
则:S[6]=a[6-21+1]=a[6-(6&-6)+1]=a[5]+a[6]。
分离出最后的1
注意: 最后的1表示一个整数的二进制表示中,从左向右数最后的那个1。
由于我们经常需要将一个二进制数的最后的1提取出来,因此采用一种高效的方式来做这件 事是十分有必要的。令num是我们要操作的整数。在二进制表示中,num可以记为a1b, a代表最后的1前面的二进制数码,由于a1b中的1代表的是从左向右的最后一个1, 因此b全为0,当然b也可以不存在。比如说13=1101,这里最后的1右边没有0,所以b不存在。
我们知道,对一个数取负等价于对该数的二进制表示取反加1。所以-num等于(a1b)^- +1= a^- 0b^- +1。由于b全是0,所以b^- 全为1。最后,我们得到:
-num=(a1b)^- +1=a^- 0b^- +1=a^- 0(1…1)+1=a^- 1(0…0)=a^- 1b
现在,我们可以通过与操作(在C++,java中符号为&)将num中最后的1分离出来:
num & -num = a1b & a^- 1b = (0…0)1(0…0)
int lowbit(int t){//计算c[t]展开的项数 return t&(-t); } 例: lowbit(1)=1 C1 = A1 lowbit(2)=2 C2 = A1 + A2 lowbit(3)=1 C3 = A3 lowbit(4)=4 C4 = A1 + A2 + A3 + A4 lowbit(5)=1 C5 = A5 lowbit(6)=2 C6 = A5 + A6 lowbit(7)=1 C7 = A7 lowbit(8)=8 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ....... c[t]展开的项数就是lowbit(t),c[t]就是从a[t]开始往左连续求lowbit(t)个数的和,
public class TreeArray{ int n;//数组元素个数 int[] a;//原数组 int[] c;//对应的树状数组 public TreeArray(int[] a){ n=a.length; this.a=a; c=new int[a.length]; for(int i=1;i< a.length;i++){ //从下标1开始 for(int j=0;j< lowbit(i);j++) c[i]=c[i]+a[i-j]; } } private int lowbit(int t){//计算c[t]展开的项数 return t&(-t); } private void update(int i,int x){ while(i<=n){ c[i]=c[i]+x; i=i+lowbit(i); } } private int Sum(int k){ //求前k项的和. 从下标1开始 int sum=0; while(k>0){ sum+=c[k]; k=k-lowbit(k); } return sum; } public static void main(String args[]){ int a[]={0,1,2,3,4,5,6,7,8,9,10}; //从下标1开始 TreeArray ta=new TreeArray(a); System.out.println(ta.Sum(10)); ta.update(5,-20); System.out.println(ta.Sum(10)); System.out.println(ta.Sum(4)); } }http://blog.csdn.net/chenguolinblog/article/details/10050049
1 一维树状数组
1 什么是树状数组
树状数组是一个查询和修改复杂度都为log(n)的数据结构,假设数组A[1..n],那么查询A[1]+...+A[n]的时,间是log级别的,而且是一个在线的数据结构。
2 树状数组作用
我们经常会遇到动态连续和查询问题,给定n个元素A[1~N],让我们求sum[L,R] = A[L]+...+A[R],或者更改A[i]的值。
树状数组是一个查询和修改复杂度都为log(n)的数据结构,假设数组A[1..n],那么查询A[1]+...+A[n]的时,间是log级别的,而且是一个在线的数据结构。
2 树状数组作用
我们经常会遇到动态连续和查询问题,给定n个元素A[1~N],让我们求sum[L,R] = A[L]+...+A[R],或者更改A[i]的值。
假设数据很小的时候,那么我们利用暴力就可以搞定,这个时候更改A[i]的复杂度为O(1),但是求和的复杂度为O(n),如果有m次求和就是O(n*m),但是m很大的时候这个方法显然是不能够满足效率的要求。这个时候我们引入树状数组,树状数组的求和和更新都是O(logN),所以大大的降低了复杂度。
3 具体分析
1 建立树状数组就是先把A[] 和 C[]清空,然后假设有n个数那么就是做n次的update()操作就是建立树状数组,所以总的时间复杂度为O(nlogn)。
2 设原数组为A[1..N],树状数组为c[1..N],其中c[k] = A[k-(2^t)+1] + ... + A[k]。比如c[6] = A[5] + A[6]。
2 设原数组为A[1..N],树状数组为c[1..N],其中c[k] = A[k-(2^t)+1] + ... + A[k]。比如c[6] = A[5] + A[6]。
假设 A为被计数数组,C为树状数组(计数)
0000 0001:C1 = A1
0000 0010:C2 = A1 + A2
0000 0011:C3 = A3
0000 0100:C4 = A1 + A2 + A3 + A4
0000 0101:C5 = A5
0000 0110:C6 = A5 + A6
0000 0111:C7 = A7
0000 1000:C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
0001 0000:C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8+ A9 + A10 + A11 + A12 + A13 + A14 + A15+ A16
0000 0010:C2 = A1 + A2
0000 0011:C3 = A3
0000 0100:C4 = A1 + A2 + A3 + A4
0000 0101:C5 = A5
0000 0110:C6 = A5 + A6
0000 0111:C7 = A7
0000 1000:C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
0001 0000:C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8+ A9 + A10 + A11 + A12 + A13 + A14 + A15+ A16
3 也就是说,把k表示成二进制1***10000,那么c[k]就是A[1***00001] + A[1***00010] + ... + A[1***10000] 这一段数的和。
4 设一个函数lowbit(k)为取得k的最低非零位,容易发现,根据上面的表示方法,从A[1]到A[k]的所有数的总和即为
sum[k] = c[k] + c[k-lowestbit(k)] + c[k-lowestbit(k)-lowestbit(k-lowestbit(k))] + ... 于是可以在logk的时间内求出sum[k]。
sum[k] = c[k] + c[k-lowestbit(k)] + c[k-lowestbit(k)-lowestbit(k-lowestbit(k))] + ... 于是可以在logk的时间内求出sum[k]。
5 当数组中某元素发生变化时,需要改动的c值是c[k],c[k+lowestbit(k)], c[k+lowestbit(k)+lowestbit(k+lowestbit(k))] ... 这个复杂度是logN (N为最大范围)
6 如果题目要求sum[L , R] = sum[R]-sum[L-1]
sum[L-1] = A[1]+A[2]+...+A[L-1]
sum[R] = A[1]+A[2]+...+A[L]+...+A[R]
sum[R]-sum[L-1] = A[L]+A[L+2]+...+A[R]
sum[L-1] = A[1]+A[2]+...+A[L-1]
sum[R] = A[1]+A[2]+...+A[L]+...+A[R]
sum[R]-sum[L-1] = A[L]+A[L+2]+...+A[R]
7 树状数组的下标严格从1开始,所以如果出现0的情况要注意加1.(因为lowbit(0)是0所以如果出现为0的时候会进入无限循环中) , 树状数组中的每个元素至少含有它本身的一个值。
2 二维树状数组
1 二维树状数组说白了就是每一维都是树状数组
问题:一个由数字构成的大矩阵,能进行两种操作
1 对矩阵里的某个数加上一个整数(可正可负)
2 查询某个子矩阵里所有数字的和,要求对每次查询,输出结果。
2 一维树状数组很容易扩展到二维,在二维情况下:数组A[][]的树状数组定义为:
C[x][y] = ∑ a[i][j], 其中,x-lowbit(x) + 1 <= i <= x , y-lowbit(y) + 1 <= j <= y.
3 例:举个例子来看看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[][]呢?
记:
B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...} 这是第一行的一维树状数组
B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...} 这是第二行的一维树状数组
B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...} 这是第三行的一维树状数组
B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...} 这是第四行的一维树状数组
那么:
C[1][1] = a11 , C[1][2] = a11+a12 , C[1][3] = a13 , C[1][4] = a11 + a12 + a13 + a14 , c[1][5]=a15.这是A[][]第一行的一维树状数组
C[2][1] = a11 + a21 , C[2][2] = a11 + a12 + a21 + a22 , C[2][3] = a13 + a23 , C[2][4] = a11 + a12 + a13 + a14 + a21 + a22 + a23 + a24 这是A[][]数组第一行与第二行相加后的树状数组
C[3][1] = a31 , C[3][2] = a31 + a32 , C[3][3] = a33 , C[3][4] = a31 + a32 + a33 + a34 , C[3][5] = a35 , C[3][6]=a35+a36,...这是A[][]第三行的一维树状数组
C[4][1] = a11 + a21 + a31 + a41 , C[4][2] = a11 + a12 + a21 + a22 + a31 + a32 + a41 + a42 ,这是A[][]数组第一行+第二行+第三行+第四行后的树状数组
1 对矩阵里的某个数加上一个整数(可正可负)
2 查询某个子矩阵里所有数字的和,要求对每次查询,输出结果。
2 一维树状数组很容易扩展到二维,在二维情况下:数组A[][]的树状数组定义为:
C[x][y] = ∑ a[i][j], 其中,x-lowbit(x) + 1 <= i <= x , y-lowbit(y) + 1 <= j <= y.
3 例:举个例子来看看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[][]呢?
记:
B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...} 这是第一行的一维树状数组
B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...} 这是第二行的一维树状数组
B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...} 这是第三行的一维树状数组
B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...} 这是第四行的一维树状数组
那么:
C[1][1] = a11 , C[1][2] = a11+a12 , C[1][3] = a13 , C[1][4] = a11 + a12 + a13 + a14 , c[1][5]=a15.这是A[][]第一行的一维树状数组
C[2][1] = a11 + a21 , C[2][2] = a11 + a12 + a21 + a22 , C[2][3] = a13 + a23 , C[2][4] = a11 + a12 + a13 + a14 + a21 + a22 + a23 + a24 这是A[][]数组第一行与第二行相加后的树状数组
C[3][1] = a31 , C[3][2] = a31 + a32 , C[3][3] = a33 , C[3][4] = a31 + a32 + a33 + a34 , C[3][5] = a35 , C[3][6]=a35+a36,...这是A[][]第三行的一维树状数组
C[4][1] = a11 + a21 + a31 + a41 , C[4][2] = a11 + a12 + a21 + a22 + a31 + a32 + a41 + a42 ,这是A[][]数组第一行+第二行+第三行+第四行后的树状数组
3 树状数组的两类操作
1 单点更新,区间求和
1 一维树状数组,单点更新,区间求和
比如要更新点x ,x点的值加上val即调用add(x , val) , 求区间[1 , x]的和即为getSum(x)
int lowbit(int x){ return x&(-x); } int getSum(int x){ int sum = 0; while(x){ sum += treeNum[x]; x -= lowbit(x); } return sum; } void add(int x , int val){ while(x < MAXN){ treeNum[x] += val; x += lowbit(x); } }2 二维树状数组,单点更新,区间求和
比如要更新点(x , y) ,(x , y)点的值加上val即调用add(x , y , val) , 求矩形[1 , 1] - [x , y]的和即为getSum(x , y)
如上图求矩形的面积为getSum(x2 , y2)-getSum(x1-1,y2)-getSum(x2,y1-1)+getSum(x1-1 , y1-1)
int lowbit(int x){ return x&(-x); } int getSum(int x , int y){ int sum = 0; for(int i = x ; i > 0 ; i -= lowbit(i)) for(int j = y ; j > 0 ; j -= lowbit(j)) sum += treeNum[i][j]; return sum; } void add(int x , int y , int val){ for(int i = x ; i < MAXN ; i += lowbit(i)) for(int j = y ; j < MAXN ; j += lowbit(j)) treeNum[i][j] += val; }
2 区间更新,单点求和
1 一维树状数组
更改区间[x , y],区间[x , y]里面的每个数全部加上val , 查询点k的值
区间[x , y]加上val相当于点x加上val , 点y+1减去val,那么求k点的值就等于[1,k]的和
int lowbit(int x){ return x&(-x); } int getSum(int x){ int sum = 0; while(x){ sum += treeNum[x]; x -= lowbit(x); } return sum; } void add(int x , int val){ while(x < MAXN){ treeNum[x] += val; x += lowbit(x); } } void solve(){ // 把区间[x , y]每一点加上val add(x , val); add(y+1 , -val); // 计算点k的值 int num = getSum(k); }
2 二维树状数组
更改矩形[x1 , y1] - [x2 , y2],[x1 , y1] - [x2 , y2]里面的每个数全部加上val , 查询点(x , y)的值
矩形[x1 , y1] - [x2 , y2]里面的每一个元素加上val相当于点(x1 , y1)加上val , 点(x1 , y2+1)减去val,点(x2+1 , y1)减去val , 点(x2+1 , y2+1)加上val。那么求某个点(x , y)的值即求[1 , 1] - [x , y]的和
int lowbit(int x){ return x&(-x); } int getSum(int x , int y){ int sum = 0; for(int i = x ; i > 0 ; i -= lowbit(i)) for(int j = y ; j > 0 ; j -= lowbit(j)) sum += treeNum[i][j]; return sum; } void add(int x , int y , int val){ for(int i = x ; i < MAXN ; i += lowbit(i)) for(int j = y ; j < MAXN ; j += lowbit(j)) treeNum[i][j] += val; } void solve(){ // 矩形[x1 , y1]-[x2 , y2]每个点加上val add(x1 , y1 , val); add(x2+1 , y1 , -val); add(x1 , y2+1 , -val); add(x2+1 , y2+1 , val); // 求点(x , y)的值 int num = getSum(x , y); }
5 常用的技巧
假设初始化数组每个点的值为1,那么我们知道对于一维的树状数组来说,我们知道treeNum[i] = lowbit(i) . 对于二维树状数组来说treeNum[i][j] = lowbit(i)*lowbit(j)
void init(){ // 一维 memset(treeNum , 0 , sizeof(treeNum)); for(int i = 1 ; i < MAXN ; i++){ num[i] =1; treeNum[i] = lowbit(i); } // 二维 memset(treeNum , 0 , sizeof(treeNum)); for(int i = 1 ; i < MAXN ; i++){ for(int j = 1 ; j < MAXN ; j++){ num[i][j] = 1; treeNum[i][j] = lowbit(i)*lowbit(j); } } }Read full article from 初步搞懂树状数组