树系列第 19 篇：线段树与树状数组——区间问题的树形解法

本文是“树系列”的第 19 篇。前面十几篇里，我们见过 BST、AVL、红黑树、B 树、堆、Trie，它们各自守卫着一类问题：排名、查找、磁盘 IO、取极值、前缀匹配。今天要登场的两位选手有些不同——它们守卫的是区间（range）：给你一个数组，一会儿把某个位置的值改掉，一会儿问某一段连续下标的和（或者最大值、最小值、平均值），这两种操作还要交替出现几十万次。如果每次都老老实实地重新算一遍，程序早就超时了。线段树（Segment Tree）和树状数组（Fenwick Tree / Binary Indexed Tree）就是为此而生的树形解法：它们都把“一段区间”当作树上的一个节点，让一次修改或一次查询只沿着树走 O(log n) 步。本篇会从朴素数组和前缀和的两个极端讲起，然后用图把线段树的建树、单点修改、区间查询、懒标记一步一步拆开，再切换到更轻巧的树状数组，最后用逆序对和扫描线看看它们在真实题目里的威力。

如果你是一路读过来的老朋友，请先在心里把三块地基捡起来：第 3 篇的完全二叉树、第 4 篇的数组存储、第 16 篇的堆的数组技巧。线段树会把这三样东西几乎原封不动地复用一遍——树是静态的完全二叉树，存储用一维数组，父子关系用下标算。如果你对“把树装进数组”这个操作还有任何陌生感，建议先回头把第 4 篇和第 16 篇各读十分钟，再回来面对今天的内容。下面我们先花一小节把地基重新擦亮。

0 先捡回三块地基：完全二叉树、数组存储、堆的数组技巧

0.1 完全二叉树：编号连续是它的灵魂

第 3 篇讲过，完全二叉树是“除了最后一层外每一层都满、最后一层从左到右连续”的二叉树。这句话听起来像是在描述一棵树的形状，但它真正的价值在于编号规则：如果从根开始，一层一层、从左到右编号，那么所有节点的编号是连续的 1、2、3、4……。一棵有 n 个节点的完全二叉树，编号恰好覆盖 1 到 n，中间不会跳号。这个“编号连续”的性质，是后面所有“数组存树”技巧的总开关。

为什么编号必然连续？因为每一层的容量都是上一层的一倍：第 0 层最多 1 个节点，第 1 层最多 2 个，第 2 层最多 4 个，第 k 层最多 2^k 个。只要上一层被填满，下一层的编号就从上一层的末尾接着往下排；即使最后一层不满，只要从左到右连续，编号仍然一气呵成。堆、线段树全都依赖这个性质。

0.2 数组存储：用下标算亲戚

第 4 篇把“树怎么存进内存”这个问题拆开讲过。链式存储需要每个节点带左右指针，指针在内存里乱跳，缓存不友好；而完全二叉树可以放进一维数组：根放在下标 1（或者 0），然后按编号顺序平铺。第 i 号节点的父亲在下标 i >> 1（即 i/2 向下取整），左孩子在 2 * i，右孩子在 2 * i + 1。这样一来，“找孩子”变成一次乘法，“找父亲”变成一次移位，整棵树的亲戚关系全部由算术规则接管，不需要任何指针。

第 16 篇的堆把这个技巧用到了极致：堆就是一棵“住在数组里的完全二叉树”，父节点的值永远不大于（小顶堆）或不小于（大顶堆）孩子。堆的上浮只找父亲、下沉只找较大的孩子，每一轮都只沿一条链走，所以插入和删除都是 O(log n)。你可能已经注意到，堆的操作永远只关心根，从来不需要关心“某个区间里的和是多少”。今天的线段树要往前走一步：节点不止是“最大值”，而是一段连续区间的聚合信息；操作也不只发生在根上，而是可以精确地定位到任意一段区间。

这张图就是“树系列”后半程的路线图：完全二叉树给了形状，数组存储给了地址，堆证明了“数组 + 下标公式”足够支撑完整的数据结构。今天只是把“关心根”升级成“关心任意区间”，方法本质上没有变。

1 问题登场：改一个点，查一段和

1.1 一个具体到能动手算的例子

空谈抽象没有用，我们先定义一个具体的数组。假设我们有 8 个数，下标从 0 到 7：

a = [1, 3, 5, 7, 9, 11, 13, 15]
下标: 0  1  2  3  4  5   6   7

现在你的程序要反复执行两种操作：

1. 单点修改：把 a[3] 加上 5。修改之后，a[3] 从 7 变成 12。
2. 区间查询：问“下标 2 到 7 这一段的元素和是多少”，也就是 a[2] + a[3] + a[4] + a[5] + a[6] + a[7]。

两种操作交替出现：可能先问一次 [2,7]，再改 a[3]，再问 [0,4]，再改 a[6]，再问 [1,7]……一共来上十万次。你要保证每一次都能在很短的时间内回答。

这里有个很容易被忽略的细节：查询的区间是任意的。今天可能问 [2,7]，明天可能问 [0,0]，后天可能问 [4,5]，我们没法提前预知，也就没法针对某几个固定区间做预处理。数据结构要解决的，就是“任意区间”和“任意修改”之间的这场拔河。

1.2 方案一：朴素数组，查询吃亏

最朴素的办法：什么都不预处理，原样保留数组 a。修改当然痛快——a[3] += 5 是一步直接改内存，时间 O(1)。但查询就难看了：要回答 [l, r] 的和，只能从 l 到 r 把元素逐个加起来。区间越长，花的力气越大；最坏情况下问 [0, n-1]，就是一次 O(n) 的全数组扫描。

如果总共有 M 次操作，每次查询都可能是 O(n)，总时间就是 O(n·M)。n 和 M 都是十万级别时，10^10 次加法足以让任何比赛程序超时。而且请注意，这个方案里“修改快”的优势也帮不上忙——查询时我们还是要傻乎乎地把每个元素重新读一遍。数组记得住每个元素，却记不住任何“一段的汇总”，所以每次查询都要从零开始。

// 朴素数组：修改 O(1)，查询 O(n)
const a = [1, 3, 5, 7, 9, 11, 13, 15];

function pointUpdate(pos, delta) {
  a[pos] += delta;
}

function rangeSum(l, r) {
  let sum = 0;
  for (let i = l; i <= r; i++) sum += a[i];
  return sum;
}

1.3 方案二：前缀和，修改吃亏

聪明的读者立刻会想到：既然查询多，那我提前算好前缀和不行吗？定义 pre[i] = a[0] + a[1] + … + a[i]，那么 sum(l, r) = pre[r] - pre[l-1]（当 l = 0 时直接用 pre[r]）。查询变成一次减法，O(1)，漂亮极了。

但代价出在修改上：改一个 a[pos]，从 pos 开始往后的所有前缀和都要跟着变。举个例子，改 a[3] 加 5，那么 pre[3]、pre[4]、pre[5]、pre[6]、pre[7] 全部要加 5——一个修改牵动 O(n) 个位置。如果修改很频繁，这个方案的总时间同样是 O(n·M)，只是把“查询吃亏”换成了“修改吃亏”。

// 前缀和：修改 O(n)，查询 O(1)
const pre = new Array(a.length);
pre[0] = a[0];
for (let i = 1; i < a.length; i++) pre[i] = pre[i - 1] + a[i];

function pointUpdate(pos, delta) {
  a[pos] += delta;
  for (let i = pos; i < a.length; i++) pre[i] += delta; // 后面全部要改
}

function rangeSum(l, r) {
  return l === 0 ? pre[r] : pre[r] - pre[l - 1];
}

1.4 两个极端之间，藏着树的入口

把两个方案并排看，结论非常清晰：数组是“修改 O(1)、查询 O(n)”，前缀和是“修改 O(n)、查询 O(1)”。它们像拔河的两端，谁都赢不了——问题在于它们都只有一种粒度的信息。数组记得的是单个元素，前缀和记得的是从 0 开始的整段前缀，中间没有任何过渡。

如果有一台“信息天平”，我们希望存在一种组织方式，让修改只影响一小部分汇总信息（O(log n) 个），查询也只需要拼凑一小部分汇总信息（O(log n) 个）。换句话说：把数组切成若干段，每一段先算好和；修改时只重算包含该位置的段，查询时把覆盖查询区间的段拼起来。 分段粒度越细，修改越便宜；分段粒度越粗，查询越省事。有没有一种“粗细兼备”的分段方案？

有。答案就是按 2 的幂分级：先有一个覆盖全体的大段，再把大段对半劈成两个中段，中段再对半劈成小段，一直劈到单个元素。这样总共只有 log 层，任意一个位置只属于每一层中的一段（一共 O(log n) 段），任意一个查询区间也总能被 O(log n) 段拼出来。这棵树，就是线段树；而这棵树的“轻量版”，把“对半劈”换成“按 lowbit 劈”，就是树状数组。

1.5 在线与离线：为什么“先改完再查”救不了我们

在进入树形结构之前，值得把一个容易迷惑的问题讲清楚：既然前缀和慢在“修改要牵连后面所有前缀”，那能不能把所有修改攒起来，最后一次性重建前缀和？能，但前提是离线——即所有操作都先执行完，再统一查询。离线场景下，用差分数组可以在 O(n + m) 内完成全部区间加，再 O(n) 重建前缀和，之后每个查询 O(1)，非常优秀，甚至比线段树还快。

但我们的问题设定是在线的：修改和查询交替出现，查询 [2,7] 的时候，程序不知道下一个操作是改还是查，更不可能等所有修改结束再回答。前缀和的 O(n) 修改是“硬伤”，因为它每次都要推翻一大片已算好的结果；而树形结构的全部意义，就在于把“推翻重来”变成“局部修补”：一次修改只触碰 O(log n) 个节点，一次查询也只拼装 O(log n) 个节点，无论操作序列怎么穿插，总时间都稳在 O(M log n)。在线和离线的区别，是理解“为什么要发明树状结构”的一把钥匙：离线的世界可以批量重来，在线的世界只能边走边修。

1.6 分块：树形解法的“近亲”

在跳到线段树之前，还有一条值得知道的中间路线：分块（sqrt decomposition）。把数组切成约 √n 个块，每块长度约 √n，预先算好每块的和。修改一个点：更新元素本身，再更新所在块的块和，O(1)。查询 [l,r]：中间的整块直接取块和，两端的“散块”逐个元素加，最多 O(√n) 个元素，总时间 O(√n)。

分块比朴素数组快了一个数量级（√n 对 n），实现却只有十几行，而且非常灵活——块内可以存任意信息，甚至支持一些不可结合的奇怪操作。它和线段树的关系很微妙：分块是“固定一把尺子量到底”，线段树是“每一层换更细的尺子”。当 n = 10^5 时，√n ≈ 316，而 log n ≈ 17，差近 20 倍；n = 10^6 时差约 60 倍。这就是为什么线段树值得多写几十行代码：它把“两端散块”这个最后的 O(√n) 尾巴，也压缩成了 O(log n)。理解分块，能让你更清楚地看见线段树到底优化了什么。

