📖 第 3.9 章 ⏱️ 约 70 分钟 🎯 进阶

第 3.9 章：线段树入门

📝 前置条件： 理解前缀和（第 3.2 章）、数组和递归（第 2.3 章）。线段树是较进阶的数据结构——确保熟悉递归后再深入学习。

线段树是竞赛编程中最强大的数据结构之一，解决了前缀和无法处理的根本问题：带更新的区间查询。

3.9.1 问题：为什么需要线段树

思考这个挑战：

  • 数组 A，共 N 个整数
  • Q1： A[l..r] 的和是多少？（区间求和查询）
  • Q2： 更新 A[i] = x（单点更新）

前缀和方案： 区间查询 O(1)，但更新需要重新计算所有前缀和，O(N)。对于 M 次混合查询，总计 O(NM) —— N,M = 10^5 时太慢了。

线段树方案： 查询和更新都是 O(log N)。M 次混合查询总计：O(M log N) ✓

数据结构构建查询更新最适合
简单数组O(N)O(N)O(1)只有更新
前缀和O(N)O(1)O(N)只有查询
线段树O(N)O(log N)O(log N)查询 + 更新
树状数组（BIT）O(N log N)O(log N)O(log N)代码更简单，仅限前缀和

上图展示了在数组 [1, 3, 5, 7, 9, 11] 上构建的线段树。每个内部节点存储其区间的和。对区间 [2,4] 的查询（和=21）只需组合 2 个节点——O(log N) 而不是 O(N)。

3.9.2 结构：什么是线段树？

线段树是一棵完全二叉树：

  • 每个叶节点对应一个数组元素
  • 每个内部节点存储其区间的聚合值（和、最小值、最大值等）
  • 根节点覆盖整个数组 [0..N-1]
  • 覆盖 [l..r] 的节点有两个子节点：[l..mid] 和 [mid+1..r]

对 N 个元素的数组，树最多有 4N 个节点（我们使用大小为 4N 的 1-indexed 树数组作为安全上界）。

数组：[1, 3, 5, 7, 9, 11]（下标 0..5）

树（1-indexed，节点 i 的子节点是 2i 和 2i+1）：
         [0..5]=36
        /          \
  [0..2]=9       [3..5]=27
   /     \        /      \
[0..1]=4 [2]=5  [3..4]=16  [5]=11
  /   \          /    \
[0]=1 [1]=3   [3]=7  [4]=9

下图展示了线段树的完整结构，以及查询 sum([2,4]) 时蓝色高亮的访问路径：

Segment Tree Structure

3.9.3 构建线段树

📄 查看代码：3.9.3 构建线段树 
// 构建线段树 — O(N)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int tree[4 * MAXN];  // 线段树数组（大小为 4 倍数组长度）
int arr[MAXN];       // 原始数组

// 构建：递归填充 tree[]
// node = 当前树节点下标（从 1 开始）
// start, end = 该节点覆盖的范围
void build(int node, int start, int end) {
    if (start == end) {
        // 叶节点：存储数组元素
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        // 先构建左右子节点
        build(2 * node, start, mid);        // 左子节点
        build(2 * node + 1, mid + 1, end);  // 右子节点
        // 内部节点：子节点之和
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1);  // 从节点 1 开始构建，覆盖 [0..n-1]

    return 0;
}

对 [1, 3, 5, 7, 9, 11] 的构建追踪：

📄 Code 完整代码 
build(1, 0, 5):
  build(2, 0, 2):
    build(4, 0, 1):
      build(8, 0, 0): tree[8] = arr[0] = 1
      build(9, 1, 1): tree[9] = arr[1] = 3
      tree[4] = tree[8] + tree[9] = 4
    build(5, 2, 2): tree[5] = arr[2] = 5
    tree[2] = tree[4] + tree[5] = 9
  build(3, 3, 5):
    ...
    tree[3] = 27
  tree[1] = 9 + 27 = 36

