The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

树状数组 By masterLuo

以前一直对树状数组这种结构并不感冒,因为觉得它能做到的事儿线段树也可以很好的完成。而且线段树应用更加灵活,可以说比树状数组的应用范围大很多。不过最近碰到两道题,都可以用树状数组这种结构很好的解决,代码非常精简单,特别是在二维应用的时候,用线段树非常麻烦,如果不是必要的话,不应当菜用线段树这种结构,而应用树状数组。稍微研究了下树状数组这种结构,写个总结吧。

树状数组它的每个元素并不像普通数组那样只保存自己的值,而是保存了从它开始前2^k个值的和(k为位置后面的二进制的0的个数)你可以看下图:

 

 

粉线色结点都只保持它自己的值,因为它们的二进制未尾0个数为0。绿色结点都保持了自己与它前一个值的和,蓝色结点保存了四个结点的值的和。棕色结点保存了8个结点的值的和。说了这么多,这种结构有什么用?它有什么优势呢?
它的主要优势就是可以快速求一段的和,即将求一段和的复杂度降到logN级别的,但是它增了修改一个元素的复杂度,使修改一个元素的复杂度也是logN级别的,不难知道,如果一个应用对于查询很多,每次查询都是一个区间的和,那么树状数组它的优势就很明显了。

问题一:怎么求一段元素的和?如果要求A[i –> j],显然如果能快速求A[1->i-1]和A[1->j]那么问题就解决了。怎么快速转化呢?
因为每个位置它都包含了一段的值,如果这一段值被加进来后,可以快速跳到下一个值,再求。如求A[1->6],那么知道6包括两个元素的和,下一次再求4,发现4包括四个元素的和,那么这两个和加进来就是结果。怎么快速求6的下一个元素呢?这就需要求出它二制后的0的个数的2的次幂,再与6作差即可。如6=(0000 0110)2,所以2^1=2 ,6-2=4,  4=(0000 0100), 所以2^2=4,4-4=0,结束。
int sum(int n) {
 int ret = 0;
 while(n > 0) {
  ret += ss[n];
  n -= lowbit(n);
 }
 return ret;
}
问题二:怎么快速求一个数二进制后面0的个数的2次幂?位运算。两种方法:x&(-x)或x&(x^(x-1)),它们都利用了位运算的特点,因为我们要求的就是从低位到到高位把遇到的第一个1保持不变,其余各位清0的一个操作!
inline int lowbit(int x) {
 return x & (x ^ (x - 1));
}
问题三:怎么快速修改一个元素的值?从上面的图可以看到,修改一个元素的值,所有包含它的值的元素都会被修改。同样,它的变化只与求和有一些不同,求和是往下走,而修改值是往上走!
void change(int i, int value) {
 while(i <= N) {
  ss[i] += value;
  i += lowbit(i);
 }
}
 
变形应用:上面应用都是修改一个元素的值,求一段元素的和。那么它还可以进行什么样的操作呢?修改一段元素都增加或减少一个定值,查询一个元素的值!同样是logN级别的。问题是这样转化的:如果把a-b区间内的元素都要增加v,那么实际就可以把a元素增加v, b+1减少v,那么查询a元素的值呢?就是求sum(1->a)所有元素的和就行了!这样操作是否是正确的?正确性很容易证明,自己在纸上画画就会明白了。

二维树状数组与一维的情况类似。它也可以进行一段的操作,变形应用也可以。要注意的问题就是修改的值会变成四个角。


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/MasterLuo/archive/2009/12/25/5073784.aspx

posted on 2010-03-29 16:51 abilitytao 阅读(202) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理