0Pricing
Competitive Programming Academy · 课时

线段树：构建与查询

在 log n 时间内查询区间最小值、最大值或总和

线段树：构建与查询 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

超越树状数组

树状数组擅长求和，但线段树还可以处理最小值、最大值、最大公约数等操作。它是区间查询中灵活实用的主力工具。

覆盖区间的树

每个节点负责数组中的一个区间。根节点覆盖全部数据，子节点不断将区间一分为二，直到叶节点各自保存一个元素。

由数组支持的存储方式

我们将树存储在大小为2n或 4n 的一维数组中。节点 1 是根节点，节点 i 的子节点位于 2i 和 2i+1。

seg = [0] * (2 * n)

叶节点保存数据

在迭代形式中，原始值位于数组的后半部分，索引范围为 n 到 2n-1。

for i in range(n):
    seg[n + i] = a[i]

自底向上构建

每个内部节点都是其两个子节点的combine结果。请从 n-1 向下填充到 1，整棵树就准备好了。

for i in range(n - 1, 0, -1):
    seg[i] = seg[2*i] + seg[2*i+1]

combine 操作

combine函数定义了这棵树的行为。求和时使用加法，求最小值时使用最小值操作，求最大值时使用最大值操作。替换它即可改变查询内容。

def combine(x, y):
    return min(x, y)

单点更新，然后向上回溯

要修改一个值，请设置对应叶节点，然后向根节点移动，并在途中根据两个子节点重新计算每个父节点。

i += n
seg[i] = value
while i > 1:
    i //= 2
    seg[i] = combine(seg[2*i], seg[2*i+1])

查询半开区间

区间查询从两端开始扫描，将边界节点逐步合并到答案中。该区间是半开区间，包含 l，但不包含 r。

迭代查询循环

让 l 和 r 相向移动。当某个索引处于奇数边界时，请先将该节点计入答案，再移动指针。

while l < r:
    if l & 1: res = combine(res, seg[l]); l += 1
    if r & 1: r -= 1; res = combine(res, seg[r])
    l //= 2; r //= 2

两端都是对数级

构建需要 O(n) 时间，而每次更新和查询需要O(log n)时间。这种平衡正是线段树如此灵活的原因。

注意单位元

请将结果初始化为操作的单位元：求和时为 0，求最小值时为正无穷，求最大值时为负无穷。初始值错误就会导致答案错误。

res = float('inf')

快速检查

在迭代形式的树中，原始数据存放在哪里？

回顾：灵活的区间操作

您构建了线段树：叶节点位于数组后半部分，父节点通过 combine 得到，并且可以用 O(log n) 的时间更新和查询总和、最小值或最大值。🌳

常见问题解答

「线段树：构建与查询」课时是免费的吗？

是的 — 「线段树：构建与查询」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「线段树：构建与查询」这节课中我会学到什么？

在 log n 时间内查询区间最小值、最大值或总和 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

「线段树：构建与查询」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 用于前缀和的树状数组
  2. 使用 BIT 计算逆序对
  3. 线段树：构建与查询
  4. 区间更新的延迟传播
← 返回 Competitive Programming Academy