接下来的三节，我们把线段树从“空想”变成“代码”。

2 线段树直觉：把区间不断二分

2.1 每个节点管一段区间

线段树的核心思想只有一句话：每个节点负责一段连续区间，并把这段区间的“汇总信息”存在节点里。以我们的 8 个元素为例，根节点负责 [0,7]，存的是 8 个数的总和；根节点把区间对半劈开，左孩子负责 [0,3]，右孩子负责 [4,7]；再往下，[0,3] 又劈成 [0,1] 和 [2,3]，[4,7] 劈成 [4,5] 和 [6,7]；最后一层，每个区间只有一个元素，那就是原始数组本身。

为什么一定要对半劈？因为对半劈能保证两件事。第一，树的层数只有 O(log n)：区间长度每下一层就减半，从 n 缩到 1 只需要 log 层。第二，任何一个位置只落在每一层的一个节点里：从根往下，区间一分为二，位置 pos 只会走进其中一半。这两条合起来，就是“修改只影响 O(log n) 个节点”的数学保证。

先看整棵树的形状。用递归树画出来，[0,7] 的线段树长这样：

请盯着这张图看十秒钟，你会注意到三件事。第一，它是一棵二叉树，而且每个内部节点的两个孩子的区间首尾相接：[0,3] 的左孩子是 [0,1]、右孩子是 [2,3]，中间没有空隙，也没有重叠。第二，叶子恰好对应原数组的每个位置，从上到下从左到右就是 a[0] 到 a[7]。第三，任意两个兄弟节点合起来，恰好覆盖父亲的全部区间——这是“合并”能够自底向上进行的前提。

2.2 节点里存什么

节点里存的是“这段区间的汇总”。汇总可以有很多种：

• 区间和：tree[node] = a[l] + a[l+1] + … + a[r]，最经典；
• 区间最大值：tree[node] = max(a[l], …, a[r])；
• 区间最小值、区间乘积、区间异或、区间 gcd：原理一模一样，只是合并公式不同。

为了行文统一，本篇以区间和为主讲。合并公式是 tree[node] = tree[left] + tree[right]。最大值场景只需要把加号换成 Math.max，其余全部逻辑一字不改——这本身就是线段树优雅的地方：树的形状和操作流程是固定的，变的只有“叶子取值”和“合并公式”两处。

如果我们的数据是 [1,3,5,7,9,11,13,15]，那么各节点存的值是：

[0,7]   = 1+3+5+7+9+11+13+15 = 64
[0,3]   = 1+3+5+7            = 16
[4,7]   = 9+11+13+15         = 48
[0,1]   = 1+3                = 4
[2,3]   = 5+7                = 12
[4,5]   = 9+11               = 20
[6,7]   = 13+15              = 28
叶子节点 = 对应的单个元素

2.3 完全二叉树与数组编号

观察图 2.1，线段树其实是一棵近似完全二叉树：每一层从左到右的节点是连续的（虽然 n 不是 2 的幂时，最后一层会有“缺位”）。既然形状上大体是“层内连续、父在子上”，我们就可以复用第 4 篇的数组存储：根放下标 1，节点 i 的左孩子放 2i，右孩子放 2i+1。这就是为什么很多线段树教材都直接说“用 4n 大小的数组存”。后面第 6 节我们会专门证明 4n 的来源，现在你先记住约定：

tree[1]  ：根，负责 [0, n-1]
tree[2i] ：节点 i 的左孩子
tree[2i+1]：节点 i 的右孩子
tree[i>>1]：节点 i 的父亲

注意，线段树和堆有一个区别：堆的数组里每个位置就是“一个元素”，而线段树的数组里每个位置是“一段区间的汇总”，所以同一个元素会在多层里重复出现（叶子里有 a[3]，[2,3] 的和里也有它，[0,7] 的和里还有它）。这不是浪费，而是“预处理”的必然结果——用重复存储换取查询时 O(log n) 的拼装速度。

2.4 为什么“对半劈”就够用

一个自然的问题是：把区间切成几段最好？切成两段、三段，甚至按固定长度切成 k 段，行不行？答案是：对半劈是“信息结构”上最自然的选法，而且它是 O(log n) 的来源。

先证明一件事：任何查询区间 [l,r]，都能被拆成若干个互不相交的树节点区间，而且个数是 O(log n)。证明的思路就是第 5 节将要实现的递归：从根开始，如果当前节点区间与 [l,r] 完全无关，丢弃；如果被完全覆盖，直接收下；如果部分覆盖，则把问题下放给两个孩子。每个“被收下”的节点都对应查询区间的一段，这些段首尾相接、互不重叠，恰好拼出 [l,r]。至于为什么个数是 O(log n)：每一层最多只有常数个“边界节点”需要继续下探，而完整覆盖的节点在本层就收工，所以总访问量正比于层数。这个证明的每个细节，都会在 5.5 节用手算验证一遍。

再说拆分基数。如果区间每次切成 3 段，层数会变成 O(log3 n)，比 O(log2 n) 小一点，但换来两个麻烦：第一，一个位置会同时落在更多“路径”上（每层可能命中 2 个边界节点而不是 1 个），修改的代价反而变大；第二，合并逻辑要处理三份结果，代码复杂度和出错概率直线上升。切成 2 段则每层的“包含关系”最简单——一个位置要么在左，要么在右，绝不脚踏两只船。数据结构设计里有一条朴素的规律：复杂度的底数不是关键，log 的“每层常数”和实现的简洁度才是关键。二分以最小的实现成本拿到 O(log n)，这就是线段树选择二分的原因。

2.5 合并公式的抽象：能合就能建树

前面提到线段树换合并公式就能换功能，这里把这件事说透。线段树要求合并操作满足两条性质：

1. 可结合：op(op(x, y), z) = op(x, op(y, z))。因为节点信息是从两个孩子“两两合并”出来的，合并顺序不同结果必须相同；
2. 有单位元：存在一个元素 e，使得 op(x, e) = op(e, x) = x。因为查询时“完全无关”的节点要返回一个不影响结果的占位值。

满足这两条的操作有一长串：加法（单位元 0）、乘法（单位元 1）、最大值（单位元 -∞）、最小值（单位元 +∞）、gcd（单位元 0）、按位或（单位元 0）、按位与（单位元全 1）、字符串拼接（单位元空串）……统统可以塞进线段树。这也是线段树被称为“通用区间数据结构”的原因：它不关心你的“和”是怎么定义的，只负责把区间拆到合适粒度，再按你的规则合并。

但要注意，可结合不等于可逆。区间和能用“前缀相减”回答，是因为加法有减法；最大值没有“逆运算”，所以树状数组做不了最值。线段树则不需要逆运算——它把所有相关的段正向合并起来，从不做减法（除了把查询拆开时）。这个区别可以概括成一句话：树状数组依赖“可差”，线段树只依赖“可合”。“可合”比“可差”宽松得多，这就是线段树更通用的数学根源。

3 建树：递归自底向上

3.1 递归函数的三段式

线段树的所有核心函数都是同一个套路，我们管它叫“三段式”：

1. 递归出口：当前区间只有一个元素（l == r），直接把它放进 tree[node]；
2. 拆分：取中点 mid = (l + r) >> 1，左孩子递归处理 [l, mid]，右孩子递归处理 [mid+1, r]；
3. 合并：孩子都算完了，tree[node] = tree[2*node] + tree[2*node+1]。

建树（build）是这个套路最直接的体现：先递归到叶子，再在回溯的路上自底向上把和一层层合并上来。整个过程像盖楼：先浇筑最底层的一间间小屋（叶子），然后一层一层往上封顶。

// 线段树数组，下标从 1 开始；n 为元素个数
const tree: number[] = new Array(4 * n).fill(0);

