线段树与树状数组

简介

在算法竞赛与软件开发中，处理动态数组的区间查询与更新问题是一项常见且关键的挑战。例如，我们需要频繁地计算数组中某个连续子数组的和、最大值或最小值，同时数组中的元素可能被随时修改。朴素的方法，如每次查询都遍历区间，在数据量大且操作频繁时会导致无法接受的时间复杂度。线段树（Segment Tree）与树状数组（Binary Indexed Tree, BIT）正是为解决这类“动态区间问题”而生的两种高效数据结构。

线段树是一种基于分治思想的二叉树结构，它将整个数组区间递归地划分为更小的子区间，并将每个区间的聚合信息（如和、最值）存储在相应的树节点中。这种设计使得区间查询和区间更新的时间复杂度都能达到 O(log n)，在单点更新和区间更新之间取得了优雅的平衡。树状数组，又称二叉索引树或 Fenwick Tree，是一种更为精巧的数据结构。它利用二进制索引的巧妙性质，以更少的代码量实现了高效的单点更新与前缀和查询，进而可以高效处理区间和查询。虽然其功能看似是线段树的子集，但其实现简洁、常数小，是解决特定问题的利器。

本页将深入剖析这两种数据结构的原理、实现细节、应用场景，并通过经典例题展示如何运用它们解决实际问题。理解它们的异同与适用边界，将极大提升你解决复杂数据维护问题的能力。

核心概念

线段树原理：区间查询与更新的平衡

线段树的核心思想是“空间换时间”与“分治”。对于一个长度为 n 的数组 nums，我们构建一棵二叉树。树的根节点代表整个区间 [0, n-1]。每个非叶子节点代表一个区间，并将其均分为左右两个子区间，分别由其左右子节点代表。叶子节点则代表长度为1的单个元素区间。

每个树节点不仅存储其代表的区间范围 [l, r]，还存储一个“值” val，这个值是该区间内所有元素根据问题需求聚合的结果，例如区间和、区间最大值等。构建树的过程是自底向上的：先创建叶子节点（其 val 即为原数组元素值），然后内部节点的 val 由其两个子节点的 val 计算得出（例如求和或取最大值）。

区间查询：当需要查询区间 [L, R] 的聚合值时（例如区间和），我们从根节点开始递归。如果当前节点区间 [l, r] 完全包含在查询区间 [L, R] 内，则直接返回该节点存储的 val。如果完全不重叠，则返回一个不影响结果的值（如求和时返回0，求最大值时返回负无穷）。如果部分重叠，则递归查询左右子树，并将结果合并。由于每一层最多访问两个“边界节点”，且树高为 O(log n)，因此查询复杂度为 O(log n)。

区间更新与延迟传播：单点更新是区间更新的特例。对于区间更新（如将 [L, R] 内每个元素都加一个值 delta），如果也采用类似查询的方法，更新所有相关的叶子节点，复杂度会退化为 O(n)。为此，线段树引入了“懒惰标记”（Lazy Propagation）。其思想是，更新时，如果当前节点区间完全包含在目标更新区间内，我们并不立即更新其所有子孙节点，而是将需要更新的值 delta 作为一个“待办任务”记录在该节点的 lazy 标记中，并更新当前节点的 val（如区间和则 val += delta * (r-l+1)）。只有当后续查询或更新需要深入到该节点的子节点时，我们才将 lazy 标记的值“下推”给子节点，并清空当前节点的标记。这种机制确保了更新操作的时间复杂度也维持在 O(log n)。

树状数组原理与实现

树状数组的设计基于一个关键的观察：任何一个正整数都可以表示为若干个2的幂次之和。树状数组定义了一个数组 tree，其下标 i 管理着原数组 nums 中一段特定区间的和。具体来说，下标 i 管理的区间长度为 lowbit(i)，即 i 的二进制表示中最低位的1所对应的值，区间终点是 i，起点是 i - lowbit(i) + 1。

