树状数组

树状数组(Binary Indexed Tree Fenwick Tree)是一种用于维护数列前缀和、区间和以及支持单点更新的数据结构。它能够在 $O(\log n)$ 的时间复杂度内完成这些操作，比传统的前缀和算法更具有实用价值。树状数组也常常被用于解决数据结构中的某些问题，例如求逆序对、求数列中某一个数在排序后的排名等等。

基本思想

树状数组的核心思想是将原数列分解成若干个部分，对每一部分求出它们的和，并将这些和保存在一个数组中。数组中下标 $i$ 保存的是数列以第 $i$ 个元素结尾的、长度为 $lowbit(i)$ 的区间和（其中 $lowbit(i)$ 表示 $i$ 的最末尾的一个1所代表的数值）。这样，我们只需要利用这个数组就可以很方便地计算数列任意前缀和以及区间和了。

实现细节

初始化

构造树状数组需要两个步骤：

1. 定义一个数组 $tree$，用于保存树状数组的节点值。
2. 将原始输入数组中的每个数加入到树状数组中。

1
2
3
4
5
6
7
8
9

void init(int arr[], int tree[], int n) {
    for (int i = 1; i <= n; i++) {
        tree[i] += arr[i-1];
        int j = i + lowbit(i);
        if (j <= n) {
            tree[j] += tree[i];
        }
    }
}

lowbit操作

在树状数组的实现中，需要用到一个函数 $lowbit(i)$，它表示 $i$ 的最末尾的一个1所代表的数值。这个函数的实现方法比较简单，代码如下：

1
2
3

int lowbit(int x) {
    return x & -x;
}

单点查询

单点查询函数的实现比较简单，只需要将查询的位置不断地向前跳转，即反复减去当前位置的 lowbit 值，直到位置为0为止。代码如下：

1
2
3
4
5
6
7
8

int query(int tree[], int i) {
    int res = 0;
    while (i > 0) {
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}

区间查询

区间查询函数是树状数组最重要的操作。通过利用前缀和计算公式 $sum_{i,j} = sum_j - sum_{i-1}$，我们可以很容易地计算出数列 $[1,j]$ 和数列 $[1,i-1]$ 的前缀和，从而计算出数列 $[i,j]$ 的区间和。

1
2
3

int queryRange(int tree[], int l, int r) {
    return query(tree, r) - query(tree, l-1);
}

单点修改

单点修改操作需要将对应的节点值更新之后重新计算对应的每个节点的值，具体代码如下：

1
2
3
4
5
6

void update(int tree[], int i, int add, int n) {
    while (i <= n) {
        tree[i] += add;
        i += lowbit(i);
    }
}

总结

树状数组是一种非常实用的数据结构，它可以在 $O(\log n)$ 的时间复杂度内完成数列前缀和、区间和以及支持单点更新等操作。