function build(node: number, l: number, r: number): void {
  if (l === r) {
    tree[node] = a[l];
    return;
  }
  const mid = (l + r) >> 1;
  build(node * 2, l, mid);        // 左孩子
  build(node * 2 + 1, mid + 1, r); // 右孩子
  tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

// 入口
build(1, 0, n - 1);

这段代码总共不到十行，但它已经是一个完整的线段树骨架。调用 build(1, 0, 7) 时，程序会先一路扎到 [0,0]、[1,1] 等叶子，把 a[i] 写进对应节点；然后回溯：[0,1] 算出 4，[2,3] 算出 12，[0,3] 算出 16；右边同理算出 20、28、48；最后根节点 [0,7] 得到 64。整个过程每层都把所有区间算一遍，一共 O(n) 次合并。

3.2 建树的执行过程图

如果把 build(1, 0, 7) 的执行顺序画出来，是下面这张“先深后合”的流程图。箭头从上往下是递归深入，从下往上是回溯合并：

3.3 为什么建树是 O(n)

直觉上“递归把每个区间都算一遍”好像挺费，其实每个节点只被创建一次：叶子有 n 个，内部节点大约也有 n 个，总数是 O(n)，每个节点做 O(1) 的加法，总时间 O(n)。请注意，这里的 O(n) 是数组长度的线性，而不是 log 的乘积——虽然每一层都要访问整层节点，但层数只有 log 层，且每层节点数从 n/2、n/4、n/8 快速衰减，等比级数求和收敛到 2n，所以总工作量是线性的。

顺便说一句，线段树建树的“自底向上”和堆的建堆“从最后一个非叶节点下沉”是同一个思想：先保证子树正确，再合并成更大的子树。第 16 篇你背过的“下沉前先确保两个孩子是合法堆”，在这里的等价版本就是“合并前先确保两个孩子已经算好了自己的区间和”。

3.4 当 n 不是 2 的幂：编号会“跳号”

第 3.3 节说建树是 O(n)，但有一个细节我们一直按“n = 8”这个舒服的例子在讲。真实世界里的 n 很少恰好是 2 的幂，比如 n = 6，这时线段树长什么样？

区间 [0,5] 从中间劈开：mid = 2，左孩子 [0,2]，右孩子 [3,5]。[0,2] 再劈成 [0,1] 和 [2,2]；[3,5] 劈成 [3,4] 和 [5,5]；[0,1] 继续劈成 [0,0]、[1,1]，[3,4] 劈成 [3,3]、[4,4]。按照“根 = 1，左孩子 = 2i，右孩子 = 2i+1”的约定，把每个节点的编号标上去：

看出问题了吗？编号 10 和 11 消失了：[3,4] 的两个孩子本该是 12 和 13，它们前面空出了 10、11 两个格子。这是“下标算孩子”的必然代价：当树形不完全规整时，编号会跳跃，数组必须为跳过的位置留白。上例中最大编号是 13，而节点总数只有 2n - 1 = 11 个；如果数组只开 2n = 12，编号 13 就会越界。这就是为什么线段树统一开 4n——不是我们浪费，而是编号跳跃的“天花板”真的需要这么多。第 6 节我们会给出 4n 的严格证明，这里先记住：空洞不可怕，数组开够就行，留白的位置永远不会被访问。

3.5 线段树与堆：同住数组，各怀绝技

学到这里，你可能会问：线段树和堆长得也太像了——都住数组、都用 2i/2i+1、都是完全二叉树，区别到底在哪？区别在三个地方。

第一，节点存的东西不同。堆的节点存“一个元素”，靠父子之间的值序维持结构；线段树的节点存“一段区间的汇总”，元素只在叶子层出现一次，内部节点全是派生信息。第二，关心的位置不同。堆只允许访问根（最大/最小），其他节点对使用者透明；线段树允许访问任意区间，根只是“全体区间”的入口。第三，空间与形状不同。堆的 n 个元素恰好铺满一棵紧凑完全二叉树，2n 数组绰绰有余；线段树为了照顾“任意区间”，节点是区间汇总，形状由二分决定，最坏需要 4n。一句话：堆把数组变成“自动取极值机”，线段树把数组变成“任意区间查询机”——机制同源，使命各异。

4 单点修改：从叶子一路更新到根

4.1 修改的“最小影响原则”

现在看第一种操作：把 a[pos] 加 delta。朴素数组直接改数组，O(1)；线段树里多了一道手续——a[pos] 的值同时被许多个节点“记住”了：叶子 [pos,pos] 记得它，[pos-1,pos] 或 [pos,pos+1] 这类父区间记得它，再往上所有包含 pos 的区间都记得它。为了保持整棵树的信息一致，所有包含 pos 的节点都必须重新计算。

好消息是：从根到叶子的路径每一层只有一个节点包含 pos，所以需要更新的节点恰好是一条链，长度等于树的深度，O(log n) 个。其余的节点（兄弟子树）完全不受影响，碰都不用碰。这就是“最小影响原则”：修改只沿一条链传播，而不是像前缀和那样横扫半个数组。

操作流程分两段：

1. 下潜：从根开始，每次根据 pos 与 mid 的关系决定往左还是往右走，直到叶子 [pos,pos]；
2. 回溯：叶子加完 delta 后，沿着原路返回，每到一层就重新执行 tree[node] = tree[left] + tree[right]。

4.2 修改路径图

以“把 a[3] 加 5”为例，图中加粗的节点就是需要重算的全部节点：叶子 [3,3] 从 7 变 12，父亲 [2,3] 从 12 变 17，再往上 [0,3] 从 16 变 21，最后根 [0,7] 从 64 变 69。整个更新只动了 4 个节点，右边的整棵子树 [4,7] 以及左边的 [0,1] 都安然无恙。

细心的读者会问：既然叶子改了，为什么中间节点不能“直接加 delta”，而要用 tree[left] + tree[right] 重算？两种做法其实都对：因为 delta 恰好同时加在左右孩子之一的区间和上，父亲直接 += delta 也正确。但用“重算”更符合统一模板——以后遇到最大值、最小值、gcd，+= delta 就不灵了，而“取两个孩子的最值”永远是对的。让合并公式成为唯一的信息通道，是线段树扩展性的来源。

4.3 代码

function update(node: number, l: number, r: number, pos: number, delta: number): void {
  if (l === r) {
    tree[node] += delta; // 叶子：原始数组 a[pos] 同步变化
    a[pos] += delta;
    return;
  }
  const mid = (l + r) >> 1;
  if (pos <= mid) {
    update(node * 2, l, mid, pos, delta);
  } else {
    update(node * 2 + 1, mid + 1, r, pos, delta);
  }
  tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 回溯重算
}

// 入口：把 a[3] 加 5
update(1, 0, n - 1, 3, 5);

每一次递归只向一侧下潜，所以递归深度等于树高，update 的时间是 O(log n)。如果你不想在叶子处同步维护 a，也可以只在叶子处 tree[node] += delta，但那样 a 数组就“过期”了；多数实现会保留 a 以便随时读取单点值，两种都可以，保持统一即可。

4.4 走查一次完整更新

我们手把手走一遍 update(1, 0, 7, 3, 5)：

1. 在 [0,7]，mid = 3，pos = 3 不大于 mid，往左走，进入 [0,3]；
2. 在 [0,3]，mid = 1，pos = 3 大于 mid，往右走，进入 [2,3]；
3. 在 [2,3]，mid = 2，pos = 3 大于 mid，往右走，进入 [3,3]；
4. 叶子：tree[11] += 5，从 7 变 12，返回；
5. 回到 [2,3]：tree[5] = tree[10] + tree[11] = 5 + 12 = 17，返回；
6. 回到 [0,3]：tree[2] = tree[4] + tree[5] = 4 + 17 = 21，返回；
7. 回到根：tree[1] = tree[2] + tree[3] = 21 + 48 = 69，结束。

如果你对照 4.2 的图看这七步，会发现程序走过的路径和图上加粗的四个节点完全重合。图是程序的地图，程序是图的翻译——学线段树最好的方式，就是像这样把每一步递归和图上的一条边对上号。

4.5 修改的边界与一致性

单点修改的代码只有十几行，但工程上有几个边界值得养成习惯。第一，参数校验：pos 必须在 [0, n-1] 之内，delta 可以是负数（减法就是加负数），否则递归会走出树的管辖范围。第二，叶子双写的一致性：我们在叶子处同时更新了 tree[node] 和原始数组 a[pos]。如果只更新 tree 不更新 a，那么以后直接读 a 会拿到旧值；如果只更新 a 不更新 tree，查询就会出错。两种策略选一种并坚持到底，推荐双写，因为 a 的 O(1) 随机读太常用了。第三，多组测试数据的清理：线段树数组是复用的，下一组数据开始前必须 tree.fill(0)，否则残留的旧和会悄悄污染新树。第四，递归深度：n = 10^6 时树深约 20 层，n = 10^9 也才 30 层，远小于任何语言的默认栈上限，递归写法完全安全；真正要担心的是“忘了递归出口”导致的无限递归，那比栈溢出更隐蔽。把这四条写进你的模板注释里，线段树就基本不会出工程事故。

5 区间查询：把 [l,r] 拆成 O(log n) 个节点

5.1 三种相遇：全盖、无关、半盖

查询是线段树的真正重头戏。目标：给定 [l, r]，返回这段区间的和。做法依然是递归，但在每个节点上，当前节点区间 [ql, qr] 和查询区间 [l, r] 只可能有三种关系：

1. 完全覆盖（全盖）：l <= ql && qr <= r。当前节点管的整段都在查询范围内，直接返回 tree[node]，不再往下钻；
2. 完全无关：qr < l || r < ql。两个区间没有交集，返回 0（对和来说，0 是“无贡献”的单位元；对最大值来说是 -∞，对最小值来说是 +∞）；
3. 部分覆盖（半盖）：两边有交集但都不完全包含。此时无法直接回答，必须把问题拆给两个孩子：左孩子管 [ql, mid]，右孩子管 [mid+1, qr]，分别递归后把结果合并。

“全盖就直接返回”是查询高效的关键：我们永远不钻到叶子去逐个加元素，而是把查询区间拼装成若干个完整的、已经算好的大段。查询区间越大、节点越靠上，拼装越省力。

5.2 查询拆分配图

现在查询 [2,7] 的和。递归过程会把 [2,7] 拆成四个节点：[2,2]、[3,3]、[4,5]、[6,7]。你看，[4,7] 整个被包含，所以它作为一个整体被直接取走，不用拆开；左边 [0,3] 只包含后半段，所以拆到 [2,3]，而 [2,3] 又只部分包含（[2,3] 整个在 [2,7] 内啊——等等，这里要小心：[2,3] 完全被 [2,7] 覆盖，为什么图中还要拆成 [2,2] 和 [3,3]？）

好问题。答案是：在 [0,3] 处，查询区间 [2,7] 与左孩子 [0,1] 完全无关，与右孩子 [2,3] 完全覆盖——右孩子 [2,3] 应该整体返回 12，根本不需要再拆！真正的拆法是：根 [0,7] 半盖，进 [0,3] 和 [4,7]；[4,7] 全盖，返回 48；[0,3] 半盖，左孩子 [0,1] 无关返回 0，右孩子 [2,3] 全盖返回 12。答案 48 + 12 = 60。

验证一下：a[2]+a[3]+a[4]+a[5]+a[6]+a[7] = 5+12+9+11+13+15 = 65？不对，这里要小心，我们还没做 a[3]+=5 的修改。在初始数据下，5 + 7 + 9 + 11 + 13 + 15 = 60，完全一致。如果先执行了第 4 节的修改，那么 [2,3] 返回 17，[4,7] 仍是 48，答案变成 65。数据结构的魅力就在于此：查询永远读的是当前最新的汇总，修改过多少次它都知道。

5.3 递归决策流程图

把“全盖 / 无关 / 半盖”的判断画成决策树，就是查询函数的路由表：

注意判断顺序：先判无关，再判全盖，最后才拆。先判无关可以避免把“八竿子打不着”的子树白白递归下去；先判全盖则能及时“截胡”，把大段结果直接拿走。这两个判断合起来，保证了每个节点要么 O(1) 返回，要么只下探到有希望的子树上。

5.4 代码

function query(node: number, ql: number, qr: number, l: number, r: number): number {
  if (qr < l || r < ql) return 0;                    // 完全无关
  if (l <= ql && qr <= r) return tree[node];         // 完全覆盖
  const mid = (ql + qr) >> 1;
  const leftSum = query(node * 2, ql, mid, l, r);
  const rightSum = query(node * 2 + 1, mid + 1, qr, l, r);
  return leftSum + rightSum;                         // 部分覆盖：合并
}

// 入口：查询 [2,7]
const ans = query(1, 0, n - 1, 2, 7);

代码和 build 惊人地相似：同样是“叶子出口 + 拆分 + 合并”的三段式，只是出口条件从 l === r 变成了三种区间关系。这也再次印证了线段树的本质：它是一套固定的递归框架，建树、修改、查询只是往框架里填不同的判断和合并逻辑。

5.5 为什么查询只碰 O(log n) 个节点

这是线段树最容易被忽略、也最值得证明的一点。朴素理解“每层走两个分支”，很容易以为查询是 O(log n) 的，但实际上递归会访问不止一条链——像 [2,7] 这种“左右都跨界”的查询，每一层可能同时访问多个节点。严谨的说法是：每一层最多访问 O(1) 个“边界节点”和若干个“全盖节点”，而全盖节点在那一层直接返回，不再产生新访问。

直观解释是这样的：把查询区间的左端点 l 和右端点 r 看作两条“边界线”。递归时，任何一层最多有两个节点与左边界纠缠（一个可能半盖，另一个完全无关），也最多有两个节点与右边界纠缠；其余落在两条边界之间的节点，一旦被完整包含，就立即整体返回。所以每一层访问的节点数是常数（通常不超过 4 个），层数 O(log n)，总访问量 O(log n)。

如果你想要一个更“肌肉记忆”式的验证：n = 8 时 [2,7] 访问了根、[0,3]、[0,1]、[2,3]、[4,7]，一共 5 个节点，约等于 2·log 8；而如果朴素地去数 6 个元素，那要访问 6 个叶子。n 越大，差距越悬殊——当 n = 10^6 时，查询只需要访问几十个节点，而不是上百万个。

5.6 区间查询的常见错误

查询代码看起来短，错误却非常典型，这里列出三个高频坑。

第一个坑是不判“完全无关”导致无限递归。如果把判断顺序写成“先判全盖、再拆”，那么当递归到达一个与查询区间不相交的叶子时，全盖不成立、区间又无法再拆（l == r，mid == l，左孩子还是它自己），函数会一遍遍调用自己直到栈溢出。举一个具体例子：n = 1 时查询 [5,6]（越界区间），如果代码没有“无关返回 0”这一句，query(1,0,0,5,6) 会反复调用 query(2,0,0,5,6)、query(4,0,0,5,6)……永无休止。所以“先判无关”不是优化，而是正确性要求。

第二个坑是单位元选错。区间和用 0 当“无贡献”，因为 x + 0 = x；但同样的代码换到区间最大值时，如果还用 0，查询全负数区间就会得到错误答案——最大值运算的单位元是 -∞（或 -Infinity），最小值是 +∞，乘积是 1，gcd 是 0。换合并公式时，必须同步换单位元，这是线段树“换皮不换骨”最容易漏掉的一步。

第三个坑是0 基与 1 基混用。线段树代码里常见两种约定：递归参数用 0 基闭区间 [l,r]，数组下标用 1 基节点编号；树状数组更是强制 1 基内部下标。一旦入口处忘记转换（比如 update(1, 0, n-1, pos, delta) 里传了 1 基的 pos），整个树的数据就全错位了。建议在模板入口统一封装一层，把 0 基接口暴露给业务代码，内部再换算，从源头消灭这类错误。

5.7 三个边界查询：全区间、单点、空区间

理解查询的边界情况，能帮你验证代码是否正确。第一个是全区间查询 [0, n-1]：根节点被完整覆盖，递归第一层就返回 tree[1]，复杂度 O(1)——这是线段树最舒服的查询。第二个是单点查询 [p, p]：它永远不会命中“全盖”的祖先（因为祖先的区间比 p 宽），只能一路下潜到叶子，复杂度 O(log n)。有趣的是，单点查询和单点修改走的是同一条路径：前者“只读叶子”，后者“改完叶子再回溯重算”。第三个是空区间（l > r）：正规接口应该在入口直接返回单位元，不要交给递归；如果代码没处理，很可能因为“无关判断”的边界写反（比如 qr < l && r < ql）而漏判，产生错误结果。把这三种边界加进你的单元测试，线段树正确性就有了一半保障。

6 复杂度与空间：O(log n) 的代价是 4n 数组

6.1 三笔账：时间、空间、常数

把前五节的内容汇总成一张表：

操作	朴素数组	前缀和	线段树
建树/预处理	O(1)	O(n)	O(n)
单点修改	O(1)	O(n)	O(log n)
区间查询	O(n)	O(1)	O(log n)
空间	n	n	4n

线段树没有在任何单项上“封神”，但它赢在均衡：修改和查询都只有 O(log n)，无论操作序列怎么编排，总时间都是 O(M log n)。这就是数据结构的“木桶原理”——最短的那块板决定了整体的可用性，线段树把两块板都削到了同一高度。

为什么 O(log n) 这么关键？因为 n 和 M 都很大时，log n 的增长慢得惊人：n = 10^6 时 log 2 n ≈ 20，n = 10^9 时也才 30。换句话说，无论数据怎么膨胀，单次操作都只需要几十步，这是“百万次操作秒过”的底气。

6.2 为什么数组要开 4n

这是每个线段树初学者都会问的问题：树的节点明明只有 2n - 1 个（n 个叶子加 n-1 个内部节点），为什么数组要开 4 倍？

要理解这一点，先想清楚一个残酷的事实：线段树并不总是教科书里那种规整的完全二叉树。当 n 恰好是 2 的幂（如 8），区间一路对半劈，树的每一层都住满节点，编号 1 到 15，数组开 2n 都绰绰有余。但当 n 不是 2 的幂（如 5、6、7），情况就变了：递归劈分时，某些层的节点编号会“跳号”，树的形状像一棵缺了右下角的完全二叉树。我们用“下标 2i / 2i+1”存孩子，就必须为这些跳过的编号预留空间，否则可能把两个不同节点挤进同一个格子。

最坏情况出现在 n 比 2 的幂大 1 的时候，比如 n = 9：区间 [0,8] 劈成 [0,4] 和 [5,8]，这两半长度分别为 5 和 4，再往下劈时，左边那半会一直“多出一个小尾巴”，导致树的深度达到 ⌈log2 n⌉ + 1。数学上可以证明：无论 n 是多少，把树补成一棵“能装下 n 个叶子的完全二叉树”后，节点总数不超过 4n - 1。证明思路是这样：

1. 设 h = ⌈log2 n⌉，即 n 向上取到 2 的幂，补全后完全二叉树的高度为 h；
2. 深度为 h 的完全二叉树，总节点数最多为 2^(h+1) - 1；
3. 因为 2^(h-1) < n <= 2^h，所以 2^(h+1) <= 4n；
4. 于是总节点数 2^(h+1) - 1 < 4n，开 4n 一定够。

一句话版本：最坏情况下线段树大约等于“把 n 补成下一个 2 的幂”后那棵完全二叉树的规模，而那个规模不会超过 4n。 开 4 * n 是工程上最省心的选择——不用计算树高，不用处理边界，多出来的空间顶多三倍，对内存完全可接受。

小提示：如果你想省空间，还有一种“迭代线段树”的写法，用 2n 的空间，不需要递归，但代码可读性和扩展性（尤其是懒标记）会打折扣。竞赛和工程里，4n + 递归是接受度最高的组合；本篇也沿用这个约定。

6.3 空间换时间的哲学

4n 的数组里，每个位置存一段区间的汇总，同一个元素被“复制”到 O(log n) 个节点中。这看起来是浪费，其实是典型的空间换时间：我们牺牲了约 4 倍的存储，换来每次操作从 O(n) 降到 O(log n)。数据结构的道路上，这种交易无处不在：Trie 用几十倍的指针空间换字符串前缀查询 O(长度)；哈希表用空桶换 O(1) 平均访问；线段树用重复的汇总换区间操作的“随叫随到”。理解交易，才算理解了为什么“空间 4n”不是一个 bug，而是设计的一部分。

6.4 递归的代价与迭代替代

递归版线段树清晰易懂，但每次函数调用都有栈帧开销，常数因子比纯循环大。幸运的是递归深度只有 log n，栈帧开销在 n 和 M 都很大时依然可以接受；真正需要优化常数时，可以换成迭代线段树。

迭代版的思路是：把 n 向上补成 2 的幂 size，叶子放在数组的 [size, size + n - 1] 区间，根还是 1。单点修改从叶子出发，i >>= 1 一路向上重算父亲；区间查询则用两个指针 l、r 从叶子层同时向上爬，遇到“l 是右孩子”就收下它并右移，遇到“r 是左孩子”就收下它并左移，直到两指针错开。代码比递归版更绕，但避免了递归调用，还只用 2n 空间：

// 迭代线段树（仅单点改 + 区间和）
class IterSegTree {
  private n: number;      // 补全后的 size
  private tree: number[];

  constructor(arr: number[]) {
    this.n = 1;
    while (this.n < arr.length) this.n <<= 1;
    this.tree = new Array(2 * this.n).fill(0);
    for (let i = 0; i < arr.length; i++) this.tree[this.n + i] = arr[i];
    for (let i = this.n - 1; i >= 1; i--) {
      this.tree[i] = this.tree[i * 2] + this.tree[i * 2 + 1];
    }
  }

  update(pos: number, delta: number): void {
    let i = this.n + pos;
    this.tree[i] += delta;
    for (i >>= 1; i >= 1; i >>= 1) {
      this.tree[i] = this.tree[i * 2] + this.tree[i * 2 + 1];
    }
  }

  query(l: number, r: number): number {
    let res = 0;
    let left = l + this.n;
    let right = r + this.n;
    while (left <= right) {
      if (left % 2 === 1) res += this.tree[left++];
      if (right % 2 === 0) res += this.tree[right--];
      left >>= 1;
      right >>= 1;
    }
    return res;
  }
}

这段代码值得细品：left % 2 === 1 表示 left 是右孩子，它没有被父亲完全覆盖，必须单独收下；right % 2 === 0 同理。等你想通为什么这两行成立，就真正理解了“数组 + 下标 = 树”。不过要注意，迭代版一旦加上懒标记，代码量会迅速膨胀，所以教学和面试推荐递归版，追求极致常数再上迭代版。

6.5 边界规模：n = 1、n = 0 与内存上限

两个极端情况值得顺手处理。当 n = 1 时，树只有根节点 [0,0]，4n = 4 的数组绰绰有余，建树、修改、查询都退化成 O(1)，代码不用任何特判——这是 4n 约定带来的额外好处。当 n = 0 时，区间 [0,-1] 没有意义，任何操作都应该在入口直接返回单位元或抛错，不要让递归进入负区间，否则中点和下标的组合会制造出无穷无尽的边界怪例。

内存上限也要心里有数：n = 10^6 时，4n = 4×10^6 个格子；JS/TS 的 number 占 8 字节，约 32MB，完全可接受；C++ 的 int 数组只要 16MB。n 到 10^7 时递归版 4n 就逼近 320MB，需要考虑迭代版 2n 或动态开点。竞赛圈流传一句“线段树四倍数组，空间从来不是问题”是有前提的——前提是 n 在 10^6 以内。

7 懒标记：让“区间加”也飞起来

7.1 新操作：给一整段加上同一个数

到目前为止，我们只支持“改一个点”。现在升级需求：操作变成区间加——把 a[l] 到 a[r] 的每一个元素都加上 v，然后继续查询任意区间的和。朴素做法是循环 l 到 r 逐个调 update，一次区间加 O((r-l+1) log n)，最坏 O(n log n)，跟没优化差不多。

懒标记（lazy propagation，也译作“懒传播”）的思想是：先别急着把 v 加到每个叶子头上，而是把这次区间加“记账”在某个整段的节点上，等将来真的需要知道更细的信息时，再连本带利地下推。 就像你给朋友转了一笔钱，对方暂时没收到明细，只在自己的账本上记了个总数——只要没人问每一笔，总数就够用。

具体规则：当区间加的范围完整覆盖节点 [ql,qr] 时，我们只更新这个节点：

1. tree[node] += v * (qr - ql + 1)：整段每个元素都加 v，区间和要加 v 乘以长度；
2. lazy[node] += v：在这挂一个“欠条”，说明“本节点已经替整段收下 v，但孩子们还不知道”。

孩子们的信息暂时是“过期”的，但没关系——只要将来不深入这个节点，就永远不需要纠正它们。

7.2 懒标记挂账图

假设当前树是初始数据，现在执行“把 [4,7] 整体加 3”。根节点 [0,7] 与 [4,7] 半盖，于是下探到右孩子；右孩子 [4,7] 被完整覆盖，直接挂账：tree[3] += 3×4 = 12，lazy[3] += 3。[4,5]、[6,7] 以及四个叶子一个都没动，它们的值和 lazy 都保持原样。

现在问“[4,7] 的和是多少”，根下探到 [4,7] 时发现它被完整覆盖，直接返回 tree[3] = 60，全程没有碰任何一个叶子，却给出了正确结果。这就是懒标记的威力：把 O(区间长度) 的逐点更新，压成了 O(log n) 的挂账。

7.3 下推：欠条什么时候兑现

挂账总有需要兑现的时候。比如挂完账后，又来一个查询 [6,6] 的单点值：递归走到 [4,7] 时，发现查询区间只覆盖了它的右半部分，必须进入 [6,7]、再进入 [6,6]。可 [4,7] 的孩子们还停留在旧数据，不知道“+3”这回事。此时就必须下推（push down）：

1. 把 lazy[node] 分给两个孩子：lazy[left] += lazy[node]，lazy[right] += lazy[node]；
2. 孩子的区间和也要同步：tree[left] += lazy[node] × 左孩子长度，右孩子同理；
3. 清空当前节点的 lazy[node] = 0——欠条已经兑现给孩子，账本两清。

下推的代价是 O(1)：只更新两个孩子的汇总，不递归、不逐点。只有真正需要进入孩子时，才发生一次下推；不需要时，欠条就一直躺在父节点身上，成本为零。

7.4 代码骨架

我们给线段树加上 lazy 数组，并写全区间加和区间查询。为了聚焦核心，这里用类封装：

class LazySegmentTree {
  private tree: number[];
  private lazy: number[];

  constructor(private n: number) {
    this.tree = new Array(4 * n).fill(0);
    this.lazy = new Array(4 * n).fill(0);
  }

  // 下推：把 node 的懒标记分给两个孩子
  private pushDown(node: number, len: number): void {
    if (this.lazy[node] === 0) return;
    const v = this.lazy[node];
    const left = node * 2;
    const right = left + 1;
    // 左孩子区间长度 = len - len/2（奇数时左长右短）
    const leftLen = len - Math.floor(len / 2);
    this.tree[left] += v * leftLen;
    this.tree[right] += v * Math.floor(len / 2);
    this.lazy[left] += v;
    this.lazy[right] += v;
    this.lazy[node] = 0;
  }

  // 区间加：把 [l,r] 每个元素加 delta
  rangeAdd(node: number, ql: number, qr: number, l: number, r: number, delta: number): void {
    if (qr < l || r < ql) return;                       // 无关
    if (l <= ql && qr <= r) {                           // 全盖：挂账
      this.tree[node] += delta * (qr - ql + 1);
      this.lazy[node] += delta;
      return;
    }
    const mid = (ql + qr) >> 1;
    this.pushDown(node, qr - ql + 1);                   // 半盖：先兑现欠条
    this.rangeAdd(node * 2, ql, mid, l, r, delta);
    this.rangeAdd(node * 2 + 1, mid + 1, qr, l, r, delta);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }

  // 区间查询：与第 5 节几乎一样，只是半盖时先 pushDown
  query(node: number, ql: number, qr: number, l: number, r: number): number {
    if (qr < l || r < ql) return 0;
    if (l <= ql && qr <= r) return this.tree[node];
    const mid = (ql + qr) >> 1;
    this.pushDown(node, qr - ql + 1);
    return this.query(node * 2, ql, mid, l, r)
         + this.query(node * 2 + 1, mid + 1, qr, l, r);
  }
}

对比第 5 节的普通查询，唯一实质性的新增就是两处 pushDown。这也是懒标记的全部秘密：挂账只改当前节点，下推只影响两个孩子，谁需要深入，谁就先兑现欠条。

7.5 走查：挂账 + 查询的完整故事

跟着一个小例子把机制串起来。数据还是初始的 8 个数，执行三步：

1. rangeAdd([4,7], +3)：如 7.2 图所示，tree[3] = 60，lazy[3] = 3，其余不动；
2. 查询 [6,7]：根半盖进 [4,7]；[4,7] 半盖，必须先 pushDown(3)——于是 [4,5] 变成 20+6=26（lazy=3），[6,7] 变成 28+6=34（lazy=3），lazy[3] 归零；然后进 [6,7]，全盖，返回 34；
3. 再查询 [4,7]：此时 tree[3] 还是 60（下推时它自己的 sum 已经包含了 60 吗？注意：下推只是把欠条转给孩子，父节点的 sum 不变，仍是 60），[4,7] 全盖，直接返回 60。

第三步的 60 是正确的：26 + 34 = 60。整个过程中，叶子 [4,4]、[5,5] 始终没有单独更新过，但它们的信息通过 [4,5] 的 lazy 保持正确。懒标记的本质是“信息可以迟一点到位，但绝不丢失”——只要每个节点都遵守“sum 已经包含自己的 lazy、孩子的 sum 可能滞后”，任何时刻查询都能自圆其说。

7.6 懒标记的适用边界

懒标记不是万能的，它要求合并操作满足“可以批量加速”：区间加对区间和是“加 v×长度”，区间加对区间最大值是“加 v”，都支持；但区间赋值（把整段设成 x）需要额外的“是否被覆盖”标记，区间乘加混合则需要维护两个标记并规定下推顺序。反过来，只支持单点改的树状数组就完全没有这些问题——这也是“线段树更强大、但更复杂”的直观体现。下一节出场的树状数组，正是用“放弃通用性”换“极简实现”的典型。

7.7 懒标记遇上区间最值：合并公式决定挂账金额

懒标记最容易写错的地方，不是下推逻辑，而是挂账金额。以“区间加 + 区间最大值”为例：给 [l,r] 每个元素加 v 后，这段的最大值怎么变？答案是直接加 v——因为每个元素都加了同一个数，最大的那个元素加完后仍然最大，最大值从 M 变成 M + v。所以全盖时写的是 tree[node] += v，而不是区间和版本里的 v × 长度。

对比一下两种合并的挂账公式：

维护的信息	区间加 v 后，全盖节点怎么更新	下推时孩子怎么更新
区间和	tree[node] += v × len	孩子的 tree += v × 孩子长度
区间最大值	tree[node] += v	孩子的 tree += v

看到没有？差别只有“要不要乘长度”一处。这背后是一条通则：挂账金额必须等于“批量操作对当前节点汇总值造成的增量”。和是加法对加法，长度会放大；最值是 max 对加法，v 直接穿透。推而广之，如果做“区间赋值 x + 区间和”，就得额外记录“本段是否整体被覆盖”以及覆盖值，否则无法判断旧值该不该加；如果做“区间乘 + 区间加”混合，还得规定先乘后加的固定顺序，因为乘法和加法的分配律只有一种方向。懒标记的复杂度从来不在于“下推”这个动作，而在于合并公式与挂账公式的配对。

7.8 区间加 + 区间查：懒标记线段树与 BIT 差分的选型

你可能已经注意到，8.9 节给树状数组也配了“区间加 + 区间查”的差分方案。两个方案都能做到 O(log n)，怎么选？

先看各自代价。BIT 差分版需要维护两个 BIT，推导公式 (x+1)·Σd[i] - Σ(i·d[i])，代码约三十行，思维负担在“为什么能拆成这样”；懒标记线段树代码约八十行，思维负担在“挂账、下推、长度”三处的配对。从实现量看，BIT 差分明显更轻。

但从扩展性看，线段树全面胜出：同一棵树还能顺便回答区间最大值、区间最小值；如果要加“区间乘”、要可持久化、要动态开点，BIT 差分完全接不住。选型口诀再升级一版：只求“区间加 + 区间和”，用 BIT 差分；但凡附带“最值”或“更花哨的区间操作”，老实上懒标记线段树。 还有一条工程经验：面试和竞赛里，线段树模板背熟后，很多人干脆全程线段树，省去“这题 BIT 行不行”的纠结——代价是常数和代码量，换来的是思维带宽。

8 树状数组：用 lowbit 玩转前缀和

8.1 换个角度想问题：前缀和的“后悔药”

第 1 节我们否掉了前缀和，因为它改一个点要连累 O(n) 个前缀。但请再想想：前缀和数组里，pre[i] 管的是 [0, i] 整段；改成“一段和”之后，包含 a[pos] 的段确实很多——但有没有可能让每个段短一点，从而让“包含某个点”的段数降到 O(log n)？

这就是树状数组（Fenwick Tree / Binary Indexed Tree，简称 BIT）的出发点。它给每个下标 i 划了一小段专属区间：bit[i] 管 (i - lowbit(i), i]，也就是从 i - lowbit(i) + 1 到 i 这一小段的和。这里的 lowbit 是“二进制里最低位的 1 所代表的值”，公式是 lowbit(x) = x & -x。比如：

lowbit(1) = 1     （1 的二进制 1，最低位 1 代表 1）
lowbit(2) = 2     （10 → 10）
lowbit(3) = 1     （11 → 1）
lowbit(4) = 4     （100 → 100）
lowbit(6) = 2     （110 → 10）
lowbit(7) = 1     （111 → 1）
lowbit(8) = 8     （1000 → 1000）

直观地说，lowbit(i) 就是“i 的二进制从右往左数，遇到第一个 1 时，这个 1 连同它右边的 0 一起组成的数”。它描述了 i 的“管辖半径”：bit[i] 往回管 lowbit(i) 个元素。i 是奇数时 lowbit = 1，只管自己；i 是 2 的幂时 lowbit = i，管到最前面。

8.2 树状数组的“管辖地图”

以 n = 8 为例，每个 bit[i] 管辖的区间如下：

bit[1] = a[1]                                          （长度 1）
bit[2] = a[1] + a[2]                                   （长度 2）
bit[3] = a[3]                                          （长度 1）
bit[4] = a[1] + a[2] + a[3] + a[4]                     （长度 4）
bit[5] = a[5]                                          （长度 1）
bit[6] = a[5] + a[6]                                   （长度 2）
bit[7] = a[7]                                          （长度 1）
bit[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]  （长度 8）

（这里为了讲下标规律，先按 1 基叙述：原数组 a[1..n]，稍后代码里会处理 0 基到 1 基的转换。）如果你把“谁包含谁”画成树，会得到一棵奇特的二叉树——不，更准确地说是一棵由二进制决定深度的树：bit[i] 的父亲是 i + lowbit(i)。比如 bit[3] 的父亲是 4，bit[4] 的父亲是 8；bit[5] 的父亲是 6，bit[6] 的父亲是 8。父亲的管辖区间恰好由若干个孩子的区间拼成，就像线段树里父亲由左右孩子拼成一样。

这棵“树”和我们熟悉的二叉树很不一样：它有多个根链汇聚到同一个祖先（bit[2] 有 bit[1] 和 bit[3] 两个孩子，但 bit[4] 又同时是 bit[2] 的孩子——等等，这样 bit[4] 就有两个父亲？）。没错，树状数组的图严格说是一棵有向无环图：从“包含关系”看，bit[4] 既包含 bit[2] 又包含 bit[6]；但从“更新路径”看，bit[2] 沿 i += lowbit(i) 走向 4，bit[6] 也走向 8，bit[4] 也走向 8。它不是一棵树，而是一张“小段拼大段”的合并网。我们叫它“树状数组”，只是因为它的更新路径确实呈现出树的跳跃感。

8.3 前缀和查询：沿 lowbit 往左跳

有了管辖地图，查询前缀 sum(1..x) 就变成拼图游戏：从 x 开始，每取一个 bit[x]，就向左跳过 lowbit(x) 个元素，继续取下一个。数学上这是恒等式：

前缀 [1..x] = [x-lowbit(x)+1 .. x] ∪ [x-lowbit(x)-lowbit(x-lowbit(x))+1 .. x-lowbit(x)] ∪ …（直到 0）

白话版：bit[x] 已经替你算好了最右边 lowbit(x) 个元素的和，剩下的前缀交给 x - lowbit(x) 去递归。因为每次至少左移 1 位（其实至少去掉最低位的 1），跳的步数等于二进制里 1 的个数，最多 O(log n)。

以 query(7) 为例（7 的二进制 111，有三个 1）：

7 → 取 bit[7] = a[7]，跳到 6
6 → 取 bit[6] = a[5..6]，跳到 4
4 → 取 bit[4] = a[1..4]，跳到 0，结束
合计 = a[1..7] ✅

区间 [l, r] 的和 = query(r) - query(l-1)，和前缀和公式一模一样——树状数组在“查询”上完全继承了前缀和的优点。

8.4 单点修改：沿 lowbit 往右跳

修改一个点 a[pos] += delta，要更新所有管辖区间包含 pos 的 bit[i]。从管辖地图可以看出，包含 pos 的区间恰好是：从 pos 开始，沿着 i += lowbit(i) 一直跳下去的所有节点。为什么？因为 bit[i] 管的区间右端是 i，左端是 i - lowbit(i) + 1；如果 pos 落在其中，即 i - lowbit(i) < pos <= i，那么 i 恰好是“把 pos 的某些低位清零再加 lowbit”的某种形态。沿着 += lowbit 跳，保证每跳一步都跨过当前最低位的 1，得到的新 i 一定覆盖 pos 且管辖区间严格变大，直到超过 n。

还是用例子说话。修改 1 基下标 3（即 0 基的 a[2]，各位按需换算），路径是 3 → 4 → 8：

3 → 更新 bit[3]（只管 a[3]）
4 → 更新 bit[4]（管 a[1..4]）
8 → 更新 bit[8]（管 a[1..8]）

如果修改 1 基下标 6，路径是 6 → 8：bit[6] 管 a[5..6]，bit[8] 管全段。如果修改 1 基下标 8，路径只有 8 自己。每一跳的 lowbit 至少翻倍（严格说，每次加上 lowbit 后，最低位的 1 会往左移动至少一位），所以步数 O(log n)。

8.5 两幅图背后的同一个 lowbit

细心的读者会发现：查询是往左跳（x -= lowbit(x)），修改是往右跳（i += lowbit(i)），方向相反，但用的是同一个 lowbit。这恰恰是树状数组的精髓——前缀的分解和单点的传播是一对互逆的操作。查询把前缀拆成若干互不相交的管辖段；修改则沿管辖树的边向上传播。两条路径的交集有个漂亮的对称性：query(x) 恰好会访问所有“管辖区间与 [1..x] 的边界有关”的节点，而 update(pos) 恰好访问所有“管辖区间包含 pos”的节点。一左一右，信息流动形成闭环。

8.6 完整代码

代码短到让人怀疑人生——核心只有五行：

class Fenwick {
  private bit: number[];

  constructor(private n: number) {
    this.bit = new Array(n + 1).fill(0); // 1 基，bit[0] 永远不用
  }

  // 单点修改：原数组 0 基 pos 加 delta
  update(pos: number, delta: number): void {
    for (let i = pos + 1; i <= this.n; i += i & -i) {
      this.bit[i] += delta;
    }
  }

  // 前缀查询：返回 a[0..pos] 的和
  queryPrefix(pos: number): number {
    let sum = 0;
    for (let i = pos + 1; i > 0; i -= i & -i) {
      sum += this.bit[i];
    }
    return sum;
  }

  // 区间查询：sum(l, r)，l、r 都是 0 基
  rangeSum(l: number, r: number): number {
    return this.queryPrefix(r) - (l === 0 ? 0 : this.queryPrefix(l - 1));
  }
}

建树有两种方式：一种是逐个元素 update，O(n log n)，代码最省事；另一种是先把原数组“拷贝”进 bit，再对每个 i 做 bit[i + lowbit(i)] += bit[i]，O(n) 完成。对绝大多数题目，O(n log n) 建树已经足够，这里不再展开。

8.7 用我们的例子完整走查

回到最初的数组 [1,3,5,7,9,11,13,15]（0 基），建树后（为节省篇幅只列相关节点）：

bit[1] = a[0] = 1
bit[2] = a[0]+a[1] = 4
bit[3] = a[2] = 5
bit[4] = a[0..3] = 16
bit[5] = a[4] = 9
bit[6] = a[4]+a[5] = 20
bit[7] = a[6] = 13
bit[8] = a[0..7] = 64

查询 [2,7] 用公式 queryPrefix(7) - queryPrefix(1)。先看 queryPrefix(7)：代码从 i = 7 + 1 = 8 开始，而 lowbit(8) = 8，累加 bit[8] 后 i 变成 0，循环结束——所以它只访问 i=8 一个节点，返回整段和 64。再看 queryPrefix(1)：从 i = 2 开始，lowbit(2) = 2，累加 bit[2] 后 i 变成 0，返回 4，即 a[0] + a[1]。两个结果相减：64 - 4 = 60，与线段树答案一致。这里的关键是：内部循环的起点是 pos + 1，而不是 pos，所以 queryPrefix(7) 的起点是 8，绝不是 1 基例子里的 7。

修改 a[3] += 5：0 基 pos=3 转成 1 基 i=4，沿 i += lowbit(i) 更新 4 和 8：bit[4] 从 16 变 21，bit[8] 从 64 变 69。再查 sum(2,7)：queryPrefix(7) 返回 69，queryPrefix(1) 仍是 4，答案 65，与线段树一致。注意 queryPrefix(1) 为什么不受修改影响：a[3] 不在 a[0..1] 内，bit[2] 的管辖区间根本不含它。

这段走查特别容易踩 0 基/1 基换算的坑：如果直接拿 1 基例子里的“7→6→4”套用到 queryPrefix(7)，就会把 i=8 的 lowbit 错算成 1，得到 8→7→6→4 的错误路径，累加出重复结果。防错口诀请背下来：更新往右跳 i += lowbit(i)，查询往左跳 i -= lowbit(i)，管辖段互不相交；0 基 pos 进 BIT 先加 1。

8.8 与线段树正面对比

现在两位选手都出场了，来一场诚实的对比：

维度	线段树	树状数组
核心思想	区间对半劈	lowbit 分段
支持操作	任意可结合运算，区间最值、区间加（懒标记）、区间乘、可持久化	前缀可差分运算（和、乘积、异或），区间最值需特殊处理
单点改 + 区间查	O(log n)	O(log n)
区间改 + 区间查	O(log n)（懒标记）	需差分技巧或维护多棵树
空间	4n	n+1
代码量	中等到复杂	极小
常数	较大（递归）	极小（循环）
调试难度	边界条件多	下标换算容易出错

一句话总结：树状数组是“够用且极简”的选手，线段树是“全能但重装”的选手。 只做单点改 + 区间和/前缀统计时，树状数组完胜；遇到区间最值、懒标记、复杂合并时，线段树几乎是唯一选择。

8.9 树状数组的三张进阶牌

基础版 BIT 已经能解决“单点改 + 区间查”，但它还有三张进阶牌，值得知道。

第一张牌：差分，让区间加也变简单。 维护差分数组 d，其中 d[i] = a[i] - a[i-1]。区间加 [l,r] 变成两次单点改：d[l] += v、d[r+1] -= v，BIT 直接支持。麻烦的是区间查：前缀和 sum(1..x) = Σ d[i]·(x-i+1)，展开成 (x+1)·Σd[i] - Σ(i·d[i])，所以同时维护两个 BIT——一个存 d[i]，一个存 i·d[i]——就能在 O(log n) 内回答任意区间和。代码量翻倍，但换来“区间加 + 区间查”的能力，是竞赛里的常见组合。

第二张牌：O(n) 建树。 逐个 update 是 O(n log n)，如果在意常数，可以先用原数组初始化 bit[i]，再做一次“自底向上的前缀传播”：对每个 i，把 bit[i] 累加给 bit[i + lowbit(i)]（如果它不超过 n）。这和线段树的建树是同构的：小段先算好，再喂给包含它的大段。n = 10^6 时，两次建树的差距肉眼可见，但多数题目 n log n 完全够用。

第三张牌：二维树状数组。 把 BIT 的循环从一层变成两层：for (i = x; i <= n; i += lowbit(i)) for (j = y; j <= m; j += lowbit(j))。单点修改 O(log² n)，子矩阵查询 O(log² n)。二维 BIT 常配合离散化处理二维偏序、网格动态求和，是“树状数组思想”在更高维度的直接推广——lowbit 的跳跃规则在高维依然成立，这是它结构优雅的最好证明。

8.10 名字里的秘密：为什么叫“树状数组”和“二叉索引树”

树状数组有两个常见名字，每个名字都透露了一半真相。“树状数组”强调它的存储形式：一个普通的一维数组，没有指针，没有递归，却因为 lowbit 规则在逻辑上长出了树的结构。“二叉索引树”（Binary Indexed Tree）强调它的索引方式：每个下标 i 的二进制本身就是树的地址——最低位的 1 决定管辖半径，去掉最低位的 1 就找到“前缀分解的下一段”，加上最低位的 1 就找到“管辖传播的下一站”。二进制在这里不是巧合，而是数据结构的“图纸”。

有一个很常见的误区：以为 bit[i] 存的是“a[1] 到 a[i] 的普通前缀和”。不对——bit[i] 只存它管辖的那一小段，比如 bit[6] 存的是 a[5..6] 而不是 a[1..6]。普通前缀和需要 O(n) 次修改才能维持，BIT 把“前缀”拆成了 log 段，每段一个节点，修改只碰 log 个节点。如果你把 BIT 当成“分块前缀和”，很多行为就顺理成章了：查询一路向左拼段，更新一路向右撒播，lowbit 就是每一块的边长。

记住这个画面：BIT 是一串大小按 lowbit 变化的积木，query 从左往右拿积木拼成完整前缀，update 把改动传给它参与的每一块。 积木总数 n 块，任何一块只属于 log 个“大组合”，所以一切操作都是 log。

8.11 lowbit 的位运算为什么是 i & -i

lowbit(i) = i & -i 这行代码看起来像魔法，拆开就一目了然。计算机里的负数用补码表示：-i = ~i + 1，也就是“按位取反再加一”。对 i = 6（二进制 110）来说，~6 是 …111001，加 1 得 …111010（即 -6 的补码）。把 6 和 -6 做按位与：110 & 010 = 010 = 2，恰好是“最低位的 1 及其右边的 0”。为什么一定如此？因为最低位的 1 右边全是 0：取反后这些 0 全变 1，加 1 一路进位，恰好让最低位的 1 恢复成 1、右边的位归零、左边全部取反；与运算只留下最低位那个 1 以及它右边的 0。

两个使用注意：第一，lowbit 只对正整数有意义，所以 BIT 的下标必须从 1 开始——如果从 0 开始，lowbit(0) = 0，i += 0 会死循环。这也是 8.6 代码里 pos + 1 的根源。第二，i & -i 在 JS 里对超过 32 位的整数会先转成 32 位有符号数，n 达到 2^31 时才有风险，工程上 BIT 的 n 根本到不了这个量级，放心用；在 C++ 里用 x & -x 的 int 版同理。

9 应用：从逆序对到扫描线

学了两种结构，当然要看看它们在一线战场上的样子。本节选三个有代表性的应用：树状数组的“成名作”逆序对、线段树的看家本领区间最值、以及扫描线的惊鸿一瞥。最后我们把第 18 篇的并查集拉回来，完成“数组里藏树”这个系列的收官拼图。

9.1 逆序对：树状数组的成名作

逆序对的定义：一个数组里，如果 i < j 且 a[i] > a[j]，就称 (i, j) 是一个逆序对。比如 [5, 2, 6, 1] 里，逆序对是 (5,2)、(5,1)、(2,1)、(6,1)，一共 4 个。暴力的双重循环 O(n²)，n = 10^5 时直接爆炸。树状数组给出 O(n log n) 的经典解法。

思路分三步：

1. 离散化：值域可能很大（比如 10^9），但元素个数只有 n，所以把所有值排序、映射成 1 到 n 的排名。这一步让树状数组的下标从“值”变成“排名”，长度刚好 n；
2. 从左到右扫描：维护一个“已出现频次”的树状数组，update(rank(x), 1) 表示值 x 出现过一次；queryPrefix(rank(x)) 回答“到目前为止，小于等于 x 的数出现了几个”；
3. 计数：当前扫描到第 i 个元素（从 0 开始数），已经插入了 i 个数（下标 0..i-1）。比当前值大的已出现个数 = i - queryPrefix(rank(x))，累加到答案。

为什么这样对？因为逆序对要求“前面的数大于后面的数”，扫描到 x 时，所有已经插进去的数都在 x 左边；其中比 x 大的那些，就与 x 构成逆序对。queryPrefix(rank(x)) 数的是“小于等于 x 的”，用总数减去它，剩下的就是“大于 x 的”。

再手算一遍这个例子，把每一步的 BIT 状态也写出来，你会彻底理解“频次统计”的运作。数组 [5,2,6,1] 离散化成排名 [3,2,4,1]，四步如下（注意代码是先查询、后插入）：

1. i = 0，插入 5（r = 3）：queryPrefix(2) 数“已插入且排名 ≤ 3 的”，BIT 还是空的，得 0；贡献 0 - 0 = 0。随后把排名 3 的位置加 1；
2. i = 1，插入 2（r = 2）：queryPrefix(1) 数“已插入且排名 ≤ 2 的”，只有排名 3 在场，排名 2 还没插入，得 0；贡献 1 - 0 = 1，恰好是逆序对 (5,2)。随后把排名 2 的位置加 1；
3. i = 2，插入 6（r = 4）：queryPrefix(3) 数“已插入且排名 ≤ 4 的”，排名 2、3 都在场，得 2；贡献 2 - 2 = 0，因为 5、2 都比 6 小；
4. i = 3，插入 1（r = 1）：queryPrefix(0) 数“已插入且排名 ≤ 1 的”，得 0；贡献 3 - 0 = 3，即 (5,1)、(2,1)、(6,1)。随后把排名 1 的位置加 1。

合计 0 + 1 + 0 + 3 = 4，与暴力结果一致。现在能看懂代码里的 i - queryPrefix(r - 1) 了：queryPrefix(r-1) 统计的是“已插入元素中排名不超过 r 的个数”，因为当前元素还没插入，它实际上等于“严格小于当前值的个数（若有重复，则再加上已出现的相等值）”；用已插入总数 i 减去它，得到“严格大于当前值的个数”——重复值共享排名，所以“等于”永远不会被错算进逆序对。这个细节（先查后插、用 r-1 而不是 r）是逆序对模板最容易写错的地方，务必对照本例多读两遍。

function countInversions(nums: number[]): number {
  // 离散化
  const sorted = [...new Set(nums)].sort((x, y) => x - y);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));

  const bit = new Fenwick(nums.length);
  let ans = 0;
  nums.forEach((v, i) => {
    const r = rank.get(v)!;
    ans += i - bit.queryPrefix(r - 1); // 已插入的 i 个数中，比 v 大的个数
    bit.update(r - 1, 1);              // 注意 update 内部会 +1 转 1 基
  });
  return ans;
}

