一、为什么需要线段树
一个在线游戏有 100 万名玩家，运营想实时查看等级在 50 到 80 之间的玩家数量。最朴素的做法：遍历整个数组统计——O(n)，每秒查询几次就扛不住了。更麻烦的是，玩家等级还在不断变化，每次更新后重新统计更是灾难。
类似的需求到处都是：数据库要统计某个时间段的交易总额，监控系统要查某段延迟区间的请求占比，股票平台要看某支代码在特定价格区间的成交量。这些问题的共同模式是：数组上的区间聚合查询 + 单点更新，两个操作都要快。
线段树（Segment Tree）就是为这个模式量身定制的。它把数组区间组织成一棵二叉树，每个节点存储一段区间的聚合值（和、最大值、最小值、计数等）。单点更新只需修改 O(log n) 个节点，区间查询只需合并 O(log n) 个节点的值——两者都在对数时间内完成。
二、现实类比
想象一本账簿的目录：最上面写着一整年的总收入，下一层按季度分列，再下一层按月份分列。你想知道 3 月到 7 月的总收入，不需要翻遍每天的单据——拿出 3 月的合计、4 到 6 月的季度合计、7 月的合计，加起来就行。某天记错了一笔？改掉那天的记录，然后沿着路径更新月度、季度、年度的合计。线段树就是这棵从细到粗的汇总树。
三、核心思想
给定数组 [2, 5, 1, 4, 9, 3]，线段树将其递归二分，每个节点存储对应区间的聚合值（以区间和为例）：
查询区间 [2, 4] 的和：递归到节点，如果当前区间完全在查询范围外则返回 0，完全在内则返回节点值，部分重叠则递归左右子树。本例中会取到 [2,2]=1、[3,3]=4、[4,4]=9，合计 14。
3.1 单点更新
更新 arr[3] = 6：从根节点出发，找到 [3,3] 叶子节点改为 6，然后沿路径回溯更新所有祖先节点的值——[3,5] 从 16 变为 18，[0,5] 从 24 变为 26。只影响 O(log n) 个节点。
3.2 区间查询
查询区间 [l, r]：从根节点出发，当前区间与 [l, r] 无交集则返回零值，完全包含则返回节点值，部分重叠则递归合并左右结果。最多访问 O(log n) 个节点。
3.3 核心操作与复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建树 | O(n) | 自底向上构建所有节点 |
| 单点更新 | O(log n) | 修改一个元素，更新路径上 log n 个节点 |
| 区间查询 | O(log n) | 最多访问 4 个节点每层，共 O(log n) |
| 区间更新（带懒标记） | O(log n) | 延迟下推更新，摊销后仍为 O(log n) |
懒标记（Lazy Propagation）是线段树的重要扩展。当需要对一个区间统一加某个值时，不逐个更新叶子节点，而是在覆盖该区间的节点上打个标记。后续查询到该节点时才把标记下推给子节点。这让区间更新也从 O(n) 降到 O(log n)。
四、变体与对比
| 特性 | 线段树 | 树状数组（Fenwick Tree） | 跳表 | 平方分解 |
|---|---|---|---|---|
| 区间查询 | O(log n) | O(log n) | O(log n) | O(√n) |
| 单点更新 | O(log n) | O(log n) | O(log n) | O(1) |
| 区间更新（懒标记） | 支持 | 需差分技巧 | 不支持 | 支持 |
| 空间 | O(4n) | O(n) | O(n) | O(n) |
| 代码复杂度 | 中等 | 低 | 中等 | 低 |
| 灵活聚合 | 任意可结合运算 | 前缀可逆运算 | 有序集合 | 任意运算 |
树状数组（Fenwick Tree / BIT）是线段树的简化版，利用 lowbit 技巧用 O(n) 空间实现前缀查询和单点更新。它的优势是代码极短、常数小，但只能做前缀可逆的运算（如求和、异或），不支持区间最大值等不可逆聚合，也不天然支持懒标记。
平方分解把数组分成 √n 个块，每块预计算聚合值。代码简单但查询 O(√n)，数据量大时不如线段树。
五、多语言实现
5.1 Go 实现
package segmenttree
// SegmentTree 支持区间求和与单点更新type SegmentTree struct { n int // 叶子节点数量 tree []int // 线段树数组，1-indexed}
// New 从数组构建线段树，O(n)func New(arr []int) *SegmentTree { n := len(arr) st := &SegmentTree{n: n, tree: make([]int, 4*n)} st.build(arr, 1, 0, n-1) return st}
func (st *SegmentTree) build(arr []int, node, lo, hi int) { if lo == hi { st.tree[node] = arr[lo] // 叶子节点 return } mid := (lo + hi) / 2 st.build(arr, node*2, lo, mid) st.build(arr, node*2+1, mid+1, hi) st.tree[node] = st.tree[node*2] + st.tree[node*2+1]}
// Update 将 arr[idx] 更新为 val，O(log n)func (st *SegmentTree) Update(idx, val int) { st.update(1, 0, st.n-1, idx, val)}
func (st *SegmentTree) update(node, lo, hi, idx, val int) { if lo == hi { st.tree[node] = val // 命中叶子 return } mid := (lo + hi) / 2 if idx <= mid { st.update(node*2, lo, mid, idx, val) } else { st.update(node*2+1, mid+1, hi, idx, val) } st.tree[node] = st.tree[node*2] + st.tree[node*2+1]}
// Query 查询区间 [l, r] 的和，O(log n)func (st *SegmentTree) Query(l, r int) int { return st.query(1, 0, st.n-1, l, r)}
func (st *SegmentTree) query(node, lo, hi, l, r int) int { if r < lo || hi < l { return 0 // 无交集 } if l <= lo && hi <= r { return st.tree[node] // 完全包含 } mid := (lo + hi) / 2 return st.query(node*2, lo, mid, l, r) + st.query(node*2+1, mid+1, hi, l, r)}5.2 TypeScript 实现
class SegmentTree { private tree: number[]; private n: number;
constructor(arr: number[]) { this.n = arr.length; this.tree = new Array(4 * this.n).fill(0); this.build(arr, 1, 0, this.n - 1); }
private build(arr: number[], node: number, lo: number, hi: number): void { if (lo === hi) { this.tree[node] = arr[lo]; // 叶子节点 return; } const mid = Math.floor((lo + hi) / 2); this.build(arr, node * 2, lo, mid); this.build(arr, node * 2 + 1, mid + 1, hi); this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1]; }
// 单点更新：将 arr[idx] 设为 val update(idx: number, val: number, node = 1, lo = 0, hi = this.n - 1): void { if (lo === hi) { this.tree[node] = val; return; } const mid = Math.floor((lo + hi) / 2); if (idx <= mid) this.update(idx, val, node * 2, lo, mid); else this.update(idx, val, node * 2 + 1, mid + 1, hi); this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1]; }
// 区间查询：[l, r] 的和 query(l: number, r: number, node = 1, lo = 0, hi = this.n - 1): number { if (r < lo || hi < l) return 0; // 无交集 if (l <= lo && hi <= r) return this.tree[node]; // 完全包含 const mid = Math.floor((lo + hi) / 2); return this.query(l, r, node * 2, lo, mid) + this.query(l, r, node * 2 + 1, mid + 1, hi); }}
// 使用示例const st = new SegmentTree([2, 5, 1, 4, 9, 3]);console.log(st.query(2, 4)); // 14 → 1+4+9st.update(3, 6); // arr[3] = 6console.log(st.query(2, 4)); // 16 → 1+6+9两个实现都用 1-indexed 数组存储线段树，node*2 和 node*2+1 分别是左右子节点。这是最经典的写法，空间开 4n 是安全的上界。
六、生产验证
PostgreSQL —— 范围统计与 BRIN 索引
PostgreSQL 的 BRIN（Block Range Index）索引在概念上与线段树类似：将表按物理块分组，每个块范围存储最小值和最大值。查询时先通过块范围的摘要信息快速排除不相关的块，减少 I/O。虽然内部实现不是教科书式的线段树，但区间聚合、逐层缩小的思路一脉相承。
Redis —— 有序集合的范围操作
Redis 的有序集合（ZSET）使用跳表实现范围查询 ZRANGE/ZRANGEBYSCORE。跳表在此承担的角色与线段树类似：O(log n) 定位起点，然后顺序遍历区间内的元素。Redis 7.0 还引入了 listpack 优化小集合的存储，本质上是对区间数据结构的场景化选择。
Competitive Programming —— 线段树的实战演练场
线段树在算法竞赛中几乎是必考数据结构。Codeforces 上有大量线段树题目，涵盖区间和、区间最值、区间异或、懒标记等变体。SPOJ 的经典题目如 GSS1（区间最大子段和）展示了线段树处理复杂聚合的能力——每个节点不仅要存区间和，还要存前缀最大值和后缀最大值，合并逻辑比简单求和精巧得多。
七、小结
什么时候用
- 区间聚合查询 + 单点更新：需要频繁查询某个范围的和、最大值、最小值，同时元素在动态变化
- 区间批量更新：配合懒标记，对一个区间统一加值或设值，O(log n) 完成
- 多维度聚合：同一棵线段树可以同时维护和、最大值、最小值等多种聚合信息
- 实时统计面板：监控、运营看板等需要秒级响应的区间统计场景
什么时候别用
- 只有单点查询：不需要区间聚合时，简单数组就够了，线段树的多余开销不划算
- 更新极多、查询极少：如果查询频率远低于更新频率，O(n) 遍历 + 缓存结果可能更实际
- 数据规模很小（< 100）：数组遍历 O(n) 在小数据量下常数更小，线段树的递归开销反而拖后腿
- 需要区间最值且不需要更新：静态数据用 Sparse Table 预处理，查询 O(1) 比线段树更快
八、参考资料
- 线段树 Wikipedia - 数据结构定义与操作复杂度
- Fenwick Tree 论文 - Fenwick, 1994, 树状数组的原始论文
- Lazy Propagation in Segment Trees - 懒标记的详细解释与实现
- PostgreSQL BRIN 索引文档 - Block Range Index 设计原理
- Redis ZSET 实现 - 跳表在有序集合中的应用
支持与分享
如果这篇文章对你有帮助，欢迎支持作者或分享给更多人
部分信息可能已经过时