3.9.4 区间查询

查询 arr[l..r] 的和：

核心思路： 递归下降树，在每个覆盖 [start..end] 的节点处：

  • 若 [start..end] 完全在 [l..r] 内：直接返回该节点的值（完成！）
  • 若 [start..end] 完全在 [l..r] 外：返回 0（无贡献）
  • 否则：递归进入两个子节点，将结果求和
📄 C++ 完整代码 
// 区间查询：arr[l..r] 的和 — O(log N)
// node = 当前树节点，[start, end] = 覆盖范围
// [l, r] = 查询范围
int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        // 情况一：当前区间完全在查询范围外
        return 0;   // 求和的单位元（求最小值用 INT_MAX）
    }
    if (l <= start && end <= r) {
        // 情况二：当前区间完全在查询范围内
        return tree[node];   // ← 关键行：直接使用该节点！
    }
    // 情况三：部分重叠——递归进入子节点
    int mid = (start + end) / 2;
    int leftSum  = query(2 * node, start, mid, l, r);
    int rightSum = query(2 * node + 1, mid + 1, end, l, r);
    return leftSum + rightSum;
}

// 用法：arr[2..4] 的和
int result = query(1, 0, n - 1, 2, 4);
cout << result << "\n";  // 5 + 7 + 9 = 21

在 [1,3,5,7,9,11] 的树上查询 [2..4] 的追踪：

query(1, 0, 5, 2, 4):
  query(2, 0, 2, 2, 4): [0..2] 与 [2..4] 部分重叠
    query(4, 0, 1, 2, 4): [0..1] 在 [2..4] 外 → 返回 0
    query(5, 2, 2, 2, 4): [2..2] 在 [2..4] 内 → 返回 5
    返回 0 + 5 = 5
  query(3, 3, 5, 2, 4): [3..5] 与 [2..4] 部分重叠
    query(6, 3, 4, 2, 4): [3..4] 在 [2..4] 内 → 返回 16
    query(7, 5, 5, 2, 4): [5..5] 在 [2..4] 外 → 返回 0
    返回 16 + 0 = 16
  返回 5 + 16 = 21 ✓

只访问了 4 个节点——O(log N)！

下图展示了哪些节点被访问以及原因——绿色节点直接返回其值，橙色节点递归进入子节点，灰色节点立即被剪枝：

Segment Tree Query Visualization

3.9.5 单点更新

更新 arr[i] = x（修改单个元素）：

📄 更新 `arr[i] = x`（修改单个元素）： 
// 单点更新：设置 arr[idx] = val — O(log N)
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // 叶节点：更新值
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);      // 在左子树中更新
        } else {
            update(2 * node + 1, mid + 1, end, idx, val); // 在右子树中更新
        }
        // 子节点更改后，更新这个内部节点
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

// 用法：设置 arr[2] = 10
update(1, 0, n - 1, 2, 10);

单点更新只修改从更新的叶节点到根节点路径上的节点——仅 O(log N) 个节点，其他所有分支保持不变：

Segment Tree Point Update

3.9.6 完整实现

这是完整的、可直接用于竞赛的线段树：

📄 这是完整的、可直接用于竞赛的线段树： 
// 线段树 — O(N) 构建，O(log N) 查询/更新
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long tree[4 * MAXN];

void build(int node, int start, int end, long long arr[]) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid, arr);
    build(2 * node + 1, mid + 1, end, arr);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

long long query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r)
         + query(2 * node + 1, mid + 1, end, l, r);
}

