线段树（Segment Tree）

算法原理

线段树是分治法思想 + 二叉树结构 + 懒标记技术的合体：树上每个节点代表数组的一段区间 [pl, pr]，从根 [1, n] 开始每次把区间对半分给两个儿子，直到叶子（pl = pr 只有一个元素）；节点上存的值（本动画是区间和）在建树回溯时由左右儿子合并而来。因为除了最后一层其他层全满，它是"最平衡"的二叉树，高度只有 ⌈log₂n⌉。

本动画在一棵 8 元素的数列上完整走一遍主线（a = [3, 1, 4, 1, 5, 9, 2, 6]，根 sum = 31）：

建树：分半 [1,8] → [1,4][5,8] → 4 片叶子两层 → 回溯逐层合并 sum
查询 [3,6]：命中 [3,4] 返 5、命中 [5,6] 返 14 → ans = 19
更新 [2,5] += 2（懒标记）：命中就记账，部分相交才下钻
查询 [3,3]：走到挂账的 [3,4]，先 push down 三步结账，返 6

所有递归都遵守三态口诀「命中返 · 相交钻 · 无交跳」：节点区间被查询/更新区间完全包含（命中）就整段处理、不再下钻；部分相交（含节点覆盖整个查询的情形）就拆开递归；无交集立即返回 0 / 跳过。

动画怎么看

上半区是树：15 个节点卡 = 区间 [l,r] + sum，父子实线连线；黄色描边 = 部分相交（下钻），绿色 = 命中，灰色 = 无交集，品红描边 = 回溯时 pushup 重算，红色 = 朴素做法的灾难路线；本拍移动的边青色加粗；
宣告牌 + ans 累加器（右上）：每幕宣告当前操作与区间，青色区间括号同步罩在数组条上；查询幕命中一拍 ans 就累加一项；
lazy 角标：更新命中内部节点时，卡右上角挂出黄色 lazy 2 小牌——账记在节点上、孩子还没拿到钱；数组条上对应叶子（a[3]、a[4]）此时仍是旧值，账本拍会用虚框点出"账未结"；
pushdown 三步：查询走到有账的 [3,4] 时逐拍演示——①儿子 val += lazy×len ②儿子 lazy += 账 ③自己 lazy 清 0（角标红闪消失），随后 [3,3] 返 6；
数组 a 条（底部）：始终显示叶子实时存储值——懒标记期间它和"真实数组"不一致，正是"账未结"的可视化；大✓收幕时定格 3 3 6 3 7 9 2 6。

复杂度分析

项目	复杂度	说明
建树	O(n)	每个节点合并一次
单次查询 / 区间更新	O(log n)	每层只访问常数个节点，从根最多走到叶
m 次操作总计	O((n+m)·log n)	本动画 n=8、m=3 次操作
空间	O(4n)	节点数 ≤ 2^⌈log₂n⌉+1 − 1 ≤ 4n−1，开 4n 数组即可
对比树状数组	—	树状数组常数小但只能做前缀/区间和；线段树能做最值、区间赋值、区间乘加等任意可合并信息

C++ 参考代码

#include <iostream>
const int N = 8;
long long val[4 * N], lazy[4 * N];
int a[N + 1] = {0, 3, 1, 4, 1, 5, 9, 2, 6};   // 1 基

void pushup(int id) { val[id] = val[id * 2] + val[id * 2 + 1]; }

void build(int id, int l, int r) {
    if (l == r) { val[id] = a[l]; return; }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    pushup(id);
}

void pushdown(int id, int l, int r) {          // 下传三步
    if (lazy[id]) {
        int mid = (l + r) / 2;
        val[id * 2]     += lazy[id] * (mid - l + 1);   // ① 儿 val += 账×长度
        val[id * 2 + 1] += lazy[id] * (r - mid);
        lazy[id * 2]     += lazy[id];                  // ② 儿 lazy += 账
        lazy[id * 2 + 1] += lazy[id];
        lazy[id] = 0;                                  // ③ 自己清 0
    }
}

void update(int id, int l, int r, int x, int y, long long k) {
    if (x <= l && r <= y) {                    // 命中：记账，不下传
        val[id] += k * (r - l + 1);
        lazy[id] += k;
        return;
    }
    pushdown(id, l, r);                        // 有账先结，再下钻
    int mid = (l + r) / 2;
    if (x <= mid) update(id * 2, l, mid, x, y, k);
    if (y > mid)  update(id * 2 + 1, mid + 1, r, x, y, k);
    pushup(id);                                // 回溯重算
}

long long query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) return val[id];      // 命中：直接返回
    pushdown(id, l, r);
    int mid = (l + r) / 2;
    long long ans = 0;
    if (x <= mid) ans += query(id * 2, l, mid, x, y);
    if (y > mid)  ans += query(id * 2 + 1, mid + 1, r, x, y);
    return ans;
}

int main() {
    build(1, 1, N);                            // 根 sum = 31
    update(1, 1, N, 2, 5, 2);                  // [2,5] += 2，账记在 [3,4]
    std::cout << query(1, 1, N, 3, 6) << "\n"; // 25 = 6+3+7+9，懒标记自动结账
    std::cout << query(1, 1, N, 3, 3) << "\n"; // 6
    return 0;
}

什么时候用线段树

线段树是"区间问题 + 修改和询问交替出现"的通用解法：区间加/区间求和（洛谷 P3372 模板）、区间乘加混合（P3373，两个懒标记按先乘后加复合）、区间最值、区间赋值（P1558 色板游戏：30 位掩码 + 赋值懒标记）、区间平方和（P1471）乃至最大子段和合并（P4513，节点维护 sum/lmax/rmax/tmax 四个值）——只要大区间的答案能由小区间的答案合并出来，线段树就能维护。它的里程碑意义在于懒标记：把"逐点改"的 O(n) 灾难压成"整段记账"的 O(log n)。判断口诀：单点改 + 前缀和可用户可树状数组；要区间改 + 区间问、或维护的信息超出前缀和的表达能力，就上线段树。