如果你熟悉归并排序的逆序对解法，会发现两者殊途同归：归并排序在“合并”时统计跨区间的逆序，树状数组则在“插入”时统计前缀内的逆序。前者是分治，后者是偏序统计——树状数组版更短、更不容易写错，而且天然适配“边插入边查询”的在线场景。

9.2 区间最值：线段树的看家本领

把线段树的合并公式从“+”换成 Math.max，叶子存 a[i]，整棵树立刻变成“区间最大值树”。查询逻辑一行都不用改：无关返回负无穷（-Infinity 或极小值），全盖返回 tree[node]，半盖取左右孩子的最大值。单点修改同样只沿一条链重算。

树状数组做区间最值就比较尴尬：因为最大值不可差分——max(l,r) ≠ max(0,r) - max(0,l-1)，所以“前缀查询”的思路直接失效。虽然经过特殊改造（维护两个方向的 BIT）可以做固定端点查询，但通用性远不如线段树。这个例子很好地划清了两者的能力边界：凡是依赖“减”的运算（和、异或、乘积的逆元），树状数组都能玩；凡是只有“合”没有“拆”的运算（最值、gcd），线段树才是主场。

9.3 扫描线：一句话预告

线段树的另一个经典舞台是扫描线（sweep line）：求平面上若干个矩形的面积并或周长并时，把所有矩形的竖直边按 x 坐标排序，从左到右“扫描”；用线段树维护当前 x 位置被矩形覆盖的 y 方向总长度，每扫过一条边就更新一次覆盖长度，面积增量 = 覆盖长度 × x 的间距。这里的线段树通常是“区间覆盖计数”版本：每个节点记录被覆盖次数和有效长度，配合离散化的 y 坐标，一次扫描就是 O(n log n)。具体实现细节我们留到系列后续或专门的文章，本篇只需要记住一句话：扫描线 = 排序 + 线段树维护覆盖，是“区间问题树形解法”在二维世界的延伸。

