首页 > 笔记 > 树状数组总结

树状数组总结

一种简单,常数小,高效的小巧数据结构。有着迷人的性质。。。


假如我们有树状数组a[1..n],那么查询a[1]+…+a[n]的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别。

来观察这个图:

images

令结点编号为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

这里有一个有趣的性质:

设节点编号为x,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,

所以很明显:Cn = A(n – 2^k + 1) + … + An

 

2^k有一种简单的求法:利用补码的性质

 

当想要查询一个SUM(n)(求a[n]的和),可以依据如下算法即可:

step1: 令sum = 0,转第二步;
step2: 假如n <= 0,算法结束,返回sum值,否则sum = sum + Cn,转第三步;
step3:    令n = n – lowbit(n),转第二步。

可以看出,这个算法就是将这一个个区间的和全部加起来,为什么是效率是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的过程。

它的优点就是非常简单

例题


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×