void update(int node, int start, int end, int idx, long long val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2 * node, start, mid, idx, val);
    else update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    long long arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1, arr);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // 单点更新：设置 arr[i] = v
            int i; long long v;
            cin >> i >> v;
            update(1, 0, n - 1, i, v);
        } else {
            // 区间查询：arr[l..r] 的和
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

样例输入：

6 5
1 3 5 7 9 11
2 2 4
1 2 10
2 2 4
2 0 5
1 0 0

样例输出：

21
26
41

(第1次查询 [2,4] = 5+7+9 = 21；执行 update arr[2]=10 后，第2次查询 [2,4] = 10+7+9 = 26；第3次查询 [0,5] = 1+3+10+7+9+11 = 41)

3.9.7 线段树 vs 树状数组（BIT）

特性线段树树状数组（BIT）
代码复杂度中等（约 30 行）简单（约 15 行）
区间查询任意结合性操作仅限前缀和
区间更新可以（需懒惰传播）可以（需技巧）
单点更新O(log N)O(log N)
空间O(4N)O(N)
使用场景区间最小/最大、复杂查询带更新的前缀和

💡 核心思路： 若需要带更新的区间和，树状数组更简单。若需要区间最小值、区间最大值，或任何非前缀操作，用线段树。

3.9.8 区间最小值查询变体

只需将聚合操作从 + 改为 min：

📄 只需将聚合操作从 `+` 改为 `min`： 
// 区间最小线段树 — 结构相同，操作不同
void build_min(int node, int start, int end, int arr[]) {
    if (start == end) { tree[node] = arr[start]; return; }
    int mid = (start + end) / 2;
    build_min(2*node, start, mid, arr);
    build_min(2*node+1, mid+1, end, arr);
    tree[node] = min(tree[2*node], tree[2*node+1]);  // ← 改为 min
}

int query_min(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return INT_MAX;   // ← min 的单位元
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return min(query_min(2*node, start, mid, l, r),
               query_min(2*node+1, mid+1, end, l, r));
}

3.9.9 带懒惰传播的区间更新

前面的线段树处理单点更新。对于区间更新：「给 [L, R] 的所有元素加 V」怎么办？

没有懒惰传播，需要 O(N) 次更新（每个元素一次）。有了懒惰传播，实现 O(log N) 区间更新。

线段树懒惰传播（Lazy Propagation）

💡 核心思路： 不立即更新所有受影响的叶节点，而是「懒惰地」推迟更新——在适用的最高节点存储更新，只在真正需要子节点时才向下传递。

每个节点现在存储两个值：

  • tree[node]：该区间的实际聚合值（区间和）
  • lazy[node]：尚未向子节点传递的待处理更新

向下传递规则： 访问有待处理懒惰更新的节点时：

  1. 将懒惰更新应用到该节点的值
  2. 将懒惰更新传递给两个子节点（向下传递）
  3. 清除该节点的懒惰值
📄 3. 清除该节点的懒惰值 
// 带懒惰传播的线段树
// 支持：区间加法更新、区间求和查询 — 各 O(log N)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

ll tree[4 * MAXN];   // tree[node] = 区间和
ll lazy[4 * MAXN];   // lazy[node] = 待处理的加法值（0 表示无待处理）

// ── 向下传递：将待处理懒惰传递给子节点 ──
void pushDown(int node, int start, int end) {
    if (lazy[node] == 0) return;  // 无待处理更新

    int mid = (start + end) / 2;
    int left = 2 * node, right = 2 * node + 1;

    // 更新左子节点的和：加 lazy * （左子节点元素数量）
    tree[left]  += lazy[node] * (mid - start + 1);
    tree[right] += lazy[node] * (end - mid);

    // 将懒惰传递给子节点
    lazy[left]  += lazy[node];
    lazy[right] += lazy[node];

    // 清除当前节点的懒惰（已向下传递）
    lazy[node] = 0;
}

// ── 构建 ──
void build(int node, int start, int end, ll arr[]) {
    lazy[node] = 0;
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2*node, start, mid, arr);
    build(2*node+1, mid+1, end, arr);
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── 区间更新：给 [l, r] 内所有元素加 val ──
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;  // 范围外：无操作

    if (l <= start && end <= r) {
        // 当前区间完全在 [l, r] 内：应用懒惰，不递归
        tree[node] += val * (end - start + 1);  // ← 关键：乘以区间长度
        lazy[node] += val;                        // 存储给子节点的待处理值
        return;
    }

    // 部分重叠：先向下传递已有懒惰，再递归
    pushDown(node, start, end);  // ← 关键：递归前必须先 pushDown！

    int mid = (start + end) / 2;
    update(2*node,   start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);

    // 从子节点更新当前节点
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── 区间查询：[l, r] 内元素之和 ──
ll query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;  // 范围外

    if (l <= start && end <= r) {
        return tree[node];  // 完全在内：返回存储的和（已包含懒惰！）
    }

    // 部分重叠：先向下传递，再递归
    pushDown(node, start, end);  // ← 关键：递归前必须先 pushDown！

    int mid = (start + end) / 2;
    ll leftSum  = query(2*node,   start, mid, l, r);
    ll rightSum = query(2*node+1, mid+1, end, l, r);
    return leftSum + rightSum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    ll arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n-1, arr);

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            // 区间更新：给 [l, r] 加 val
            int l, r; ll val;
            cin >> l >> r >> val;
            update(1, 0, n-1, l, r, val);
        } else {
            // 区间查询：[l, r] 之和
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n-1, l, r) << "\n";
        }
    }

    return 0;
}