核心操作： 1. lowbit(x)：计算 x & (-x)，用于快速找到管理的区间长度和遍历路径。 2. 单点更新 update(i, delta)：当原数组位置 i 的值增加 delta 时，我们需要更新所有管理包含 i 的区间的 tree 元素。操作是 while i <= n: tree[i] += delta; i += lowbit(i)。这相当于沿着二进制表示不断向高位进位，复杂度 O(log n)。 3. 前缀和查询 query(i)：查询原数组前 i 个元素的和。操作是 ans = 0; while i > 0: ans += tree[i]; i -= lowbit(i)。这相当于不断剥掉二进制表示中的最低位1，复杂度 O(log n)。

通过前缀和，我们可以计算任意区间 [l, r] 的和：query(r) - query(l-1)。树状数组的代码极其简洁，常数开销远小于线段树。然而，其原生形式只支持“单点更新”和“前缀和查询”（进而得到区间和）。通过一些技巧（如差分数组），可以将其扩展以支持“区间更新”和“单点查询”，但原生不支持直接的“区间更新+区间查询”或“区间最值”操作，这是它与线段树的主要功能区别。

实战示例

例题1：区域和检索 - 数组可修改 (LeetCode 307)

这是一个典型的动态区间和问题，要求实现一个类，支持单点更新和区间和查询。下面分别用树状数组和线段树实现。

# 解法一：树状数组 (Binary Indexed Tree)
class NumArrayBIT:
def __init__(self, nums):
"""
初始化树状数组。
:type nums: List[int]
"""
self.n = len(nums)
self.nums = nums[:]  # 保存原数组副本，用于计算增量
self.tree = [0] * (self.n + 1)  # 树状数组下标从1开始
# 初始化构建树状数组，可以视为n次单点更新
for i in range(self.n):
self._update(i, nums[i])
def _lowbit(self, x):
"""计算lowbit值。"""
return x & (-x)
def _update(self, index, delta):
"""
内部更新函数：在树状数组位置 index+1 处增加 delta。
注意：外部接口的 index 是原数组下标，从0开始。
"""
i = index + 1  # 转换为树状数组下标（从1开始）
while i <= self.n:
self.tree[i] += delta
i += self._lowbit(i)
def update(self, index, val):
"""
将原数组索引 index 处的元素更新为 val。
:type index: int
:type val: int
:rtype: None
"""
delta = val - self.nums[index]  # 计算变化量
self.nums[index] = val         # 更新原数组副本
self._update(index, delta)     # 更新树状数组
def _query(self, index):
"""
内部查询函数：计算原数组前 index+1 个元素的和。
"""
i = index + 1
s = 0
while i > 0:
s += self.tree[i]
i -= self._lowbit(i)
return s
def sumRange(self, left, right):
"""
返回原数组中索引 left 和 right 之间（包含两端）的元素总和。
:type left: int
:type right: int
:rtype: int
"""
# 区间和 = 前right+1项和 - 前left项和
return self._query(right) - self._query(left - 1)
# 解法二：线段树 (Segment Tree) - 支持区间和
class SegmentTreeNode:
"""线段树节点类。"""
def __init__(self, l, r, val=0):
self.l = l          # 节点代表的区间左端点（原数组下标）
self.r = r          # 节点代表的区间右端点
self.val = val      # 区间和
self.left = None    # 左子节点
self.right = None   # 右子节点
class NumArraySegTree:
def __init__(self, nums):
"""
初始化并构建线段树。
:type nums: List[int]
"""
self.nums = nums
if nums:
self.root = self._build(0, len(nums) - 1)
def _build(self, l, r):
"""递归构建线段树，返回构建好的根节点。"""
if l == r:  # 叶子节点
return SegmentTreeNode(l, r, self.nums[l])
mid = (l + r) // 2
left_child = self._build(l, mid)
right_child = self._build(mid + 1, r)
node = SegmentTreeNode(l, r, left_child.val + right_child.val)
node.left = left_child
node.right = right_child
return node
def update(self, index, val):
"""
单点更新：将索引 index 处的值修改为 val。
"""
delta = val - self.nums[index]
self.nums[index] = val
self._update_node(self.root, index, delta)
def _update_node(self, node, index, delta):
"""递归更新节点值。"""
if node.l == node.r == index:  # 找到目标叶子节点
node.val += delta
return
mid = (node.l + node.r) // 2
if index <= mid:  # 目标在左子树
self._update_node(node.left, index, delta)
else:  # 目标在右子树
self._update_node(node.right, index, delta)
# 回溯更新父节点的区间和
node.val = node.left.val + node.right.val
def sumRange(self, left, right):
"""区间和查询。"""
return self._query_node(self.root, left, right)
def _query_node(self, node, L, R):
"""递归查询区间[L, R]的和。"""
if L <= node.l and node.r <= R:  # 当前节点区间完全包含在查询区间内
return node.val
if node.r < L or node.l > R:    # 当前节点区间与查询区间无重叠
return 0
# 部分重叠，递归查询左右子树
return self._query_node(node.left, L, R) + self._query_node(node.right, L, R)
# 测试代码
if __name__ == "__main__":
nums = [1, 3, 5, 7, 9]
print("原始数组:", nums)
# 测试树状数组
bit_solver = NumArrayBIT(nums)
print("树状数组 - 区间和[1,3]:", bit_solver.sumRange(1, 3))  # 应输出 3+5+7=15
bit_solver.update(2, 6)  # 将 nums[2] 从5改为6
print("更新后树状数组 - 区间和[1,3]:", bit_solver.sumRange(1, 3))  # 应输出 3+6+7=16
# 测试线段树
seg_solver = NumArraySegTree(nums)
print("线段树 - 区间和[0,4]:", seg_solver.sumRange(0, 4))  # 应输出 1+3+6+7+9=26
seg_solver.update(4, 10)  # 将 nums[4] 从9改为10
print("更新后线段树 - 区间和[0,4]:", seg_solver.sumRange(0, 4))  # 应输出 1+3+6+7+10=27

