树状数组

树状数组 又名 二叉索引树（Binary Indexed Tree，BIT）：多用于高效计算数列的 前缀和，区间和，可以用于 在线查询。

最早由 Peter M. Fenwick 于 1994 年提出，又以其发明者命名为Fenwick树

lowbit 运算

lowbit(x) = x & (-x)：返回得到 x 转化为二进制后，最后一个 1 的位置所代表的值

也可以理解为能整除 x 的最大 2 的幂值
可以直接使用宏定义：#define lowbit(x) ((x) & (-x))

定义

BIT 其实仍然是一个数组，并且与前缀和数组类似，都是用来记录和，但是它存放的是：在 i 号位之前（包括 i） lowbit(i) 个整数之和

以下有如下数组定义

原始数组 A：输入的数组
树状数组 C：C[i] 覆盖的长度是 lowbit(i)（2 的幂次）
- 树状数组的下标必须从 1 开始

树状数组的定义如下：很像一棵树

基本函数

BIT 由两个基本函数：

getSum(x)：返回前 x 个数之和，即 A[1] + ... + A[x]
update(x, v)：将第 x 个数加上 v，即 A[x] += v

getSum(x)

记 SUM(1, x) = A[1] + ... + A[x]，由于 C[x] 覆盖的长度是 lowbit(x)，因此：

C[x] = A[x - lowbit(x) + 1] +...+ A[x]

马上可以得到：SUM(1, x) = SUM(1, x - lowbit(x)) + C[x]，因此 getSum(x) 函数如下：

int getSum(int x) {
	int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) { // i > 0，下标从 1 开始
        sum += c[i]; // 累加 c[i]，然后问题缩小为 SUM(1, x - lowbit(x))
    }
    return sum;
}

因为 i -= lowbit(i) 是将 i 最右的 1 置 0 的过程，因此 时间复杂度 $O(logn)$

如果要求 [x, y] 的区间和，可以转化为 getSum(y) - getSum(x - 1)

update(x, v)

如果是普通的前缀和，update 操作需要的时间复杂度为 $O(n)$ 。对于 BIT 而言，并不是所有的数组都覆盖 x，因此只需要更新覆盖到 x 的 C[] 即可。

因此从 C[x] 开始更新，我们需要寻找 距离当前 C[x] 最近且能覆盖 C[x] 的 C[y]。

根据下图我们可以发现：离 C[9] 最近且覆盖的是 C[10]，然后是 C[12]，注意到二进制从 1001 → 1010 → 1100，每次将最低位的 1 进位，因此我们可以得到 y = x + lowbit(x)

所以 update(x, v) 的函数如下：

void update(int x, int v) {
	for (int i = x; i <= MAXN; i += lowbit(i)) {
        c[i] += v;
    }
}

因为 i += lowbit(i) 是将 i 最右的 1 进位的过程，因此 时间复杂度 $O(logn)$

经典应用

树状数组最经典的应用：给定一个有 N 个正整数的序列 A（N <= 10^5，A[i] <= 10^5），对序列中每个数，求出序列中它左边比它小的数的个数。

我们可以使用一个 hash 数组，hash[x] 记录整数 x 当前出现的次数。

从头开始遍历 A 数组，假设当前访问的是A[i]，则 hash[A[i]]++，然后 A[i] 左边比它小的数的个数就是：hash[1] + hash[2] + ... + hash[A[i] - 1]。

显然，则两个操作就是 update(A[i], 1) 和 getSum(A[i] - 1)。我们在操作中用树状数组代替 hash 数组。

for (int i = 0; i < n; i++) {
    update(A[i], 1);
    printf("%d\n", getSum(A[i] - 1));
}

如果要统计 A[i] 左边比它大的元素呢？等价与计算hash[A[i] + 1] + ... + hash[N]，即 getSum(N) - getSum(A[i])

如果要统计右边的话，就是镜像问题了，从右往左遍历元素数组即可。

离散化

如果 A[i] <= 10^5 不成立（A[i] <= 10^9），即树状数组无法开得那么大，这里就要用到一种技巧：离散化。

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

与”给定 N 个学生的成绩然后排名类似“，所要做的事情就是将 A[i] 与 1~N 对应起来。

一般来说，可以设置一个临时的结构体数组，用以存放输入序列的值以及原始序号，而在输入完毕后将其按值 val 排序，然后再按”计算排名“的方式将”排名“按原始数组序号 pos 存入一个新的数组即可。

#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) ((x) & (-x))
const int MAXN = 100010;

struct Node {
    int val;
    int pos;

    friend bool operator< (Node a, Node b) {
        return a.val < b.val;
    }
} temp[MAXN];
int A[MAXN];
int c[MAXN];

int getSum(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        sum += c[i];
    }
    return sum;
}

void update(int x, int v) {
    for (int i = x; i <= MAXN; i += lowbit(i)) {
        c[i] += v;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &temp[i].val);
        temp[i].pos = i;
    }
    sort(temp, temp + n);
    for (int i = 0; i < n; ++i) {
        if (i == 0 || temp[i].val != temp[i - 1].val) {
            A[temp[i].pos] = i + 1;
        } else {
            A[temp[i].pos] = A[temp[i - 1].pos];
        }
    }
    for (int i = 0; i < n; ++i) {
        update(A[i], 1);
        printf("%d\n", getSum(A[i] - 1));
    }

    return 0;
}

离散化通常只适用于离线查询，必须知道所有出现的元素才可以离散化。

但是，我们可以先将所有的操作数都记录下来，然后对其出现过的数据离散化，再按记录下的顺序进行”在线“查询

扩展

序列第 K 大：就是要找出满足 getSum(i) >= K 最小的 i，使用二分法：

int findKthElement(int k) {
	int l = 1, r = MAXN, mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (getSum(mid) >= k) r = mid;
        else l = mid + 1;
    }
    return l;
}

扩展数组 A[] 为二维数组 A[][]：将树状数组扩展为二维，然后将 update、getSum 使用两层 for 循环即可

int c[MAXN][MAXN];

int getSum(int x, int y) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(y)) {
            sum += c[i][j];
        }
    }
    return sum;
}

void update(int x, int y, int v) {
    for (int i = x; i <= MAXN; i += lowbit(i)) {
        for (int j = y; j <= MAXN; j += lowbit(j)) {
            c[i][j] += v;
        }
    }
}

区间更新、单点查询

以上的树状数组都是再进行 单点更新、区间查询，如果要反过来该怎么做？此处就要修改以下树状数组的定义了：C[i] 长度不变，但是不再表示这段区间的元素之和，而是这段区间每个数加了多少。

因此 A[i] 的值就是覆盖它的若干个 C[] 的值，因此函数与原本的 update 十分相似：

// 返回 A[i] 的值
int getSum(int x) {
	int sum = 0;
    for (int i = x; i <= MAXN; i += lowbit(i)) {
        sum += c[i];
    }
    return sum
}

而 update 与原本的 getSum 相似：

// 把前 x 个数加上 v
void update(int x, int v) {
    for (int i = x; i > 0; i -= lowbit(i)) {
        c[i] += v
    }
}