树状数组

原理

（树状数组下标从1开始）假设有原数组arr[1...n]，可以创建一个与之对应的树状数组tr[1...n]，tr[x]存储区间arr[x-lowbit(x)+1 ... x]中所有数之和，可以发现的是该区间的长度是lowbit(x)。

树状数组完成两种操作：

1、区间查询：查询序列[1...x]区间的区间和，即x位置的前缀和

int ask(int x) {
    int r = 0;
    for (; x >= 1; x -= x & -x)
        r += tr[x];
    return r;
}

2、单点更新：把序列x位置的数加上一个值v

void add(int x, int v) {
    for (; x <= n; x += x & -x)
        tr[x] += v;
}

优势

树状数组区间查询和单点更新的时间复杂度都是$O(logn)$；

原数组单点更新时间复杂度是$O(1)$，区间查询的时间复杂度是$O(n)$；

前缀和数组单点更新时间复杂度是$O(n)$，区间查询的时间复杂度是$O(1)$；

如果算法中区间查询和单点更新的操作数量都达到了$O(n)$级别，那么使用树状数组算法整体复杂度为$O(nlogn)$，而使用原数组和前缀和数组时间复杂度都是$O(n^2)$。

应用

可以用来计算arr[i]左边/右边多少数小于/大于当前数：维护一个数组元素的计数数组，记录每个数左边/右边的数组元素各有多少个，这个计数数组用树状数组的方式实现，然后通过树状数组计算计数数组的前缀和得到结果。

如果是计算arr[i]左边有多少数小于/大于当前数，则需要从左向右遍历：

for (int i = 1; i <= n; i++) {
    ask(arr[i]-1); // 得到左边有多少数小于当前数
    ask(arr[i]); // 得到左边有多少数小于等于当前数

    ask(n) - ask(arr[i]); // 得到左边有多少数大于当前数
    ask(n) - ask(arr[i]+1); // 得到左边有多少数大于等于当前数

    add(arr[i], 1); // 更新树状数组，给arr[i]的计数加一
}

如果是计算arr[i]右边有多少数小于/大于当前数，则需要从右向左遍历：

for (int i = n; i >= 1; i--) {
    ask(arr[i]-1); // 得到右边有多少数小于当前数
    ask(arr[i]); // 得到右边有多少数小于等于当前数

    ask(n) - ask(arr[i]); // 得到右边有多少数大于当前数
    ask(n) - ask(arr[i]+1); // 得到右边有多少数大于等于当前数

    add(arr[i], 1); // 更新树状数组，给arr[i]的计数加一
}

进而可以用来计算逆序对数。

数组arr[1...n]中数的范围可能比较大，计数数组（树状数组）用其中的数直接作为下标可能不太合适，通常需要离散化。

---