⚠️ 懒惰传播常见错误

4 大懒惰传播 Bug：

  1. 递归前忘记 pushDown —— 子节点会在父节点的懒惰之上再接收子节点自己的，导致查询结果错误
  2. 大小乘数用错 —— 写 tree[node] += val 而非 tree[node] += val * (end - start + 1)。节点存的是和，给 (end-start+1) 个元素各加 val 意味着和增加 val×(大小)
  3. 未将 lazy[] 初始化为 0 —— 用 memset(lazy, 0, sizeof(lazy)) 或在 build() 中初始化
  4. 混合不同操作的懒惰 —— 若同时有「区间加」和「区间乘」两种懒惰，顺序很重要，需要两个独立的懒惰数组和仔细处理的 pushDown

懒惰传播通用化

该模式适用于任何满足以下条件的操作：

  • 聚合是结合性操作（和、最小值、最大值、XOR……）
  • 更新在聚合上分配（给 n 个元素各加 k，和增加 k*n）
更新查询懒惰存储pushDown 公式
区间加区间和加法增量tree[child] += lazy * size; lazy[child] += lazy
区间赋值区间和赋值tree[child] = lazy * size; lazy[child] = lazy
区间加区间最小加法增量tree[child] += lazy; lazy[child] += lazy
区间赋值区间最小赋值tree[child] = lazy; lazy[child] = lazy

3.9.10 区间赋值（第二类懒惰）

区间加是最常见的懒惰操作，但竞赛中还有另一类：把 [L, R] 内所有元素设为同一个值 V。

区别在于 pushDown 逻辑：区间加的懒惰是「增量叠加」，区间赋值的懒惰是「直接覆盖」。

📄 区别在于 pushDown 逻辑：区间加的懒惰是「增量叠加」，区间赋值的懒惰是「直接覆盖」。 
// 带区间赋值懒惰的线段树
// tree[i] = 区间和，lazy[i] = 赋值标记（-1 表示无标记）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;

ll tree[4*MAXN];
ll lazy[4*MAXN];  // -1 = 无标记

void build(int s, int t, int p, ll a[]) {
    lazy[p] = -1;
    if (s == t) { tree[p] = a[s]; return; }
    int m = s + ((t - s) >> 1);
    build(s, m, p*2, a);
    build(m+1, t, p*2+1, a);
    tree[p] = tree[p*2] + tree[p*2+1];
}