这里的线段树和本篇前面讲的有两个差异：一是节点不再存“和”或“最值”，而是存“被覆盖次数”和“有效覆盖长度”，合并公式变成“覆盖次数大于 0 时取整段长，否则取左右孩子之和”；二是 y 坐标必须先离散化，把浮点或稀疏坐标压缩成整数区间，否则线段树的下标无从谈起。扫描线的难度不在线段树本身，而在“把几何问题翻译成区间覆盖问题”的建模能力——这也是为什么先精通线段树、再碰扫描线，是最稳的学习路径。

9.4 与第 18 篇的关系：都是“数组里藏树”

如果你把学过的数据结构摆在一起，会发现一条惊人的暗线：它们都在用数组承载树，用下标代替指针。

• 第 16 篇的堆：heap[i] 的父是 i>>1，孩子是 2i、2i+1，一棵完全二叉树；
• 本篇的线段树：同样的下标规则，但节点存的是区间汇总；
• 本篇的树状数组：bit[i] 的“父亲”是 i + lowbit(i)，一棵按二进制索引的隐式树；
• 第 18 篇的并查集：parent[i] 指向父亲，森林存在数组里，路径压缩让树矮到近乎一层。

四者共享同一个哲学：树的结构信息不靠指针，而靠下标公式和数组内容推导。区别在于“谁是指向谁的”：堆和线段树是“算术定父子”，BIT 是“lowbit 定父子”，并查集是“内容定父子”。所以并查集能动态合并两棵树（改一个 parent 就行），堆和线段树的形状却必须在建树时定死——因为它们的位置就是下标，下标就是身份。

