Chapter 5 Segment Tree¶
§1 Motivation¶
1.1Application Scenario¶
【场景】给定一个长度可达百万级的数组A[1000000]，需要频繁执行任意区间[L, R]的聚合查询（以区间和为例）。
1.2Naive Implementation¶
最直接的实现方式是遍历区间内的元素逐个累加，代码实现如下：
ElementType Query ( ElementType A[ ], int L, int R )
{
ElementType sum = 0;
for ( int i = L; i <= R; ++i )
sum += A[i];
return sum;
}
- 缺陷：对于高频次的区间查询操作，线性时间复杂度的性能极差，无法满足大规模数据的处理需求。
§2 Structure¶
2.1 Definition¶
【定义】线段树是一棵完全二叉树，树中每个节点对应原数组的一个区间[start, end]：
- 叶子节点：对应区间长度为1，即原数组的单个元素A[i]，为直接存储的数值
- 非叶子节点：对应区间被划分为左右两个子区间，分别对应其左、右孩子节点，存储该区间的聚合结果（以区间和为例，即左右孩子节点的值之和，为动态计算值）
2.2Example Structure¶
以长度为5的数组A[5] = {7,2,5,3,8}为例，对应的线段树结构如下：
- 根节点：对应区间[0,4]，存储区间和25
- 左子树根节点：对应区间[0,2]，存储区间和14；右子树根节点：对应区间[3,4]，存储区间和11
- 递归拆分至叶子节点，分别对应[0](7)、[1](2)、[2](5)、[3](3)、[4](8)
[0,4]=25
/ \
/ \
[0,2]=14 [3,4]=11
/ \ / \
[0,1]=9 [2,2]=5 [3,3]=3 [4,4]=8
/ \
[0,0]=7 [1,1]=2
2.3Array Representation¶
线段树作为完全二叉树，可通过数组高效存储，与二叉堆的存储逻辑一致：
- 定义数组tree[]存储线段树的节点值
-
对于数组中索引为
node的节点： -
左孩子节点索引：
2 * node -
右孩子节点索引：
2 * node + 1 -
空间复杂度：S(N) = O(2N-1) = O(N)，对于长度为N的原数组，线段树仅需线性级别的存储空间。
将上述树映射到 tree[] 数组中（根节点从索引 1 开始）：
节点索引: 1 2 3 4 5 6 7 8 9
tree[node]: 25 14 11 9 5 3 8 7 2
对应区间: [0,4] [0,2] [3,4] [0,1] [2,2] [3,3] [4,4] [0,0] [1,1]
§3 Operations¶
线段树的核心操作包括构建(Build)、区间查询(Query)、单点更新(Update)，所有操作均基于递归实现。·
3.1 Build Operation¶
递归构建完全二叉树：自顶向下拆分区间，直到区间长度为1（叶子节点），直接赋值为原数组对应元素；自底向上合并左右子节点的聚合值，完成非叶子节点的赋值。该操作仅需执行一次，作为预处理步骤。
void Build ( int node, int start, int end )
{
// Base Case: Leaf Node（叶子节点，区间长度为1）
if ( start == end ) {
tree[ node ] = A[ start ];
return;
}
// Recursive Step: Split and Build Children（递归拆分区间，构建左右子树）
int mid = ( start + end ) / 2;
Build ( 2 * node, start, mid );
Build ( 2 * node + 1, mid + 1, end );
// Merge Logic: Sum of children（合并结果，当前节点值为左右孩子之和）
tree[ node ] = tree[ 2 * node ] + tree[ 2 * node + 1 ];
}
-
初始调用：通常从根节点开始，即
Build(1, 0, n-1)（n为原数组长度，根节点索引为1，原数组下标从0到n-1） -
时间复杂度：T(N) = O(N)，线段树共有约2N个节点，每个节点仅被访问并赋值一次，构建操作仅需执行一次。
3.2 Query Operation¶
根据当前节点对应的区间与查询区间[L, R]的重叠关系，分三类情况处理，避免遍历原数组的所有元素，实现对数时间复杂度的区间查询：
1. 无重叠(No Overlap)：当前节点区间完全在查询区间外，对查询结果无贡献，返回聚合操作的单位元（求和操作的单位元为0）
2. 完全重叠(Total Overlap)：当前节点区间完全在查询区间内，直接返回当前节点存储的聚合值，无需继续递归
3. 部分重叠(Partial Overlap)：当前节点区间与查询区间部分相交，递归查询左右子树，合并左右子树的查询结果作为当前节点的返回值
int Query ( int node, int start, int end, int L, int R )
{
// Case 1: No Overlap (Node is completely outside query range)
if ( R < start || end < L ) {
return 0;
}
// Case 2: Total Overlap (Node is completely inside query range)
if ( L <= start && end <= R ) {
return tree[ node ];
}
// Case 3: Partial Overlap (We need to go deeper into both children)
int mid = ( start + end ) / 2;
int left_sum = Query ( 2 * node, start, mid, L, R );
int right_sum = Query ( 2 * node + 1, mid + 1, end, L, R );
return left_sum + right_sum;
}
-
初始调用：
Query(1, 0, n-1, L, R)，从根节点开始查询区间[L, R]的和 -
时间复杂度：T(N) = O(log N)，每次递归最多访问树的两层，线段树的高度为
⌊log N⌋，因此单次查询仅需对数级别的时间，适合高频次区间查询。
以 Query(1, 3) 为例，查询 A[1..3] 的区间和（预期结果: 2+5+3=10）：
【T】完全重叠直接返回 【P】部分重叠继续递归 【N】无重叠返回0
[0,4]=25 【P】
/ \
[0,2]=14 【P】 [3,4]=11 【P】
/ \ / \
[0,1]=9【P】 [2,2]=5【T】 [3,3]=3【T】 [4,4]=8【N】
/ \
[0,0]=7【N】 [1,1]=2【T】
结果 = 标记【T】的节点值相加 = 5 + 3 + 2 = 10
3.3 Update Operation¶
定位到原数组索引idx对应的线段树叶子节点，更新其值为新值val；随后自底向上回溯，更新所有包含该索引的祖先节点的聚合值，保证整棵线段树的聚合结果正确。
void Update ( int node, int start, int end, int idx, int val )
{
// Base Case: Leaf Node found（找到对应索引的叶子节点，完成更新）
if ( start == end ) {
tree[ node ] = val;
return;
}
// Recursive Step: Go left or right depending on where “idx” is（递归定位到对应子树）
int mid = (start + end) / 2;
if ( start <= idx && idx <= mid ) {
// Index is in the left child（索引在左子树，递归更新左子树）
Update ( 2 * node, start, mid, idx, val );
} else {
// Index is in the right child（索引在右子树，递归更新右子树）
Update ( 2 * node + 1, mid + 1, end, idx, val );
}
// Backtracking Step: Update current node based on new children values（回溯更新当前节点值）
tree[ node ] = tree[ 2 * node ] + tree[ 2 * node + 1 ];
}
- 初始调用：
Update(1, 0, n-1, idx, val)，从根节点开始，将原数组idx位置的元素更新为val - 时间复杂度：T(N) = O(log N)，仅需遍历从根节点到目标叶子节点的一条路径（长度为树的高度
log N），回溯更新祖先节点同样仅需log N步，单次更新为对数时间复杂度。
以 Update(idx=1, val=10) 为例，将 A[1] 从 2 更新为 10：
[0,4]
25 → 33 ← 回溯: 22+11=33
/ \
[0,2] [3,4]
14 → 22 ←回溯 11 (不变)
/ \ / \
[0,1] [2,2] [3,3] [4,4]
9 → 17 ←回溯 5(不变) 3(不变) 8(不变)
/ \
[0,0] [1,1]
7(不变) 2→10 ★ 更新点
§4 Additional Notes¶
-
通用聚合操作支持 线段树不仅限于区间和查询，可适用于任意满足区间聚合性质的操作，例如区间最小值(min)、区间最大值(max)、区间平均值等。只需对应修改合并逻辑与无重叠场景的返回值（如区间最小值查询，无重叠时返回无穷大）即可。
-
区间更新与懒传播 对于更通用的区间更新操作（例如给区间
[2, 1000]内的所有元素统一加10），直接逐点更新的时间复杂度会退化为O(N log N)，此时可使用懒传播(Lazy Propagation) 策略优化，将区间更新的时间复杂度也降至O(log N)，该部分内容建议自主学习。