// ── pushDown：区间赋值 ──
void pushDown(int p, int s, int t) {
    if (lazy[p] == -1) return;
    int m = s + ((t - s) >> 1);
    // 左子树所有元素赋值为 lazy[p]，共 m-s+1 个
    tree[p*2]   = lazy[p] * (m - s + 1);
    tree[p*2+1] = lazy[p] * (t - m);
    lazy[p*2]   = lazy[p];   // 覆盖（不是叠加！）
    lazy[p*2+1] = lazy[p];
    lazy[p] = -1;             // 清除标记
}

// ── 区间赋值更新 ──
void update(int l, int r, ll c, int s, int t, int p) {
    if (l <= s && t <= r) {
        tree[p] = c * (t - s + 1);  // 整段赋值
        lazy[p] = c;
        return;
    }
    pushDown(p, s, t);
    int m = s + ((t - s) >> 1);
    if (l <= m) update(l, r, c, s, m, p*2);
    if (r > m)  update(l, r, c, m+1, t, p*2+1);
    tree[p] = tree[p*2] + tree[p*2+1];
}

// ── 区间求和查询（同区间加版本，先 pushDown） ──
ll query(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return tree[p];
    pushDown(p, s, t);
    int m = s + ((t - s) >> 1);
    ll res = 0;
    if (l <= m) res += query(l, r, s, m, p*2);
    if (r > m)  res += query(l, r, m+1, t, p*2+1);
    return res;
}

⚠️ 区间赋值 vs 区间加的关键区别：pushDown 时，赋值用覆盖（lazy[child] = val），加法用叠加（lazy[child] += val）。若两种操作混用，必须维护两个独立的 lazy 数组，处理优先级。

3.9.11 动态开点线段树

使用场景

当值域极大（如 $10^9$）时，无法预先开 4N 的数组。但如果操作次数 M 较少（如 $10^5$），实际被访问到的节点只有 $O(M \log V)$ 个。

核心思路： 节点只在访问到时才创建，用 ls[p]、rs[p] 记录左右子节点编号（替代 2p/2p+1）。

📄 C++ 完整代码 
// 动态开点线段树（权值线段树 / 值域线段树）
// 典型应用：区间统计、求第 k 小
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;  // 节点池上限（M * log V）

int ls[MAXN], rs[MAXN];     // 左右子节点编号
long long sum[MAXN];
int cnt, root;              // 节点计数器，根节点编号

// 单点加 1（用于插入值 x 到权值线段树）
void update(int &p, int s, int t, int x) {
    if (!p) p = ++cnt;          // 节点不存在则动态创建
    sum[p]++;
    if (s == t) return;
    int m = s + ((t - s) >> 1);
    if (x <= m) update(ls[p], s, m, x);
    else        update(rs[p], m+1, t, x);
}

// 区间求和
long long query(int p, int s, int t, int l, int r) {
    if (!p) return 0;           // 节点不存在，该区间无元素
    if (l <= s && t <= r) return sum[p];
    int m = s + ((t - s) >> 1);
    long long res = 0;
    if (l <= m) res += query(ls[p], s, m, l, r);
    if (r > m)  res += query(rs[p], m+1, t, l, r);
    return res;
}

// 用法示例：插入若干值后查询 [l, r] 内有多少个
// update(root, 1, 1e9, val);
// query(root, 1, 1e9, l, r);

空间复杂度： M 次操作后节点数为 $O(M \log V)$，远小于 $4V$。

3.9.12 线段树优化建图

使用场景

图论中，若需要「一个点向一段区间内所有点连边」或「一段区间内所有点向一个点连边」，朴素建图边数为 $O(N^2)$，用线段树可降到 $O(N \log N)$。

做法

建两棵线段树：

树方向说明
出树（区间→点）子节点→父节点（0 权边）叶节点连原图点，区间节点汇聚到父节点
入树（点→区间）父节点→子节点（0 权边）父节点分发到叶节点，叶节点连原图点
区间 [2,4] → 点 u 连边：
  在入树中，对应 [2,4] 区间节点连一条权为 w 的边到 u
  入树内部父→子连 0 权边，叶节点与原图点重合