第 18 篇的并查集告诉我们“树可以是动态的”，本篇的两棵树告诉我们“树可以是隐式的”。把这些图景拼起来，你对“为什么数据结构总爱长成树”的理解，会比单独背任何一个算法都深一层：树是把“一次定位”升级成“log 次定位”的通用装置，而数组是它最便宜的家。

9.5 更多应用：动态排名、二维偏序与区间去重

逆序对只是 BIT 应用版图的冰山一角，再补三个高频场景，帮你建立“看到什么信号该上什么结构”的直觉。

动态排名与第 k 小。 BIT 里存的是频次，queryPrefix(x) 返回“排名不超过 x 的元素个数”。要找第 k 小的值，可以二分 x，但更漂亮的做法是“BIT 上倍增”：从最高的 2 的幂开始，逐步尝试累加，找到“累加和刚好不超过 k-1”的最大前缀位置，再 +1 就是答案。因为 BIT 的每个节点正好管一段 lowbit 区间，倍增过程与 lowbit 跳跃天然契合，一次查询 O(log n)。这个技巧是“二分答案”的常数优化版，面试里属于加分项。

二维偏序。 给 n 个点 (x, y)，问有多少对点满足 x_i < x_j 且 y_i < y_j。套路是：按 x 排序，然后从左到右把 y 插进 BIT，每插入一个点，query(y-1) 就给出“之前所有 x 更小且 y 也更小的点”的个数。逆序对其实就是一维偏序的特例——把数组下标当 x、值当 y 而已。理解了这层关系，你就掌握了“排序 + BIT 扫描”这一整类题的骨架。

