5.11.3 树状数组 *

在前面「前缀与差分」的章节中，我们学习了利用数组，把每次区间操作的时间复杂度将至 #card=math&code=O%281%29&id=U1jyf) 的方法。然而，这些方法直到做完所有更新操作，还原出原数组后，才能在原数组上查询。树状数组专为解决区间改查问题而生。

5.11.3.1 单点修改，区间查询

树形结构使得这一数据结构可以在对数阶的时间内搜索到任意节点。进一步理解树状数组，我们提供了参考资料的推荐，它们讲解了普通树状数组后，也会讲解更为复杂的应用。你可以先学习本章节列出的部分。

// 普通树状数组
#include <bits/stdc++.h>
using namespace std;
const int N = 10004;
int c[N];
int n;
int lowbit(int x) {
    return x & -x;
}
void update(int x, int u) {
    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += u;
    }
}
// sum[1, x]
void query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}
// sum[l, r]
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}
int main() {
    return 0;
}

操作时间复杂度：#card=math&code=O%28%5Clog%20n%29&id=CoHBK)

参考：

树状数组详解

树状数组

5.11.3.2 区间修改，区间查询

我们知道，差分数组支持用单点修改表示区间修改。差分树状数组就是在普通树状数组上应用了差分的原理。这一模板需要两个数组。

// 差分树状数组
#include <bits/stdc++.h>
using namespace std;
const int N = 10004;
int ca[N];  // ca[i] = a[i] - a[i - 1]
int cb[N];  // cb[i] = ca[i] * (i - 1)
int n;
int lowbit(int x) {
    return x & -x;
}
void update(int x, int u) {
    for (int i = x; i <= n; i += lowbit(i)) {
        ca[i] += u;
        cb[i] += u * x;     // 如果这里写成 cb[i] += u * (x - 1)
    }
}
// sum[1, x]
int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += (x + 1) * ca[i] - cb[i];        // 这里就写成 res += x * ..
    }
    return res;
}
// sum[l, r]
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}
int main() {
    return 0;
}

5.11.3.3 树状数组求逆序对

例题：牛客 15163. 逆序数

在前面，我们使用了归并排序求逆序对，树状数组也可以很清晰地解决求逆序对问题。它的思路是，每插入一个数时，统计树状数组中大于它的数，加入答案。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100004;
int c[N];
int n;
int lowbit(int x) {
    return x & -x;
}
void update(int x, int u) {
    for (; x <= n; x += lowbit(x)) {
        c[x] += u;
    }
}
int query(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x)) {
        res += c[x];
    }
    return res;
}
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}
int main() {
    cin >> n;
    long long ans = 0;
    for (int i=0; i<n; ++i) {
        int x;
        cin >> x;
        ans += rangeQuery(x + 1, n);
        update(x, 1);
    }
    cout << ans << endl;
    return 0;
}

在上面的代码中，模板在 for 循环中省略了循环变量 i ，这也是正确的。也有人在这里写成 while 循环，这与个人习惯有关。你可以根据自己的情况，修改出最符合自己习惯和理解的模板。

然而这一求逆序对方法的弊端也很显然——那就是额外空间。归并排序只需要数的个数数量的额外空间；而树状数组需要数的范围数量的额外空间。在数的范围大、分布稀疏时，需要「离散化」操作，把大数映射到小数。

推荐阅读：树状数组和逆序对