点 u → 区间 [2,4] 连边：
  在出树中，u 连一条权为 w 的边到对应 [2,4] 区间节点
  出树内部子→父连 0 权边，叶节点与原图点重合

建好后，以每个原图点为源点跑 Dijkstra 即可在 $O((N \log N + M) \log N)$ 内解决区间连边的最短路问题。

🔗 参考题目： CF786B Legacy（点→区间、区间→点、点→点混合连边最短路）

线段树变体速览

变体用途复杂度
基础线段树单点更新 + 区间查询O(log N)
懒惰传播（区间加）区间更新 + 区间查询O(log N)
懒惰传播（区间赋值）区间赋值 + 区间查询O(log N)
动态开点线段树值域大但操作少O(M log V) 空间
权值线段树全局第 k 小、逆序对O(log V) 查询
线段树优化建图区间连边的最短路O(N log N) 建图
可持久化线段树维护历史版本O(log N) 每版本

⚠️ 常见错误

  1. 数组大小太小： 始终分配 tree[4 * MAXN]。对非 2 的幂次方大小的数组，用 2 * MAXN 会越界。
  2. 范围外的单位元用错： 求和查询返回 0；求最小查询返回 INT_MAX；求最大查询返回 INT_MIN。
  3. 忘记更新父节点： 更新子节点后，必须重新计算父节点：tree[node] = tree[2*node] + tree[2*node+1]。
  4. 0-indexed vs 1-indexed 混淆： 本实现使用 0-indexed 数组但 1-indexed 树节点，保持一致性。
  5. 前缀和足够时用线段树： 若没有更新操作，前缀和（O(1) 查询）优于线段树（O(log N) 查询）。合适时用更简单的工具。

本章总结

📌 核心要点

操作时间关键代码行
构建O(N)tree[node] = tree[2*node] + tree[2*node+1]
单点更新O(log N)递归到叶节点，向上更新
区间查询O(log N)完全在内/完全在外时提前返回
空间O(4N)分配 tree[4 * MAXN]

❓ 常见问题

Q1：什么时候选线段树 vs 前缀和？

A：简单规则——若数组从不改变，前缀和更好（O(1) 查询 vs O(log N)）。若数组被修改（单点更新），用线段树或 BIT。若需要区间更新（给一段区间加值），用带懒惰传播的线段树。

Q2：为什么树数组大小需要 4N？

A：线段树是完全二叉树。当 N 不是 2 的幂次方时，最后一层可能不完整但仍需空间。最坏情况下需要约 4N 个节点。用 4*MAXN 是安全上界。

Q3：树状数组（BIT）和线段树哪个更好？

A：BIT 代码更短（约 15 行 vs 30 行），常数更小，但只能处理「可前缀分解」的操作（如求和）。线段树更通用（可以处理区间最小/最大、GCD 等），支持更复杂的操作（如懒惰传播）。竞赛中：能用 BIT 就用 BIT，BIT 不够用时切换到线段树。

Q4：线段树能处理哪些类型的查询？

A：任何满足结合律的操作：求和（+）、最小值（min）、最大值（max）、GCD、XOR、乘积等。关键是有「单位元」（如求和的 0、最小值的 INT_MAX、最大值的 INT_MIN）。

Q5：什么是懒惰传播？什么时候需要？

A：当需要「给区间 [L,R] 的每个元素加 V」（区间更新）时，朴素做法从 L 到 R 逐个更新叶节点（O(N)），太慢。懒惰传播将更新「懒惰地」存储在内部节点，只在子节点实际需要被查询时才向下传递，将区间更新也优化为 O(log N)。

🔗 与后续章节的联系

  • 第 3.2 章（前缀和）：线段树的「简化版」——没有更新操作时用前缀和
  • 第 5.1–5.2 章（图）：欧拉序 + 线段树可以高效处理树上路径查询
  • 第 6.1–6.3 章（DP）：某些 DP 优化需要线段树维护 DP 值的区间最小/最大
  • 线段树是 USACO Gold 级别的核心数据结构，掌握它能解决大量 Gold 题目

