入门：从离线前缀和到在线区间树
基于通用数据结构概念 · 核于 2026-07
速查
- 为什么需要：前缀和擅长「数组不变 + 多次查询」（O(1) 查，但改一个元素要 O(n) 重建）；差分擅长「多次区间改 + 最后一次还原」（O(1) 改，但查要 O(n)）。一旦查询与修改交替进行（改一下查一下），两者都退化——此时需要「在线」结构。
- 在线结构：支持边改边查、每次都 O(log n) 的数据结构；本叶讲两种——线段树与树状数组。
- 线段树（Segment Tree）：把数组映射成一棵二叉树，每个节点存一个区间的聚合信息（和/最值等）；区间操作被拆成 O(log n) 个树节点操作。
- 线段树核心复杂度：建树 O(n)；单点修改 O(log n)；区间查询 O(log n)；区间修改 + 懒标记 O(log n)。
- 懒标记（lazy propagation）：区间修改时不立刻下传到叶子（否则 O(n)），而是先在覆盖节点上「记账」，等下次必须经过时再下传（
pushDown）——把区间修改从 O(n) 压到 O(log n)。 - 树状数组（BIT / Fenwick Tree）：利用
lowbit(x) = x & (-x)（二进制最低位的 1），让tree[i]管辖区间[i - lowbit(i) + 1, i]，用一个普通数组编码一棵隐式二叉树。 - 树状数组核心复杂度：单点修改 O(log n)（沿
i += lowbit(i)上传）；前缀查询 O(log n)（沿i -= lowbit(i)累加）；区间查询 = 两前缀相减。 - 区间查询通用式：
sum(l, r) = prefix(r) - prefix(l-1)——线段树直接查，树状数组靠两前缀相减。 - 定位差异：线段树通用（任意区间改 + 区间查，支持懒标记），但代码重、常数大；树状数组轻量（常数极小、代码极短），但只直接支持单点改 + 前缀查，区间改要差分技巧。
- 选型口诀：区间改 + 区间查 → 线段树；单点改 + 区间查且追求常数 → 树状数组。
- 共同前提：维护的信息必须满足结合律（和、积、min/max、GCD、异或都满足）——不满足则两者都做不了（如区间第 k 小）。
- 进阶顺序：线段树：区间查询与懒标记 → 树状数组：轻量的前缀结构 → 参考。
一、前缀和的局限：为什么需要在线结构
回顾前缀和与差分：前缀和把区间求和从 O(n) 降到 O(1)，差分数组把区间修改从 O(n) 降到 O(1)。但它们都有个共同前提——离线：
- 前缀和：数组一旦改变，整个前缀和数组就要 O(n) 重建。适合「数组不变 + 多次查询」。
- 差分数组：每次查询要 O(n) 求前缀和还原。适合「多次区间改 + 最后一次查询」。
考虑这样一个场景：长度 n 的数组，要做 q 次操作，每次随机是「把某段区间加 v」或「查某段区间的和」：
改一下 → 查一下 → 再改一下 → 再查一下 ...- 用前缀和：每次改后要 O(n) 重建，总共 O(nq)。
- 用差分数组：每次查要 O(n) 还原，总共 O(nq)。
- 用朴素数组：每次区间操作 O(n)，总共 O(nq)。
n、q 都到 10⁵ 时，O(nq) = 10¹⁰，超时。我们需要一个每次操作都 O(log n) 的结构——这就是线段树和树状数组，它们把「查询」和「修改」对称地压到 O(log n)，是前缀和/差分的「在线升级版」。
二、核心思想：用二叉树把区间操作降到 O(log n)
线段树和树状数组的共同本质：把数组 a[0..n-1] 组织成一棵二叉树，每个节点管一个区间，区间操作 = O(log n) 个节点操作的合并。由于二叉树深度 O(log n)，所以单次操作只碰 O(log n) 个节点。
线段树：显式的分治二叉树
线段树把 [0, n-1] 递归二分：
[0,7] 根节点管整个区间
/ \
[0,3] [4,7] 左右孩子各管一半
/ \ / \
[0,1] [2,3] [4,5] [6,7]
/\ /\ /\ /\
0 1 2 3 4 5 6 7 叶子对应单个元素- 每个节点存它所管区间的聚合信息（如区间和、区间最小值）。
- 查询
[l, r]：从根递归，能完全覆盖就取该节点，否则下分到左右孩子——只碰 O(log n) 个节点。 - 修改：递归到对应叶子改值，回溯时用
pushUp重新计算祖先——也只碰 O(log n) 个节点。
树状数组：用 lowbit 隐式编码的二叉树
树状数组不用真正的树结构，而是用一个普通数组 tree[1..n]，靠 lowbit（二进制最低位的 1）定义每个槽管哪个区间：
tree[i] 管辖区间 [i - lowbit(i) + 1, i]lowbit(i) 决定了 tree[i] 管多长。i 的二进制末尾 0 越多（lowbit 越大），管的区间越长——这恰好编码了一棵隐式的二叉树，修改沿 i += lowbit(i) 上传，查询沿 i -= lowbit(i) 累加。具体机制见树状数组。
三、两者定位对比
| 维度 | 线段树 | 树状数组（BIT） |
|---|---|---|
| 区间查询（和/最值） | 支持 O(log n) ✅ | 支持 O(log n)（和/异或等可减的） |
| 单点修改 | O(log n) | O(log n)（常数更小） |
| 区间修改 + 懒标记 | 支持 O(log n) ✅ | 原生不支持（差分变体仅区间加） |
| 维护的信息 | 任意满足结合律 | 需满足结合律且可逆（能 a-b 还原） |
| 代码量 | 较长（~100 行，含 lazy） | 极短（~20 行） |
| 空间 | 4n | n+1 |
| 常数 | 较大（递归） | 极小（迭代、缓存友好） |
一句话总结：
- 需要区间修改 + 区间查询 → 线段树（带懒标记）。
- 只需单点修改 + 区间（前缀）查询，追求常数小/代码短 → 树状数组。
- 只查不改 → 前缀和就够了，不必上线段树/树状数组。
下一步
理解了「为什么需要在线结构」与两者定位后，下一步深入线段树——看它如何用分治二叉树实现 O(log n) 的区间查询，以及高频考点「懒标记」如何把区间修改也压到 O(log n)，见线段树：区间查询与懒标记。