一、课上练习

编程练习

1. 树状数组 1：L49936

二、知识总结

✨ 核心思想

树状数组（Binary Indexed Tree，BIT，又称 Fenwick Tree）是一种支持单点修改和前缀查询的高效数据结构。它利用二进制分组的思想，将前缀和拆分成 O(log n) 个区间的和，实现 O(log n) 的修改和查询。

树状数组的核心在于 lowbit 运算：lowbit(x) = x & (-x)，它提取 x 的二进制最低位的 1 所代表的值。

✨ 算法原理

lowbit 运算

对于正整数 x，lowbit(x) 等于 x 的二进制表示中最低位 1 所对应的值。

例如：

• lowbit(6) = lowbit(110₂) = 2（最低位 1 在第 2 位）
• lowbit(12) = lowbit(1100₂) = 4（最低位 1 在第 3 位）

树状数组结构

定义 c[x] 管理的区间为 [x - lowbit(x) + 1, x]，长度恰好为 lowbit(x)。

树状数组中节点的父子关系：

• x 的父节点：x + lowbit(x)
• x 管理的前一个区间：x - lowbit(x)

单点修改

修改 a[x] 时，需要更新所有包含位置 x 的节点。从 x 出发，不断加 lowbit 直到超过 n。

前缀查询

查询前缀和 a[1] + a[2] + ... + a[x] 时，从 x 出发，不断减 lowbit 直到 0，累加经过的所有 c[x]。

区间查询

利用前缀和相减：sum(l, r) = query(r) - query(l - 1)。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 500005;
5
6int c[MAXN]; // 树状数组
7int n, m;
8
9// 获取x的最低位1
10int lowbit(int x) {
11    return x & (-x);
12}
13
14// 单点修改：将a[x]增加val
15void update(int x, int val) {
16    for (; x <= n; x += lowbit(x)) {
17        c[x] += val;
18    }
19}
20
21// 前缀查询：返回a[1]+a[2]+...+a[x]
22int query(int x) {
23    int sum = 0;
24    for (; x > 0; x -= lowbit(x)) {
25        sum += c[x];
26    }
27    return sum;
28}
29
30// 区间查询：返回a[l]+a[l+1]+...+a[r]
31int rangeQuery(int l, int r) {
32    return query(r) - query(l - 1);
33}
34
35int main() {
36    ios::sync_with_stdio(false);
37    cin.tie(nullptr);
38
39    cin >> n >> m;
40    for (int i = 1; i <= n; i++) {
41        int x;
42        cin >> x;
43        update(i, x); // 逐个插入建树
44    }
45
46    while (m--) {
47        int op, x, y;
48        cin >> op >> x >> y;
49        if (op == 1) {
50            update(x, y); // 将a[x]增加y
51        } else {
52            cout << rangeQuery(x, y) << "\n"; // 查询区间[x, y]的和
53        }
54    }
55
56    return 0;
57}

O(n) 建树优化

逐个插入建树的复杂度为 O(n log n)。可以优化到 O(n)：

1// O(n)建树：每个节点将自己的值加给父节点
2void build() {
3    for (int i = 1; i <= n; i++) {
4        c[i] = a[i]; // 先用原值初始化
5    }
6    for (int i = 1; i <= n; i++) {
7        int father = i + lowbit(i);
8        if (father <= n) {
9            c[father] += c[i];
10        }
11    }
12}

✨ 执行示例

以数组 a = [1, 3, 2, 5, 4, 7, 6, 8]（n=8）为例：

lowbit 值与管理区间：

查询 query(7) — 求 a[1]+...+a[7] = 28：

1. x=7 → c[7]=6，x -= lowbit(7)=1 → x=6
2. x=6 → c[6]=11，x -= lowbit(6)=2 → x=4
3. x=4 → c[4]=11，x -= lowbit(4)=4 → x=0
4. 结果 = 6 + 11 + 11 = 28 ✓

修改 update(3, 2) — 将 a[3] 增加 2：

1. x=3 → c[3] += 2，x += lowbit(3)=1 → x=4
2. x=4 → c[4] += 2，x += lowbit(4)=4 → x=8
3. x=8 → c[8] += 2，x += lowbit(8)=8 → x=16 > n，结束

✨ 解题步骤详解

1. 识别问题类型：是否需要单点修改 + 区间查询？如果是前缀和型运算（加法、异或等），树状数组是首选。
2. 确定下标范围：树状数组下标必须从 1 开始（lowbit(0) = 0 会死循环）。
3. 选择建树方式：数据量大时使用 O(n) 建树。
4. 注意数据类型：如果数据范围较大，需要用 long long。

树状数组求逆序对

1// 离散化后，从右到左扫描
2// 每次查询比当前值小的已插入元素个数
3long long countInversions() {
4    long long cnt = 0;
5    for (int i = n; i >= 1; i--) {
6        cnt += query(a[i] - 1);  // 查询比a[i]小的已插入元素个数
7        update(a[i], 1);         // 插入a[i]
8    }
9    return cnt;
10}

✨ 常见错误

1. 下标从 0 开始：lowbit(0) = 0，导致 update 和 query 死循环。树状数组下标必须从 1 开始。
2. 忘记取 long long：前缀和可能溢出 int。
3. query 函数写成累加 c[x] 而非 sum：注意前缀查询中的累加变量应该初始化为 0，且累加的是 c[x]。
4. 建树时直接赋值：c[i] = a[i] 是错误的，应该用 update(i, a[i]) 或者 O(n) 建树。
5. 区间查询忘记减 1：rangeQuery(l, r) = query(r) - query(l-1)，不是 query(l)。

✨ 算法评价

优点：

• 代码极短，常数极小
• 空间仅需一个数组
• 比线段树快 2-3 倍

缺点：

• 只能处理前缀型运算（不能直接做区间最值）
• 功能不如线段树灵活

适用场景：单点修改 + 区间求和、逆序对计数、动态排名等。