区间不同数的个数。 问数组里 [l,r] 中有多少个不同的值。经典离线做法：把所有查询按 r 排序，同时维护 last[v] 表示值 v 最近一次出现的位置；扫描到位置 i 时，把 last[a[i]] 处减 1、i 处加 1，再更新 last。这样 BIT 里“每个值只有最靠右的一个 1”，query(r) - query(l-1) 就是 [l,r] 的不同值个数。这个题的精髓是“把‘去重’翻译成‘只保留最新出现位置’”，BIT 只是忠实的计数员。

看完这三个例子，你应该能总结出 BIT 的出场规律：问题能离线、信息能按前缀差分、扫描顺序能人为规定——三者满足时，树状数组几乎总是最优选。

9.6 拿到区间题，先问自己五个问题

把本篇的选型经验压缩成一道五连问，以后拿到区间题可以按顺序自检：

1. 操作是什么？ 只有“单点改 + 区间查”还是也有“区间改”？有区间改且不是简单的差分可解，直接考虑懒标记线段树；
2. 信息是什么？ 区间和、异或、乘积（可差分）→ BIT 候选；最大值、最小值、gcd（不可差分）→ 线段树；
3. 数据范围多大？ n、M 在 10^5 以上，O(n log n) 是硬门槛，O(n²) 直接淘汰；n 只有几百时，暴力反而最快，别为炫技上树；
4. 在线还是离线？ 在线查询（来一个答一个）必须用能随时更新的结构；离线则可以排序、扫描、离散化，BIT 的舞台更大；
5. 要常数还是要通用？ 百万级操作压时限，BIT 的循环胜过递归；题目还附带“区间乘”“可持久化”等怪要求，线段树是唯一活路。

