您所在位置：主题：树状数组（Binary Indexed Trees）
Sedgewick
[专家分：0] 发布于 2008-03-20 23:49:00
最近看到一篇介绍树状数组的文章，写得很通俗。
[color=C0C0C0][url]http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees[/url][/color]
决定总结一下：
1.BIT主要用来求一段连续数字的和。
BIT最初是为了解决数据压缩而提出的。若数组A[0..n-1]相邻元素相差不大，则可采用如下压缩：
C[0] = A[0]
C[i] = A[i]-A[i-1] （i≥1）
还原：
A[i] = C[0] + C[1] + …… + C[i-1] + C[i]
2.它是线段树的一种变型，但较之更易编码，使用线性空间，其上的操作可以在对数时间内完成。
BIT采用了一种与MTF（move to front）、HEAP、SPLAY TREE完全不同的方式（它们是将最常访问的元素提前至最容易访问到的位置），BIT通过巧妙的挑选某些元素形成各种组合。（这让我想起了找零钱问题）
3.很容易就可以扩展到高维数组。
4.可以完成的操作：
■计算连续和（Read cumulative frequency）
■更新某个元素的值（Change frequency at some position and update tree）
■读出单个元素的值（Read the actual frequency at a position）
■按比例缩小整个数组（Scaling the entire tree by a constant factor）
■找出等于某个给定值那一段的下标（Find index with given cumulative frequency）
[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]
[color=C0C0C0][url]http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees[/url][/color]
决定总结一下：
1.BIT主要用来求一段连续数字的和。
BIT最初是为了解决数据压缩而提出的。若数组A[0..n-1]相邻元素相差不大，则可采用如下压缩：
C[0] = A[0]
C[i] = A[i]-A[i-1] （i≥1）
还原：
A[i] = C[0] + C[1] + …… + C[i-1] + C[i]
2.它是线段树的一种变型，但较之更易编码，使用线性空间，其上的操作可以在对数时间内完成。
BIT采用了一种与MTF（move to front）、HEAP、SPLAY TREE完全不同的方式（它们是将最常访问的元素提前至最容易访问到的位置），BIT通过巧妙的挑选某些元素形成各种组合。（这让我想起了找零钱问题）
3.很容易就可以扩展到高维数组。
4.可以完成的操作：
■计算连续和（Read cumulative frequency）
■更新某个元素的值（Change frequency at some position and update tree）
■读出单个元素的值（Read the actual frequency at a position）
■按比例缩小整个数组（Scaling the entire tree by a constant factor）
■找出等于某个给定值那一段的下标（Find index with given cumulative frequency）
[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]
