区间查询 · 在数组上反复「问一段、改一点」

有一个数组, 要反复地问「下标 $l$ 到 $r$ 这一段的和或最小值是多少」, 中间还会改某个值。朴素做法每次查询都现场扫一遍 $O(n)$, 查得多就慢。本系列把几种越来越强的解法逐个拆开——每页都能改数组、单步执行, 数组视图与树视图同步高亮, 右侧代码逐行点亮。

motivation · 前缀和

前缀和与一次减法

预处理一个前缀和数组，任意区间和一次减法算出，查询 $O(1)$。代价藏在修改里：改一个值要重算后面一整串前缀和，这正是后面两种结构的动机。

core · 树状数组 BIT

树状数组：用 lowbit 把数组叠成一棵隐形的树

同一个数组，依靠位运算让每个下标负责一段长度恰为 lowbit 的区间，单点改与前缀和查询都只走 $O(\log n)$ 步，两条链恰好相遇一次。

core · 线段树

线段树与区间的递归二分

把整段不断对半切，每个节点缓存自己那段的聚合值。查询时整段被覆盖就直接采用、完全不沾就剪掉、部分重叠才递归，最多碰 $O(\log n)$ 个节点。

advanced · lazy propagation

懒标记与区间修改

修改变成「把一整段都加上 $d$」时逐点改会退化成 $O(n)$。给被整段覆盖的节点打一个懒标记、需要进孩子时才下推，修改与查询双双回到 $O(\log n)$。

advanced · 区间合并

区间合并与最大子段和

线段树节点不止能存一个数。最大子段和让每个节点缓存四个量，合并时取「左后缀加右前缀」这个跨中点的候选，答案才拼得回来。

applications · 真实应用

应用实例：这些结构究竟用在何处

两个可交互的真实场景：用树状数组做实时排行榜求名次，用二维前缀和做图像与热力图的矩形求和，各自与朴素做法并列对照。

选型参考先看聚合本身的代数性质。可逆的聚合 (和、异或) 才谈得上前缀相减: 只读不改用前缀和最省, 要「单点改 + 前缀或区间和」用树状数组最短最快。不可逆但满足结合律并有幺元的聚合 (min、max、gcd、区间赋值、区间最大子段和) 要上线段树, 区间整体修改再配 lazy。若聚合还是幂等的 (min、max、gcd) 且数据静态, 稀疏表能做到 $O(n\log n)$ 预处理、$O(1)$ 查询。几者解决的是同一个问题, 只是在查询、修改与通用性之间取了不同的平衡。

🔗 相关链接

• Fenwick tree · Wikipedia 树状数组的来历 (Peter Fenwick, 1994) 与 lowbit 索引结构的完整推导。
• Segment tree · Wikipedia 线段树的定义、空间 O(n)、查询/修改 O(log n) 的证明与变体一览。
• Segment Tree (含 lazy propagation) · cp-algorithms.com 竞赛向的权威讲解:递归实现、区间修改的 lazy 下推、各种聚合与持久化扩展。
• Fenwick Tree · cp-algorithms.com 树状数组的一维/多维实现、区间修改区间查询的差分技巧。

和别的系列串起来看: 线段树查询时「整段覆盖就剪枝」的策略, 和分支限界的 bound 剪枝是同一种「能整片处理就别细究」的思路; 而堆式实现的线段树按满二叉树下标 (左孩子 $2i$) 寻址, 这套算术又和 二叉堆同源 —— 注意本系列引擎建的是每个内部节点恰有两个孩子的满二叉树, 节点数恒为 $2n-1$, 并非堆式的完全二叉树。