练习题

题目 3.9.1 — 经典区间和 🟢 简单 实现线段树，处理 N 个元素和 Q 次查询：单点更新或区间求和。

提示 使用 3.9.6 节的完整实现，用标志区分查询类型（1 = 更新，2 = 查询）。
✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long tree[4*MAXN];
int n, q;

void build(int node, int s, int e, int arr[]) {
    if (s==e) { tree[node]=arr[s]; return; }
    int mid=(s+e)/2;
    build(2*node,s,mid,arr); build(2*node+1,mid+1,e,arr);
    tree[node]=tree[2*node]+tree[2*node+1];
}
void update(int node,int s,int e,int idx,long long val) {
    if (s==e) { tree[node]=val; return; }
    int mid=(s+e)/2;
    if (idx<=mid) update(2*node,s,mid,idx,val);
    else update(2*node+1,mid+1,e,idx,val);
    tree[node]=tree[2*node]+tree[2*node+1];
}
long long query(int node,int s,int e,int l,int r) {
    if (r<s||e<l) return 0;
    if (l<=s&&e<=r) return tree[node];
    int mid=(s+e)/2;
    return query(2*node,s,mid,l,r)+query(2*node+1,mid+1,e,l,r);
}
int arr[MAXN];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n,arr);
    while(q--) {
        int t; cin>>t;
        if(t==1) { int i; long long v; cin>>i>>v; update(1,1,n,i,v); }
        else { int l,r; cin>>l>>r; cout<<query(1,1,n,l,r)<<"\n"; }
    }
}

复杂度： O(N) 构建，每次查询/更新 O(log N)。

题目 3.9.2 — 区间最小值 🟡 中等 同上，但查询区间最小值，处理单点更新。

提示 将树操作中的 `+` 改为 `min`，范围外返回 `INT_MAX`。
✅ 完整题解

在上面的解法中修改两行：

// 在 build/update 中：
tree[node] = min(tree[2*node], tree[2*node+1]);
// 在 query 中——范围外的单位元：
if (r < s || e < l) return INT_MAX;
// 合并：
return min(query(2*node,s,mid,l,r), query(2*node+1,mid+1,e,l,r));

初始化：tree[叶节点] = arr[s]（相同）。唯一改变的是聚合函数和单位元。

题目 3.9.3 — 逆序对计数 🔴 困难 统计满足 i < j 且 arr[i] > arr[j] 的对 (i,j) 的个数。

提示 从左到右处理元素。对每个元素 x，查询已插入的元素中 > x 的个数。
✅ 完整题解

核心思路： 将值坐标压缩到 [1..N]。对每个元素 x（从左到右），逆序对数 += （已插入元素数）- （已插入的 ≤ x 的数量）= query(N) - query(x)。然后插入 x。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int tree[MAXN], n;
void update(int i){for(;i<=n;i+=i&-i) tree[i]++;}
int query(int i){int s=0;for(;i>0;i-=i&-i)s+=tree[i];return s;}

int main(){
    cin>>n;
    vector<int> a(n);
    for(int&x:a)cin>>x;
    // 坐标压缩
    vector<int> sorted=a; sort(sorted.begin(),sorted.end());
    sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());
    for(int&x:a) x=lower_bound(sorted.begin(),sorted.end(),x)-sorted.begin()+1;
    int m=sorted.size();

    long long inv=0;
    for(int i=0;i<n;i++){
        inv += (i - query(a[i]));  // 已见过的中大于 a[i] 的个数
        update(a[i]);
    }
    cout<<inv<<"\n";
}

复杂度： O(N log N)，用 BIT（对此问题比线段树更合适）。

🏆 挑战题：USACO 2016 February Gold：围牛栏 需要带更新的区间最大查询的题目。尝试分别用树状数组和线段树解决，理解两者的权衡。