子序列求和可以转化为求由a[1]开始的序列a[1]……a[k]的和S。
而在树状数组中求S十分简单:
根据c[k]=a[k-2l+1]+ … +a[k] (l为k在二进制数中末尾0的个数)
我们从k1=k出发,按照
ki+1=ki-2lki(lki为ki在二进制数中末尾0的个数) 公式一
递推k2,k3,…,km (km+1=0)。由此得出
S=c[k1]+c[k2]+c[k3] + … + c[km]
例如,计算a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]
k1=7
k2= k1-2l1=7-20=6
k3= k2-2l2=6-21=4
k4= k3-2l3=4-22=0
即a[1]+a[2]+ a[3]+a[4]+ a[5]+a[6]+ a[7]=c[7]+c[6]+c[4]
推广到二维,同样也只需要计算由(1,1)开始的矩阵中的数字和,然后通过加减来计算子矩阵中的数字和。
小结
在上面的例子中我们可以看出采用树结构处理问题时,往往能够缩小搜索范围。这样在每次的查找过程中都能正确地选择由根开始的一条路径,不会出现无用的搜索
由于通常都是选取一条由根开始的路径,所以遍历树的快慢很大程度上取决于树的深度。如何降低树的高度就成了算法的关键。
相对于传统意义上的树,树状数组就其形式并不能称为“树”,但其核心思想却与树结构如出一辙。
<Marvolo原创,严禁转载>