什么是线段树
线段树（Segment Tree）是一种二叉树，每个节点维护数组上一个连续区间的聚合信息（区间和、最值、乘积等）。它支持在 O(log n) 时间内完成区间查询与单点/区间更新，是处理”频繁查询 + 频繁修改”场景的利器——前缀和数组虽然查询是 O(1)，但一旦有更新就要整体重建。
基本特性
- 结构上接近完全二叉树，可用数组紧凑存储；
- 每个叶子节点对应一个数组元素，内部节点是左右子节点信息的合并；
- 查询与更新的时间复杂度均为 O(log n)；
- 空间复杂度 O(n)（通常开 4n 或 2 的幂次大小的数组）。
结构示例
对数组 [1, 3, 5, 7, 9, 11] 建区间和线段树：
[0,5](36)
/
[0,2](9) [3,5](27)
/ /
[0,1](4) [2,2](5) [3,4](16) [5,5](11)
/ /
[0,0](1) [1,1](3) [3,3](7) [4,4](9)
三个核心操作
1. 构建（自底向上）
递归建树：叶子节点放数组元素，父节点合并两个子节点。下面以区间和为例：
def build(node, l, r, arr, tree):
if l == r:
tree[node] = arr[l]
return
mid = (l + r) // 2
build(2*node+1, l, mid, arr, tree)
build(2*node+2, mid+1, r, arr, tree)
tree[node] = tree[2*node+1] + tree[2*node+2]
2. 区间查询
查询区间 [q_l, q_r] 时递归下探：
- 当前节点区间完全包含于查询区间 → 直接返回节点值；
- 与查询区间无交集 → 返回不影响结果的值（求和返回 0，求最值返回 ±∞）；
- 否则 → 递归查询左右子树并合并结果。
def query(node, l, r, q_l, q_r, tree):
if r < q_l or l > q_r: # 无交集
return 0
if q_l <= l and r <= q_r: # 完全包含
return tree[node]
mid = (l + r) // 2
left = query(2*node+1, l, mid, q_l, q_r, tree)
right = query(2*node+2, mid+1, r, q_l, q_r, tree)
return left + right
3. 单点更新
找到叶子节点更新值，然后沿路径向上重算所有受影响的父节点：
def update(node, l, r, idx, val, tree):
if l == r:
tree[node] = val
return
mid = (l + r) // 2
if idx <= mid:
update(2*node+1, l, mid, idx, val, tree)
else:
update(2*node+2, mid+1, r, idx, val, tree)
tree[node] = tree[2*node+1] + tree[2*node+2]
区间更新：延迟传播（Lazy Propagation）
如果要把整个区间 [l, r] 都加上某个值，朴素做法是逐点更新到叶子，最坏 O(n log n)。延迟传播的思路是：先给节点打上”待执行”的标记，暂不往下传播，等到查询或再次更新真正需要下探时，才把标记推给子节点。这样区间更新的复杂度也降到了 O(log n)，是线段树用于区间修改场景的关键技术。
迭代式实现（Python / Go）
把树存在大小为 2 * size 的数组里（size 是不小于 n 的 2 的幂），可以用循环代替递归，代码更紧凑、常数更小。
Python
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.size = 1
while self.size < self.n:
self.size <<= 1
self.tree = [0] * (2 * self.size)
for i in range(self.n):
self.tree[self.size + i] = data[i]
for i in range(self.size - 1, 0, -1):
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def update(self, index, value):
pos = self.size + index
self.tree[pos] = value
pos >>= 1
while pos >= 1:
new_val = self.tree[2*pos] + self.tree[2*pos+1]
if self.tree[pos] == new_val:
break
self.tree[pos] = new_val
pos >>= 1
def query(self, l, r):
res = 0
l += self.size
r += self.size
while l <= r:
if l % 2 == 1:
res += self.tree[l]
l += 1
if r % 2 == 0:
res += self.tree[r]
r -= 1
l >>= 1
r >>= 1
return res
Golang
type SegmentTree struct {
tree []int
size int
}
func NewSegmentTree(data []int) *SegmentTree {
n := len(data)
size := 1
for size < n {
size <<= 1
}
tree := make([]int, 2*size)
for i := 0; i < n; i++ {
tree[size+i] = data[i]
}
for i := size - 1; i > 0; i-- {
tree[i] = tree[2*i] + tree[2*i+1]
}
return &SegmentTree{tree: tree, size: size}
}
// Update 单点更新
func (st *SegmentTree) Update(index, value int) {
pos := st.size + index
st.tree[pos] = value
for pos > 1 {
pos >>= 1
newVal := st.tree[2*pos] + st.tree[2*pos+1]
if st.tree[pos] == newVal {
break
}
st.tree[pos] = newVal
}
}
// Query 查询闭区间 [l, r] 的和
func (st *SegmentTree) Query(l, r int) int {
res := 0
l += st.size
r += st.size
for l <= r {
if l%2 == 1 {
res += st.tree[l]
l++
}
if r%2 == 0 {
res += st.tree[r]
r--
}
l >>= 1
r >>= 1
}
return res
}
应用与变种
线段树能解决各类区间操作问题：区间求和、区间最值、区间统计（满足条件的元素个数）、区间覆盖（批量修改）、逆序对计数、扫描线（矩形面积并）等。
常见变种：
- zkw 线段树：非递归实现，常数更小、代码更短；
- 动态开点线段树：按需创建节点，适合值域大但稀疏的数据；
- 可持久化线段树（主席树）：保留历史版本，支持区间第 K 大等查询；
- 二维线段树：处理二维平面上的区间问题。
总结
线段树比前缀和、差分数组实现复杂，但换来了”查询与更新都 O(log n)”的均衡能力，是处理动态区间问题的通用框架。遇到需要频繁混合查询和修改的题目，优先考虑线段树。