查看“︁树状数组”︁的源代码

{{NoteTA|G1=IT}}
{{Infobox data structure
|name          = 树状数组
|image         = 16-node Fenwick tree.svg
|type          = [[二元樹]]
|invented_by   = 鮑里斯·里亞布科
|invented_year = 1989年
|space_avg     = <math>O(n)</math>
|space_worst   = <math>O(n)</math>
|search_avg    = <math>O(\log n)</math>
|search_worst  = <math>O(\log n)</math>
|insert_avg    = <math>O(\log n)</math>
|insert_worst  = <math>O(\log n)</math>
}}
[[File:BITDemo.gif|200px|thumb|根据数组[1, 2, 3, 4, 5]来创建对应的树状数组]]
'''树状数组'''或'''二元索引树'''（{{lang-en|Binary Indexed Tree}}，簡稱 '''BIT'''），又以其发明者命名为'''芬威克樹'''（{{lang-en|Fenwick tree}}），最早由彼得·M·芬威克（Peter M. Fenwick）于1994年以《A New Data Structure for Cumulative Frequency Tables》<ref>{{cite journal |author=Peter M. Fenwick |title=A new data structure for cumulative frequency tables |journal=Software: Practice and Experience |volume=24 |issue=3 |year=1994 |pages=327–336 |doi=10.1002/spe.4380240306 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917 |access-date=2015-10-24 |archive-date=2021-02-25 |archive-url=https://web.archive.org/web/20210225061748/https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917 |dead-url=no }}</ref>为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩裡的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。它可以以<math>O(\log n)</math>的时间得到任意前缀和<math>\sum_{i=1}^j A[i], 1 <= j <= N</math>，并同时支持在<math>O(\log n)</math>时间内支持动态单点值的修改。空间复杂度<math>O(n)</math>。

== 结构起源 ==
按照彼得·M·芬威克的说法，正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和具有极其相似的方式。一方面，子序列的个数是其二进制表示中1的个数，另一方面，子序列代表的f[i]的个数也是2的幂。<ref name="bit">{{Cite web |url=http://duanple.blog.163.com/blog/static/7097176720081131113145832/ |title=Binary indexed tree-树状数组 |access-date=2012-05-09 |archive-date=2019-08-23 |archive-url=https://web.archive.org/web/20190823005432/http://duanple.blog.163.com/blog/static/7097176720081131113145832/ |dead-url=no }}</ref><ref>{{Cite web |url=http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees |title=Binary Indexed Trees |access-date=2012-05-09 |archive-date=2016-06-16 |archive-url=https://web.archive.org/web/20160616210119/https://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees |dead-url=no }}</ref><ref>{{Cite web |url=http://hawstein.com/posts/binary-indexed-trees.html |title=TopCoder树状数组教程的译文 |access-date=2012-11-18 |archive-url=https://web.archive.org/web/20130410002003/http://hawstein.com/posts/binary-indexed-trees.html |archive-date=2013-04-10 |dead-url=yes }}</ref>

== 基本操作 ==
=== 预备函数 ===
定义一个<code>lowbit</code>函数，返回参数转为二进制后,最后一个1的位置所代表的数值。

例如，<code>lowbit(34)</code>的返回值将是2；而<code>lowbit(12)</code>返回4；<code>lowbit(8)</code>返回8。

将34转为二进制为(0010 0010)<sub>2</sub>。这里的“最后一个1”指的是从<math>2^0</math>位往前数，见到的第一个1，也就是<math>2^1</math>位上的1。

程序上，<code>(~i + 1) & i</code>表明了最后一位1的值。

仍然以34为例，~(0010 0010)的结果是1101 1101（221），加1后为1101 1110（222），把0010 0010与1101 1110作AND，得0000 0010（2）。

<code>lowbit</code>的一个简便求法:（C++）
<syntaxhighlight lang=cpp>
int lowbit(int x)
{
    return x&(-x);
}
</syntaxhighlight>

=== 新建 ===
定义一个数组 BIT，用以维护<math>A</math>的前缀和，则：<math>BIT_i=\sum_{j=i-lowbit(i)+1}^{i}A_j</math>

具体能用以下方式实现：（C++）
<syntaxhighlight lang="cpp">
void build()
{ 
    for (int i = 1; i <= MAX_N; i++)
    {
        BIT[i] += A[i - 1];
        int j = i + lowbit(i);
        if (j <= MAX_N) { 
            BIT[j] += BIT[i];
        }
    }
}
//此地方採用類似動態規劃的方式初始化
</syntaxhighlight>

=== 修改 ===
假设现在要将<math>A[i]</math>的值增加delta，

那么，需要将<math>BIT[i]</math>覆盖的区间包含<math>A[i]</math>的值都加上delta，

这个过程可以写成递归，或者普通的循环。

需要计算的次数与数据规模N的二进制位数有关，即这部分的时间复杂度是<math>O(\log{N})</math>。

修改函数的C++写法：
<syntaxhighlight lang=cpp>
void edit(int i, int delta)
{
    for (int j = i; j <= MAX_N; j += lowbit(j))
        BIT[j] += delta;
}
</syntaxhighlight>

=== 求和 ===
假设我们需要计算<math>\sum_{i=1}^{k}A_i</math>的值。

#首先，将ans初始化为0，将i初始化为k。
#将ans的值加上<code>BIT[i]</code>。
#将i的值减去<code>lowbit(i)</code>。
#重复步骤2～3，直到i的值变为0。

求和函数的C/C++写法：
<syntaxhighlight lang=cpp>
int sum (int k)
{
    int ans = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}
</syntaxhighlight>

=== 时空复杂度 ===
* 初始化复杂度最优为：<math>O(N)</math>
* 单次询问复杂度：<math>O(\log N)</math>，其中N为数组大小
* 单次修改复杂度：<math>O(\log N)</math>，其中N为数组大小
* 空间复杂度：<math>O(N)</math>
=== 扩展 ===
树状数组可以通过维护差分数组来处理区间修改和单点查询。具体地，当我们在 <math>[l,r]</math> 增加 <math>d</math> 时只需执行 <code>edit(l,d)</code> 和 <code>edit(r+1,-d)</code> 。查询则与单点修改区间查询相似。
== 应用 ==
=== 求逆序对数<ref>{{Cite web |url=http://blog.csdn.net/cattycat/article/details/5640838 |title=存档副本 |access-date=2012-05-11 |archive-date=2019-11-30 |archive-url=https://web.archive.org/web/20191130220809/https://blog.csdn.net/cattycat/article/details/5640838 |dead-url=no }}</ref> ===
[[逆序数|逆序对数]]是一个数列中在它前面有比它大的个数。如4312的逆序对数是0+1+2+2=5。

可以先把数列中的数按大小顺序转化成<math>1</math>到<math>n</math>的整数（離散化），使得原数列成为一个<math>1, 2, ..., n</math>的排列<math>P</math>，创建一个树状数组，用来记录这样一个数组<math>A</math>（下标从1算起）的前缀和：若排列中的数<math>i</math>当前已经出现，则<math>A[i]</math>的值为<math>1</math>，否则为<math>0</math>。初始时数组<math>A</math>的值均为<math>0</math>，从排列中的最後一个数开始遍历，每次在树状数组中查询有多少个数小于当前的数<math>P[j]</math>（即用树状数组查询数组<math>A</math>目前<math>P[j]-1</math>个数的前缀和）并加入计数器，之后对树状数组执行修改数组<math>A</math>第<math>P[j]</math>个数值加<math>1</math>的操作。

== 参考文献 ==
{{Reflist|2}}

{{-}}
{{计算机科学中的树}}

[[Category:树结构]]
[[Category:数组]]