46 · 树状数组

第 18 节的前缀和有个硬伤：改一个数，后面所有 s[i] 全部作废，重建一次 O(n)。而比赛中“单点修改 + 区间询问”的组合出现得极频繁——数据在变，问题却还是那一个。这一节解决的就是这个矛盾：让改一个点和查一段和都只要 O(log n)，代价是 12 行代码。

前缀和的思路是“把 a[1..i] 压成一个数”，一旦中间某个值变了，这个压缩就废了。树状数组换了一种压法：按 i 的二进制位来压，每个二进制位对应一段。于是改一个点只会动到 O(log n) 段，求一个前缀和也只需要拼 O(log n) 段。以 n = 8 为例：t[1]=a[1]，t[2]=a[1..2]，t[3]=a[3]，t[4]=a[1..4]，t[6]=a[5..6]，t[8]=a[1..8]。那么 sum(6) = t[6] + t[4] = a[5..6] + a[1..4]，两段拼完，一步没多。

先看清两块骨头：lowbit（怎么算管辖长度）和三个函数的骨架（怎么跳下标）。这两块想通了，后面四种用法只是换一下“下标代表什么”。

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

int main() {
    for (int x = 1; x <= 10; ++x)
        cout << x << " -> " << (x & -x) << "\n";
    // 1->1  2->2  3->1  4->4  5->1  6->2  7->1  8->8  9->1  10->2
    return 0;
}

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

int n = 8, t[10];                                 // t[i] 管 lowbit(i) 个位置
int a[9] = {0, 3, 1, 4, 1, 5, 9, 2, 6};

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

void add(int i, int v) {
    for (; i <= n; i += lowbit(i)) t[i] += v;      // 所有管着 i 的节点都要改
}

int sum(int i) {
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += t[i];       // 一路往左上跳，把大段拼起来
    return s;
}

int main() {
    for (int i = 1; i <= n; ++i) add(i, a[i]);     // 建树：n 次单点加
    cout << sum(5) << "\n";                        // 3+1+4+1+5 = 14
    cout << sum(7) - sum(2) << "\n";               // a[3..7] = 4+1+5+9+2 = 21
    add(3, 10);                                    // a[3] 从 4 变成 14
    cout << sum(5) << "\n";                        // 24
    return 0;
}

先拿洛谷的模板题把它跑起来。这道题把“单点修改”和“区间求和”放在一起，正好对上树状数组的两个函数。

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

const int N = 500005;
int n, m;
long long t[N];                       // t[i] 管 a[i-lowbit(i)+1 .. i] 这一段

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

void add(int i, long long v) {
    for (; i <= n; i += lowbit(i))    // 往上跳：把所有"管着 i"的节点都改掉
        t[i] += v;
}

long long sum(int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i))     // 往左上跳：把几个大段拼成前缀
        s += t[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {    // 建树：读一个数就当成一次单点加
        int x;
        cin >> x;
        add(i, x);
    }

    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) add(x, y);                    // 第 x 个数加 y
        else cout << sum(y) - sum(x - 1) << "\n";  // 区间和 = 两个前缀之差
    }
    return 0;
}

第二种用法只改一件事：让树状数组去管差分数组。于是“区间加”变成两次单点加，“单点查”变成一个前缀和——正好是 add 和 sum。

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

const int N = 500005;
int n, m;
long long a[N], t[N];                 // t 维护的是差分数组 d

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

void add(int i, long long v) {
    for (; i <= n; i += lowbit(i)) t[i] += v;
}

long long sum(int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i)) s += t[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        add(i, a[i] - a[i - 1]);      // 差分 d[i] 直接进树状数组
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long k;
            cin >> l >> r >> k;
            add(l, k);                // 从 l 起，后面都多 k
            add(r + 1, -k);           // 从 r+1 起还回去（r=n 时这行自动空转）
        } else {
            int x;
            cin >> x;
            cout << sum(x) << "\n";   // 原数组第 x 个值 = 差分的前缀和
        }
    }
    return 0;
}

第三种用法最反直觉：让树状数组的下标不是位置，而是数值本身。这时 t 存的是“某个值出现了几次”，前缀和 sum(v) 就是“值 ≤ v 的元素有多少个”。一旦有了这个能力，逆序对就变成了一行加法。

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

const int N = 500005;
int n, a[N], t[N];                    // t 的下标是"值"，不是"位置"

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

void add(int i, int v) {
    for (; i <= n; i += lowbit(i)) t[i] += v;
}

int sum(int i) {
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += t[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];   // 保证 1 <= a[i] <= n

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (i - 1) - sum(a[i]);   // 前面 i-1 个里，≤ a[i] 的有 sum(a[i]) 个
        add(a[i], 1);                 // 再把 a[i] 记进去：这个值多出现了一次
    }
    cout << ans << "\n";
    return 0;
}

第四种用法把树状数组当成一棵“二叉搜索树”：在 O(log n) 内找到最小的 p 使 sum(p) ≥ k。答案如果靠二分，就是 O(log²n)，而树状数组自己就能二分。

原理：树状数组的节点正好构成一棵“按二进制分段”的树。从 p = 0 出发，从大到小试 step = 2²⁰, 2¹⁹, …, 1：如果 t[p + step] < k，说明前 p+step 个数的和还不够 k，答案在右边，就跳过去，并把 k 减去这一段的和；否则停在原地。走完 log n 步，p 就是“最后一个前缀和 < k 的位置”，答案是 p+1。

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

int n = 8, t[10];                       // 用 t 记"每个位置出现了几次"

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

int kth(int k) {                        // 最小的 p，使 sum(p) >= k
    int p = 0;
    for (int step = 1 << 20; step; step >>= 1)      // 起点取一个不小于 n 的 2 的幂
        if (p + step <= n && t[p + step] < k) {     // 这一段还不够，就整段吃掉
            p += step;
            k -= t[p];                              // t[p] 正是刚吃掉那一段的和
        }
    return p + 1;
}

int main() {
    add(2, 1); add(5, 2); add(7, 1);                // 位置 2 一个、位置 5 两个、位置 7 一个
    for (int k = 1; k <= 4; ++k) cout << kth(k) << " ";   // 2 5 5 7
    cout << "\n";
    return 0;
}

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

const int N = 500005;
int n, a[N], b[N], t[N];              // t 的下标是"名次"

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

void add(int i) {                     // 名次 i 的出现次数 +1
    for (; i <= n; i += lowbit(i)) ++t[i];
}

int sum(int i) {                      // 名次 <= i 的元素出现了几个
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += t[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; b[i] = a[i]; }

    sort(b + 1, b + n + 1);                          // 离散化：排序
    int tot = unique(b + 1, b + n + 1) - b - 1;      // 去重后值域缩到 1..tot

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int rk = lower_bound(b + 1, b + tot + 1, a[i]) - b;   // a[i] 的名次
        ans += (i - 1) - sum(rk);    // 前面 ≤ 它的有 sum(rk) 个，其余都严格大于它
        add(rk);                     // 再把它的名次记进去
    }
    cout << ans << "\n";
    return 0;
}