例题2：计算右侧小于当前元素的个数 (LeetCode 315)

这是一个经典的“逆序对”变种问题。我们可以将问题转化为动态维护一个频率数组：从右向左遍历原数组，对于每个元素 nums[i]，我们需要查询当前已遍历元素（即其右侧元素）中，值小于 nums[i] 的元素个数。这个“频率数组”需要支持单点更新（某个值的频率+1）和前缀和查询（查询小于某个值的总频率）。树状数组是解决此问题的完美工具。

class Solution:
def countSmaller(self, nums):
"""
计算每个元素右侧小于它的元素个数。
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return []
# 离散化：将原始数据映射到紧凑的排名上，方便树状数组处理
sorted_unique = sorted(set(nums))
rank_map = {num: i + 1 for i, num in enumerate(sorted_unique)}  # 排名从1开始
n_ranks = len(sorted_unique)
# 初始化树状数组，用于维护每个排名（值）出现的频率
tree = [0] * (n_ranks + 1)
def lowbit(x):
return x & (-x)
def update(idx, delta):
"""在排名 idx 处增加频率 delta"""
while idx <= n_ranks:
tree[idx] += delta
idx += lowbit(idx)
def query(idx):
"""查询排名前 idx 的总频率（即小于等于某值的元素个数）"""
s = 0
while idx > 0:
s += tree[idx]
idx -= lowbit(idx)
return s
result = []
# 从右向左遍历
for num in reversed(nums):
rank = rank_map[num]
# 查询当前小于 num（即排名小于 rank）的元素个数
count = query(rank - 1)
result.append(count)
# 将当前数字加入频率数组
update(rank, 1)
# 由于我们是逆序遍历添加结果，最后需要反转
return result[::-1]
# 测试
if __name__ == "__main__":
sol = Solution()
test_nums = [5, 2, 6, 1]
print("输入数组:", test_nums)
print("右侧小于当前元素的个数:", sol.countSmaller(test_nums))  # 应输出 [2, 1, 1, 0]

对比分析

线段树与树状数组都是解决动态区间问题的利器，但它们在功能、复杂度、实现难度上各有侧重。

最佳实践

• 根据问题特征选择数据结构：面对新问题时，首先分析操作类型。如果只涉及“单点更新+区间和查询”，优先考虑树状数组；如果涉及“区间最值”或“区间更新+区间