算法 - 12. 线段树
algorithmsdata-structurestreerange-queries
By sko•10/9/2025•15 min read
何时使用线段树
当需要对数组高效执行区间查询和单点更新时使用线段树。虽然最常用于区间和查询,但它可以适用于:
- 区间和查询(经典用例)
- 区间最小值/最大值查询(RMQ)
- 区间 GCD/LCM 查询 用于数学运算
- 满足特定条件的元素数量 在区间内
- 区间更新操作(使用懒惰传播)
- 任何可以通过组合较小区间计算的结合运算(XOR、AND、OR、乘法)
示例问题
实时交易仪表板:您正在构建一个跟踪 100 万只股票 [s₀, s₁, ..., s₉₉₉,₉₉₉] 的实时交易系统,有数千名并发用户。每秒系统必须处理:
- 10,000+ 区间查询:"234,567 到 456,789 号股票的总价值是多少?"
- 5,000+ 价格更新:"345,678 号股票刚从 $120 变为 $125"
- 两者持续且同时发生
前缀和数组失败的原因:
- 前缀和数组提供 O(1) 查询但每次更新需要 O(n)
- n = 1,000,000 且每秒 5,000 次更新 = 每秒 50 亿次操作! 💥
- 系统会在负载下崩溃
使用线段树:
- 构建: O(n) 一次性设置
- 每次查询: O(log n) ≈ 20 次操作
- 每次更新: O(log n) ≈ 20 次操作
- 总负载: (10,000 × 20) + (5,000 × 20) = 每秒 300,000 次操作 ✓
关键点:当有频繁更新和对大数据的频繁查询时,线段树对两种操作都是 O(log n) 变得至关重要。
线段树实际做什么
线段树是一个存储数组片段信息的二叉树。每个节点代表一个区间并存储该区间的操作结果(如求和)。
想象成组织公司部门:
- 根节点:"整个公司的总预算是多少?"
- 内部节点:"这个部门的总预算是多少?"
- 叶节点:"这个特定团队的预算是多少?"
操作如何工作
BUILD 操作 - "分层组织片段"
从数组 [100, 200, 150, 80] 构建线段树时:
- 为每个元素创建叶节点(代表区间 [0,0]、[1,1] 等)
- 每个父节点存储其子节点的和
- 根节点包含整个数组的和
- 树结构使高效区间查询成为可能
[530] <- [0,3]的和
/ \
[300] [230] <- [0,1]和[2,3]的和
/ \ / \
[100] [200] [150] [80] <- 单个元素
0 1 2 3 <- 数组索引QUERY 操作 - "获取任意区间的和"
查询区间 [1, 3] 时:
- 从根节点开始检查当前区间是否与查询区间重叠
- 如果完全包含:返回存储的和
- 如果部分重叠:递归检查两个子节点
- 组合重叠片段的结果
UPDATE 操作 - "更改值并维护所有和"
将索引 2 更新为 180 时:
- 更新索引 2 的叶节点
- 递归更新所有祖先节点
- 每个受影响的节点重新计算其和
- 所有区间和自动保持正确
这些操作何时发生
这些操作根据需要显式调用:
const segTree = SegmentTree.build([100, 200, 150, 80], 0, 3);
// QUERY: 获取索引 1 到 3 的股票和
let portfolioValue = segTree.rangeQuery(1, 3); // 返回 430
// UPDATE: 索引 2 的股票增加到 180
segTree.update(2, 180);
// QUERY: 更新后获取新的和
portfolioValue = segTree.rangeQuery(1, 3); // 返回 460线段树的美妙之处在于一旦构建,无论区间大小如何,查询和更新都需要 O(log n) 时间!
最重要的洞察
每个区间都可以分解为树中存储的 O(log n) 个不重叠片段 - 通过递归地将区间分成两半,我们创建一个树,其中任何区间查询最多访问 O(log n) 个节点,在查询和更新中都实现了对数时间。
记住:算法的天才之处在于预计算特定"类似2的幂"片段的结果。在每个级别,我们只需要决定:"这个片段是完全在内部、完全在外部,还是部分与我的查询区间重叠?"这个每个节点的简单决定自动组合正确的片段以高效回答任何区间查询。
决策框架
线段树涉及三个关键决策:
构建期间(分而治之):
- 递归地将区间分成两半
- 自底向上创建节点
- 组合子节点的值给父节点
查询期间(区间重叠检查):
- 无重叠:完全跳过此子树
- 完全重叠:直接返回此节点的值
- 部分重叠:查询两个子节点并组合
更新期间(传播更改):
- 更新叶节点
- 将父节点重新计算为子节点之和
- 向上传播到根节点
代码
class SegmentTree {
constructor(segmentSum, leftBoundary, rightBoundary) {
// 此节点存储的内容
this.sum = segmentSum;
// 此节点表示的区间 [leftBoundary, rightBoundary] 两端包含
this.leftBoundary = leftBoundary;
this.rightBoundary = rightBoundary;
// 树结构
this.leftChild = null;
this.rightChild = null;
}
// BUILD: 从数组创建树 - O(n) 时间
static build(array, startIndex, endIndex) {
const isSingleElement = startIndex === endIndex;
// DECISION FRAMEWORK: 基本情况 - 单个元素的叶节点
if (isSingleElement) {
const elementValue = array[startIndex];
return new SegmentTree(elementValue, startIndex, endIndex);
}
// DECISION FRAMEWORK: 将区间分成两半
const midpoint = Math.floor((startIndex + endIndex) / 2);
const leftHalfEnd = midpoint;
const rightHalfStart = midpoint + 1;
// 递归构建两半
const leftSubtree = SegmentTree.build(array, startIndex, leftHalfEnd);
const rightSubtree = SegmentTree.build(array, rightHalfStart, endIndex);
// DECISION FRAMEWORK: 组合 - 父节点存储子节点之和
const combinedSum = leftSubtree.sum + rightSubtree.sum;
const parentNode = new SegmentTree(combinedSum, startIndex, endIndex);
// 连接树结构
parentNode.leftChild = leftSubtree;
parentNode.rightChild = rightSubtree;
return parentNode;
}
// UPDATE: 将 array[targetIndex] 更改为 newValue - O(log n) 时间
update(targetIndex, newValue) {
// 边界检查 - 索引必须在此节点的区间内
const indexOutOfBounds = targetIndex < this.leftBoundary ||
targetIndex > this.rightBoundary;
if (indexOutOfBounds) {
// 索引不属于此子树 - 无需更新
return;
}
const isLeafNode = this.leftBoundary === this.rightBoundary;
const leafContainsTarget = isLeafNode &&
(this.leftBoundary === targetIndex);
// DECISION FRAMEWORK: 找到目标叶节点
if (leafContainsTarget) {
this.sum = newValue;
return;
}
// DECISION FRAMEWORK: 哪个子节点包含 targetIndex?
const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
const targetIsInRightHalf = targetIndex > midpoint;
if (targetIsInRightHalf) {
this.rightChild.update(targetIndex, newValue);
} else {
this.leftChild.update(targetIndex, newValue);
}
// DECISION FRAMEWORK: 向上传播更改
const updatedLeftSum = this.leftChild.sum;
const updatedRightSum = this.rightChild.sum;
this.sum = updatedLeftSum + updatedRightSum;
}
// QUERY: 获取区间 [queryStart, queryEnd] 的和 - O(log n) 时间
rangeQuery(queryStart, queryEnd) {
// 边界检查 - 与此节点的区间无重叠
const noOverlap = queryEnd < this.leftBoundary ||
queryStart > this.rightBoundary;
if (noOverlap) {
// 查询区间完全不与此子树重叠
return 0;
}
// 检查查询区间与此节点区间的关系
const exactMatch =
queryStart === this.leftBoundary && queryEnd === this.rightBoundary;
// DECISION FRAMEWORK: 完全重叠 - 使用预计算的和
if (exactMatch) {
return this.sum;
}
// 找到此节点区间的分割点
const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
const leftHalfEnd = midpoint;
const rightHalfStart = midpoint + 1;
// DECISION FRAMEWORK: 确定与子节点的重叠
const queryIsEntirelyInRightHalf = queryStart >= rightHalfStart;
const queryIsEntirelyInLeftHalf = queryEnd <= leftHalfEnd;
if (queryIsEntirelyInRightHalf) {
// 查询只需要右子树
return this.rightChild.rangeQuery(queryStart, queryEnd);
}
if (queryIsEntirelyInLeftHalf) {
// 查询只需要左子树
return this.leftChild.rangeQuery(queryStart, queryEnd);
}
// DECISION FRAMEWORK: 查询跨越两个子节点 - 分割并组合
const leftPortion = this.leftChild.rangeQuery(queryStart, leftHalfEnd);
const rightPortion = this.rightChild.rangeQuery(rightHalfStart, queryEnd);
const totalSum = leftPortion + rightPortion;
return totalSum;
}
}
// === 使用示例: 实时交易系统 ===
// 为演示模拟较小版本的 8 只股票
const stockPrices = [100, 200, 150, 80, 250, 300, 175, 220];
// 构建线段树 - O(n) 一次性成本
console.log("为交易系统构建线段树...");
const tradingSystem = SegmentTree.build(stockPrices, 0, 7);
// 模拟同时发生的快速查询和更新
console.log("\n=== 模拟高频交易活动 ===");
// 来自不同用户的多个区间查询
console.log("\n用户查询(同时发生):");
console.log(`交易员 A - 投资组合 [2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 805
console.log(`交易员 B - 投资组合 [0-3]: $${tradingSystem.rangeQuery(0, 3)}`); // 530
console.log(`交易员 C - 投资组合 [4-7]: $${tradingSystem.rangeQuery(4, 7)}`); // 945
// 实时发生的市场更新
console.log("\n市场更新: 股票 3 从 $80 跃升至 $120");
tradingSystem.update(3, 120);
// 新查询立即反映更改
console.log("\n市场变化后的查询(立即反映):");
console.log(`交易员 A - 投资组合 [2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 845
console.log(`交易员 D - 投资组合 [1-4]: $${tradingSystem.rangeQuery(1, 4)}`); // 690
// 另一个快速更新
console.log("\n市场更新: 股票 5 从 $300 下跌至 $250");
tradingSystem.update(5, 250);
// 更多并发查询
console.log("\n更多用户查询:");
console.log(
`交易员 E - 完整投资组合 [0-7]: $${tradingSystem.rangeQuery(0, 7)}`
); // 1545
console.log(
`交易员 F - 高价值股票 [4-7]: $${tradingSystem.rangeQuery(4, 7)}`
); // 895
// 美妙之处: 所有这些操作每个都花费了 O(log n) 时间!
// 在生产环境中 n = 1,000,000 时,每次查询/更新仍然只需要约 20 次操作疑问解答
常见疑问 #1:"如果树分成 [0,1] 和 [2,3] 这样的片段,我如何查询 [0,2]?没有节点精确存储该区间!"
为什么这看起来不可能
看树结构,您可能会想:
[0,3]
/ \
[0,1] [2,3]
/ \ / \
[0] [1] [2] [3]没有单个节点代表 [0,2]。那么我们如何查询它?
关键洞察:组合多个节点
您不需要为每个可能的区间都有一个单独的节点! 线段树组合多个节点的结果:
// 查询 [0,2] 分解为:
query(0, 2) = query(0, 1) + query(2, 2)
= node[0,1].sum + node[2].sum
= 300 + 150 = 450算法如何处理查询 [0,2]:
- 从根节点 [0,3] 开始 - 查询区间 [0,2] 部分重叠
- 在中点(1)分割查询:
- 左子节点 [0,1]: 查询 [0,1] - 完全重叠,返回和
- 右子节点 [2,3]: 查询 [2,2] - 部分重叠,更深入
- 在 [2,3] 再次分割:
- 左子节点 [2]: 查询 [2,2] - 完全重叠,返回和
- 组合: [0,1] 的和 + [2] 的和 = 答案!
查询 [0,2] 的可视化分解:
查询 [0,2]:
[0,3] "分割查询"
/ \
[0,1]✓ [2,3] "部分"
/ \
[2]✓ [3]✗
返回: [0,1].sum + [2].sum魔法:任何区间 [L,R] 都可以分解为树中已存储的最多 O(log n) 个不重叠片段。每个级别您永远不需要超过 2 个节点,因此即使在 8 元素树中像 [1,6] 这样的查询也最多只触及 2×log₂(8) = 6 个节点。
常见疑问 #2:"为什么不直接使用前缀和数组?如果我维护 prefixSum[i] = 从 0 到 i 的元素之和,我可以用 prefixSum[R] - prefixSum[L-1] 在 O(1) 时间内回答任何区间查询。"
为什么您可能认为前缀和更好
前缀和数组对于区间查询似乎更优:
// 前缀和方法
prefixSums = [0, 100, 300, 450, 530, 780, 1080];
// 查询 [2,5] = prefixSums[6] - prefixSums[2] = 1080 - 300 = 780
// O(1) 查询时间 - 似乎比 O(log n) 更好!这绝对正确...如果您永远不需要更新值。前缀和方法对于频繁查询的静态数组是完美的。
为什么前缀和在更新时失效
问题出现在这里:
// 将索引 2 从 150 更新为 180
// 现在我们需要更新索引 2 之后的所有前缀和:
prefixSums[3] = 480 (原来是 450)
prefixSums[4] = 560 (原来是 530)
prefixSums[5] = 810 (原来是 780)
prefixSums[6] = 1110 (原来是 1080)
// 每次更新都需要 O(n) 时间!对于频繁更新,前缀和成为瓶颈。如果您有 m 次更新和 q 次查询:
- 前缀和: 每次更新 O(n) × m 次更新 = O(m·n) 总计
- 线段树: 每次更新 O(log n) × m 次更新 = O(m·log n) 总计
关键权衡
使用前缀和当:
- 数组是静态的(无更新)或更新很少
- 需要 O(1) 查询时间
- 示例:计算历史数据的累积统计
使用线段树当:
- 查询和更新都很频繁
- 两种操作都可以接受 O(log n)
- 示例:显示实时投资组合价值的实时仪表板
显示效率差异的具体示例
考虑一个有 100 万只股票的交易系统 (n = 1,000,000):
场景:每秒 10,000 次查询和 10,000 次更新
使用前缀和:
- 每次更新: O(n) = 1,000,000 次操作
- 10,000 次更新 = 每秒 100 亿次操作
- 系统崩溃! 💥
使用线段树:
- 每次更新: O(log n) = 约 20 次操作
- 10,000 次更新 = 每秒 200,000 次操作
- 每次查询: O(log n) = 约 20 次操作
- 10,000 次查询 = 每秒 200,000 次操作
- 总计:每秒 400,000 次操作 - 完全可管理! ✓
为什么线段树的结构实现快速更新
魔法在于更新如何传播:
在线段树中更新索引 2:
[1110] <- 只更新这个
/ \
[250] [860] <- 只更新这个
/ \ / \
[100] [150] [180] [80] <- 只更新这个
↑
更改的值
只有 O(log n) 个节点需要更新 - 每个树级别一个!将此与前缀和比较,前缀和中每个后续和都需要更新。树结构将任何更新的"损害半径"限制为从叶节点到根节点的路径。
底线
线段树用稍慢的查询 (O(log n) vs O(1)) 换取显著更快的更新 (O(log n) vs O(n))。当数据频繁变化时,这种权衡是必不可少的。对两种操作的对数保证使线段树成为动态区间查询问题的首选。