区间查询 · 在数组上反复「问一段、改一点」
有一个数组,你要反复地问「下标 l 到 r 这一段的和 / 最小值是多少」,中间还会改某个值。朴素做法每次查询都现场扫一遍 O(n),查得多就慢。这一系列把四种越来越强的解法逐个拆开 —— 每页都能改数组、点单步,看数组视图与树视图同步高亮,右侧代码逐行点亮。
引子：前缀和把区间和压成一次减法
最直接的方案：预处理一个前缀和数组 pre[]，任意区间和 sum(l,r)=pre[r+1]-pre[l] 一步算出，查询 O(1)。但代价藏在修改里——改一个值要重算后面一整串前缀和 O(n)。这正是引出树状数组与线段树这两种「带修改也快」结构的动机。
树状数组：用 lowbit 把数组叠成一棵隐形的树
Fenwick tree / Binary Indexed Tree。同一个数组，依靠位运算 lowbit = i & −i 让每个下标「负责」一段长度恰为 lowbit 的区间，update 与前缀和 query 都只走 O(log n) 步。单步观察 query 沿 i -= lowbit(i) 往左跳、update 沿 i += lowbit(i) 往上爬，数组格子逐个点亮。
线段树：把区间递归二分成一棵树
Segment tree。把 [0,n-1] 不断对半切，每个节点缓存自己那段的聚合值。查询 [l,r] 时从根往下：整段被覆盖就直接采用、完全不沾就剪掉、部分重叠才继续递归，最多碰 O(log n) 个节点；单点修改沿一条根到叶的路径回溯更新。比 BIT 更通用——求和、最小、最大、gcd、区间赋值都能装进去。单步看节点 cover/partial/disjoint 三色高亮。
区间修改：懒标记 lazy propagation
当修改变成「把一整段 [l,r] 都加上 d」，逐个点改会退化成 O(n)。核心思路是延迟执行：给被整段覆盖的节点打一个 lazy 标记记下「这片欠加 d」，先不往下传；等真正需要进入它的孩子时再下推 (push-down)。区间修改与区间查询双双回到 O(log n)。单步看标记怎么挂、怎么在递归经过时下沉。
区间合并：节点存什么，由你定——最大子段和
线段树节点不止能存一个数。最大子段和这类问题，每个节点缓存四个量 sum / pre / suf / best，合并左右孩子时 best 还能取「左后缀 + 右前缀」这个跨中点的候选——这正是「区间合并」的关键：答案横跨子区间边界，要靠边界信息拼回来。建树与查询用同一个 combine，只是查询要从左到右保序合并命中段。单步看四量自底向上拼出，跨中点段在数组上点亮。
应用实例：这些结构究竟用在何处
两个可交互的真实场景：用树状数组做实时排行榜求名次（加入 / 查名次都 O(log n)，整张榜不重排），用二维前缀和做图像 / 热力图的矩形求和（积分图 / OpenCV cv::integral()，任意矩形 4 次查表）。每个 demo 都把「换成朴素做法要多少代价」摆在旁边对照；另附逆序对、扫描线面积并、批量调价等延伸 case。
🔗 相关链接
- 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 树状数组的一维/多维实现、区间修改区间查询的差分技巧。