这五问未必每次都有唯一答案，但至少能帮你把“凭感觉选结构”变成“按证据选结构”。数据结构题的正确打开方式，从来不是背模板，而是先翻译需求，再对照能力表——这正是下一节速查表的价值。

10 两种结构对比速查表

临别之前，把整篇文章浓缩成一张可以贴在显示器边上的表。以后做题犹豫“用哪个”的时候，先看这张表，再看题目数据范围。

对比项	线段树（Segment Tree）	树状数组（Fenwick Tree）
核心思想	区间递归对半劈，节点管一段连续区间	按 lowbit 分段，bit[i] 管 (i-lowbit(i), i]
存储形态	4n 数组 + 递归（或迭代）	n+1 数组 + 循环
建树	O(n) 递归自底向上	O(n) 或 O(n log n)
单点修改	O(log n)，沿叶子到根的链重算	O(log n)，沿 i += lowbit(i) 跳
区间查询	O(log n)，全盖/无关/半盖三态递归	O(log n)，query(r) - query(l-1)
区间加（懒标记）	原生支持，O(log n)	需要差分技巧或多棵树
区间最值	原生支持（合并公式换 Math.max）	不支持（最值不可差分）
区间乘积/异或	支持	支持
常数因子	较大（递归调用、4n 内存）	极小（循环、n+1 内存）
代码复杂度	中到高，边界条件多	极低，约 5 行核心
调试难度	数组越界、递归边界易错	0/1 基换算、lowbit 跳跃易错
扩展能力	强：懒标记、区间乘、可持久化、扫描线	弱：受限于前缀差分
典型战场	区间最值、区间加乘、扫描线、可持久化	逆序对、前缀和统计、二维偏序
一句话记忆	“对半劈 + 三态查询”	“lowbit 向左拆前缀、向右传修改”

如果你只能带走一句选型口诀：能差分就用树状数组（短、快、省），不能差分或有区间修改就上线段树（全能、稳、重）。大多数时候，题目会明确暗示：出现“区间最值”“区间赋值”“可持久化”字样，无脑线段树；出现“逆序对”“前缀和”“点更新区间查询”，树状数组是最优解。

10.1 三句口诀与一个仪式

把整篇压缩成三句可以随时背出的口诀：

1. 线段树：对半劈、三态查、叶子改、回溯合——建树与修改的骨架全在这一句里；
2. 懒标记：全盖挂账、半盖下推、sum 乘长、max 直加——挂账金额随合并公式走；
3. 树状数组：lowbit 向左拆前缀、向右传修改，0 基先加一——query 与 update 的防错守则。

最后再送你一个“仪式”：每次写完线段树或 BIT，用随机数据生成一万次操作，与朴素数组对拍。对拍通过的那一刻，你才算真正写完了一个数据结构——不是敲完代码，而是证明了它正确。

11 自测题

题目 7：选型判断

以下四个需求分别选线段树还是树状数组？

1. 单点修改 + 区间和；
2. 单点修改 + 区间最大值；
3. 区间加 + 区间和；
4. 求数组逆序对数量。

查看答案

（1）两者都行，优先树状数组，代码短常数小；（2）必须线段树，最大值不可差分；（3）线段树加懒标记，树状数组需差分+多棵树，麻烦且受限；（4）树状数组是经典最优解，O(n log n) 且实现简洁。

11.8 常见问题（FAQ）

问：线段树能处理负数和大数吗？ 能。合并公式不关心元素符号，负数照常相加、取最值。真正要注意的是溢出：C++ 的 int 在 n、M 都很大时会爆，JS/TS 里超过 2^53 的整数会丢精度，必要时用 64 位整数或 BigInt。单位元也要随数据类型调整，比如求最大值用 -Infinity，而不是随便填一个 0。

问：树状数组是线段树的“子集”吗？ 可以这样理解，但要说得精确：BIT 能解决的问题，基本都能用线段树解决，且线段树还多出区间最值、懒标记等能力；反过来不成立。所以“线段树更强”是对的，但“更强”不代表“更好”——在 BIT 够用的场景里，BIT 的代码量、常数、内存全面占优。选型是权衡，不是站队。

问：为什么树状数组又叫 Fenwick？ 因为它由 Peter M. Fenwick 在 1994 年的一篇论文中系统提出，全称 Fenwick Tree。中文语境里“树状数组”和“二叉索引树”两种叫法混用，英文缩写 BIT（Binary Indexed Tree）最常用。名字不重要，lowbit 才是灵魂。

问：值域很大（比如 10^9）但元素很少，怎么办？ 两个办法。一是离散化：把出现的值排序去重，映射成 1 到 m 的排名，BIT 只开 m 大小——逆序对那节已经演示过。二是动态开点线段树：节点不再一次性开 4n，而是用到哪开到哪，配合数组模拟指针，空间 O(操作数 log 值域)。离散化简单可靠，优先用它。

问：懒标记会不会拖慢单点查询？ 不会变慢数量级，但会“顺路清账”：单点查询路径上每个带懒标记的祖先都要下推一次，一次下推 O(1)，整条路径 O(log n)，和普通单点查询同阶。真正要小心的是“查询完忘记下推”或“下推后忘记清零”，那会导致信息重复或丢失，属于状态管理错误，不是性能问题。

问：树状数组就完全不能做区间最值吗？ 严谨地说，不是“绝对不行”，而是“非常别扭”。如果查询端点固定（比如永远问 [1,r] 的最大值），可以维护两个方向的 BIT 分别回答前缀最值和后缀最值；但任意 [l,r] 的最值需要额外构造或退化成 O(log² n) 的复杂方案，而且完全无法支持“区间加 + 区间最值”这类带懒标记的操作。数据结构选型看的是“综合性价比”：最值场景下，线段树用同样的空间和更清晰的逻辑就能拿下，何必为难 BIT。这也再次印证 8.8 的结论：能差分是 BIT 的护城河，不能差分时，护城河就成了围墙。

12 下一篇预告

下一篇是《树系列第 20 篇：哈夫曼树、选型指南与系列总结》，也是整个“树系列”的收官篇。我们会从“最优前缀编码”出发认识哈夫曼树：为什么出现频率越高的字符编码越短、如何用贪心从叶子一路合并出最优树、哈夫曼编码与压缩软件的关系；然后做一次全系列选型指南——BST、AVL、红黑树、B 树、堆、Trie、并查集、线段树、树状数组、哈夫曼树，什么场景该请哪位选手出场，一张总表定乾坤；最后回顾这二十篇里反复出现的主题：树的形状、树的存储、树的遍历、树的平衡，以及“用树换 log”的底层逻辑。第 20 篇见。

13 写在最后

回头看看本篇走过的路：我们从“改一个点、查一段和”这个不起眼的需求出发，先否掉了顾此失彼的朴素数组和前缀和，然后用“把区间对半劈”的直觉建起线段树，亲手实现了建树、单点修改、区间查询，弄清了 4n 空间从哪来；接着用懒标记把区间加也压到 O(log n)，再换一个视角，用 lowbit 造出树状数组，看它怎样用五行代码完成同样的单点改 + 区间查；最后用逆序对、区间最值、扫描线验证了两位选手的战场划分，并与第 18 篇的并查集合流，看见“数组里藏树”这条贯穿系列的红线。

如果只让你带走一句话，请带走这句：线段树和树状数组，都是把“一段区间”变成“树上节点”的装置，用 O(log n) 次拼装代替 O(n) 次枚举。 如果只让你带走一幅图，请带走那张“全盖直接返回”的查询拆分图——它浓缩了区间数据结构全部的效率来源。

最后再强调一次它们的分工：树状数组是“小而美”的极致——五行核心代码，n+1 空间，常数小到可以忽略，在线段树能覆盖的大部分基础场景里都是更优解；线段树是“大而全”的底线——最值、懒标记、动态开点、可持久化，凡是树状数组够不着的地方，它都稳稳接住。真正的强者不是只会一种结构，而是先判断问题的数学性质，再挑选最省力的工具。这，也是数据结构学习的终极心法。

动手建议三件事：第一，用 TypeScript 分别实现普通线段树和树状数组，用随机数据对拍“单点改 + 区间和”，保证两套代码输出完全一致；第二，给线段树加上懒标记，实现区间加 + 区间查，并用暴力程序验证一万次随机操作；第三，用树状数组求一个随机排列的逆序对，和双重循环的结果对拍。三件事做完，这两棵树就真正长在你手上了。

下一篇，《树系列第 20 篇：哈夫曼树、选型指南与系列总结》，我们给二十篇画上句号。第 20 篇见。