树状数组是一个查询和修改复杂度都为log(n)的数据结构,假设数组a[1...n],那么查询a[1] + …… + a[i] 的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别。
来观察一下这个图:
令这棵树的结点编号为C1,C2……Cn。令每个结点的值为这棵树的值的总和,那么容易发现:
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
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
……
C2^n=a1+a2+….+a2^n
对于序列a,我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t],k为t在二进制下末尾0的个数。
K的计算可以这样:
2^k=t and (t xor (t-1)) 或者 t and (- t)
以6为例
(6)10=(0110)2
xor 6-1=(5)10=(0101)2
(0011)2
and (6)10=(0110)2
(0010)2
这里有一个有趣的性质:
设节点编号为x,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,所以很明显:
Cn = A(n – 2^k + 1) + …… + An
算这个2^k有一个快捷的办法,定义一个函数如下即可:
int lowbit(int x)
{
return x & (x ^ (x – 1));
// return x & (-x);
}
当想要查询一个SUM(n)时,可以依据如下算法即可:
step1: 令sum = 0,转第二步;
step2: 假如n <= 0,算法结束,返回sum值,否则sum = sum + Cn,转第三步;
step3: 令n = n – lowbit(n),转第二步。
分析: 设原数组为a[1..N],树状数组为c[1..N],其中c[k] = a[k-(2^t)+1] + ... + a[k]。比如c[6] = c[5] + c[6]。也就是说,把k表示成二进制1***10000,那么c[k]就是1***00001 + 1***00010 + ... + 1***10000这一段数的和。设一个函数lowestbit(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]。当数组中某元素发生变化时,需要改动的c值是c[k],c[k+lowestbit(k)], c[k+lowestbit(k)+lowestbit(k+lowestbit(k))] ... 。
这个算法就是将这一个个区间的和全部加起来,为什么是效率是log(n)的呢?以下给出证明:
n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1,所以查询效率是log(n)的。
那么修改呢,修改一个节点,必须修改其所有祖先,最坏情况下为修改第一个元素,最多有log(n)的祖先。所以修改算法如下(给某个结点i加上x):
step1: 当i > n时,算法结束,否则转第二步;
step2: Ci = Ci + x, i = i + lowbit(i)转第一步。
i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。
数列操作
给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.
【算法分析】
如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上,所以这样做会超时,但是如果用线段树的话,还是很不错的!
C数组就是树状数组,a数组是原数组;
对于序列a,我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t],k为t在二进制下末尾0的个数。
代码如下:
#include <stdio.h> #include <string.h> #include <conio.h> int C[10]; int n = 10;
/*求2^k*/ int lowbit(int t) { return t & (-t); }
/*求1--end的和*/ int sum(int end) { int sum = 0; while(end > 0) { sum += C[end]; end
阅读(959) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~
chinaunix网友2009-12-10 12:06:29
貌似没有copy完整.
是参加了比赛,我也没奖,悲剧啊。。。
chinaunix网友2009-11-29 12:13:43
是不是没有写完啊?你也参加了湖南省程序设计大赛啊?我参加了,不过没拿奖啊!!可惜啊!!
|