高级数据结构

树状数组与线段树

前缀和留下的那个口子

前缀和那篇说过一句话：它不支持修改。 改一个元素，后面所有前缀和都得重算，O(n)。

这句话听起来像个小缺陷。实测一下才知道有多大 —— 数组 10 万个元素，10 万次操作（一半单点修改、一半区间求和，区间在全数组上随机取）。先看基本操作次数，这个数与机器和 JIT 无关：

① 前缀和，每次修改后重算      5.0×10⁹ 次
② 什么都不建，查询时现场累加    1.7×10⁹ 次
③ 树状数组                    2.6×10⁶ 次

🚨 ⚠️ 先看①和②：为了 O(1) 查询而维护前缀和，比什么都不做还慢 3 倍。 因为修改是 O(n)，而修改占了一半的操作。 📌 「预处理换查询速度」这个思路一旦有修改就可能反过来亏。

⭐ 而③把两个操作都做到 O(log n)，操作次数比①少 2000 倍、比②少 658 倍。 这就是这两个数据结构存在的全部理由：不追求某一边最快，而是不让任何一边退化到 O(n)。

⚠️ 换成耗时看也是同一个故事，但②的耗时完全取决于「查询区间有多长」—— 这是个必须写出来的参数：

                              ①        ②        ③
查询区间在全数组上随机取     2487 ms   1032 ms   4.1 ms
查询区间最长只有 1000        2397 ms     17 ms   4.0 ms
                                        ↑ 差 62 倍

👉 ② 是「查询多长就扫多长」，区间一短它就快得离谱 —— 所以离开区间长度谈「现场累加有多慢」是没有意义的。而①和③几乎不受影响：①的成本在修改上，③两边都是 O(log n)。

	区间查询	单点修改	区间修改
普通数组	O(n)	O(1)	O(n)
前缀和	O(1)	O(n)	O(n)
树状数组	O(log n)	O(log n)	需要配差分
线段树	O(log n)	O(log n)	O(log n)（带懒标记）

树状数组：先看那个 `lowbit`

树状数组（Binary Indexed Tree / Fenwick Tree）的全部魔法在一个表达式上：

const lowbit = (x) => x & -x;      // 取出 x 二进制里最低位的那个 1

 6 = 0110   lowbit = 2
 8 = 1000   lowbit = 8
12 = 1100   lowbit = 4

⭐ 为什么 x & -x 能做到：负数用补码表示， -x = ~x + 1。取反让最低位 1 右边的 0 全变成 1，加 1 之后进位一路推到那个位置，结果恰好只有最低位的 1 和 x 相同。

📌 树状数组的下标含义就是：t[i] 存的是 [i - lowbit(i) + 1, i] 这一段的和。 每个位置管一段，段长等于它的 lowbit。所以下标越「整」（二进制末尾 0 越多）管得越宽。

class BIT {
  constructor(n) { this.n = n; this.t = new Array(n + 1).fill(0); }

  add(i, delta) {                                  // 单点加
    for (; i <= this.n; i += i & -i) this.t[i] += delta;
  }

  sum(i) {                                         // 前缀和 [1, i]
    let s = 0;
    for (; i > 0; i -= i & -i) s += this.t[i];
    return s;
  }

  range(l, r) { return this.sum(r) - this.sum(l - 1); }   // ⭐ 区间靠相减
}

⭐ 两个循环的方向正好相反：add 往上跳（+= lowbit，去更新所有覆盖到 i 的段）， sum 往下跳（-= lowbit，把前缀拆成若干段拼起来）。每次至少消掉一个二进制位，所以都是 O(log n)。

🚨 下标必须从 1 开始，从 0 会死循环

这是树状数组唯一的硬性约定，而且违反它的后果非常难看：

lowbit(0) === 0        // 0 & -0 === 0
// 于是 add(0, v) 里的  i += i & -i  变成  i += 0

⚠️ 不是算错，是挂死。 实测 add(0, v) 的循环 50 步都不终止；正常的 add(1, v) 在 n=8 时只要 4 步。

📌 所以对外接口通常这样写：外部用 0 下标，进来先 +1。 🚨 忘了 +1 的症状是页面/程序直接卡住，而不是返回错误答案 —— 这反而是好事，比静默算错好找。

⚠️ 它只会算「前缀」

range(l, r) 是靠 sum(r) - sum(l-1) 凑出来的。这意味着树状数组只适用于可减的运算：求和、异或可以， ⚠️ 求区间最大值不行 —— 最大值没法相减。

📌 要维护区间最值，得改用线段树（或者写一个复杂得多的 BIT 变体，不划算）。

线段树：一棵真的树，装在数组里

线段树的思路直白得多：把区间对半分，每个节点存自己那段的答案。

                [0,7]
            /           \
        [0,3]           [4,7]
       /     \         /     \
    [0,1]   [2,3]   [4,5]   [6,7]

和堆一样用数组存树：节点 p 的左右孩子是 2p 和 2p+1。

class SegTree {
  constructor(a) {
    this.n = a.length;
    this.t = new Array(4 * a.length).fill(0);      // 🚨 4n，不是 2n，见下
    this.lazy = new Array(4 * a.length).fill(0);
    this.build(a, 1, 0, this.n - 1);
  }

  build(a, p, l, r) {
    if (l === r) { this.t[p] = a[l]; return; }
    const m = (l + r) >> 1;
    this.build(a, 2 * p, l, m);
    this.build(a, 2 * p + 1, m + 1, r);
    this.t[p] = this.t[2 * p] + this.t[2 * p + 1];
  }
}

🚨 为什么是 `4n`

这个魔数到处被抄，但很少有人说清。实测 n 从 1 到 5000：

开 2n    4965 个 n 越界，最小 n = 6
开 3n    2215 个 n 越界，最小 n = 36
开 4n    全部通过

⭐ 原因：线段树是满二叉树的形状但不一定是满的。 n 不是 2 的幂时，最底层会分裂出额外的一层，实际用到的最大下标可以逼近 4n —— 实测峰值是 3.91n（n = 4160 时）。

📌 所以 4n 不是保守，是刚好够。 ⚠️ 开 3n 能过很多用例（n < 36 全对），这正是它危险的地方：本地测着没事，交上去在某个规模上突然越界。

区间修改：懒标记

单点修改是「走到叶子，一路更新回来」。区间修改如果也这么做，把 [l, r] 里每个位置都改一遍，就是 O(n)，白搭了。

⭐ 懒标记的想法：改到某个节点时，如果它的区间被完全覆盖，就只改这个节点、在它身上记一笔「我欠孩子一个更新」，不往下走。 等真的需要访问孩子时再把这笔账推下去。

push(p, l, r) {                       // 把 p 的懒标记下推给两个孩子
  if (!this.lazy[p]) return;
  const m = (l + r) >> 1;
  this.t[2 * p]     += this.lazy[p] * (m - l + 1);    // ⭐ 乘以孩子的区间长度
  this.lazy[2 * p]  += this.lazy[p];
  this.t[2 * p + 1] += this.lazy[p] * (r - m);
  this.lazy[2 * p + 1] += this.lazy[p];
  this.lazy[p] = 0;
}

update(ql, qr, d, p = 1, l = 0, r = this.n - 1) {
  if (ql <= l && r <= qr) {                     // ⭐ 完全覆盖：就到这里，不往下
    this.t[p] += d * (r - l + 1);
    this.lazy[p] += d;
    return;
  }
  this.push(p, l, r);                           // 🚨 要往下走了，先还账
  const m = (l + r) >> 1;
  if (ql <= m) this.update(ql, qr, d, 2 * p, l, m);
  if (qr > m)  this.update(ql, qr, d, 2 * p + 1, m + 1, r);
  this.t[p] = this.t[2 * p] + this.t[2 * p + 1];
}

query(ql, qr, p = 1, l = 0, r = this.n - 1) {
  if (ql <= l && r <= qr) return this.t[p];
  this.push(p, l, r);                           // 🚨 查询也要下推
  const m = (l + r) >> 1;
  let s = 0;
  if (ql <= m) s += this.query(ql, qr, 2 * p, l, m);
  if (qr > m)  s += this.query(ql, qr, 2 * p + 1, m + 1, r);
  return s;
}

⚠️ 两个容易漏的点：

query 里也要 push。 只在 update 里下推的话，查询会读到过期的孩子。
下推时要乘区间长度。 lazy 记的是「每个元素加了多少」，节点存的是「这段的和」，所以要乘以元素个数。

🚨 忘记下推的症状

把 push 写成空函数，然后随机对拍（300 轮 × 30 次操作）：

带下推      0 次查询出错
不下推   3109 次查询出错   （例：n=8 查询 [5,5] 得 -10，应为 -16）

⚠️ 注意它不是每次都错：完全覆盖的查询直接读节点值，是对的；只有查询范围切进了某个带标记的节点内部时才读到旧值。

n=8 全区间 +10 之后
  query(0, 7)   完全覆盖 → 读节点值      不下推也对
  query(5, 5)   切进内部 → 读到旧值      得 6，正确 16

📌 但「个别用例错」这个说法偏轻 —— 上面那组随机操作里 出错的查询占了六成（2701 / 约 4536 次查询）。真正的信号是「有些用例过、有些不过」，而不是「只有个别不过」。

⭐ 建议：写完线段树一定要对拍（拿一个 O(n) 的暴力版本，随机生成操作序列比对）。这类数据结构的 bug 靠读代码很难发现，靠对拍几秒钟就能定位。

两个都会 O(log n)，选哪个

n = 20 万，20 万次混合操作（单点修改 + 区间求和）：

树状数组   7 ms
线段树    55 ms      ← 7.5 倍

⭐ 能用树状数组就用树状数组 —— 常数小得多，代码也短得多（上面 BIT 全部实现 12 行，线段树光 update + query 就 20 多行）。

需求	选
单点修改 + 区间求和	⭐ 树状数组
单点修改 + 区间最值	线段树（BIT 做不了，最值不可减）
区间修改 + 区间求和	线段树（懒标记）；或 BIT + 差分
区间修改 + 区间最值	线段树，没别的选择
只查询、不修改	🚨 前缀和 —— 别过度设计

🚨 最后一行值得强调：没有修改就别上这两个。前缀和 O(1) 查询、代码三行，任何时候都比 O(log n) 强。

一个经典应用：数逆序对

排序全景那篇提到过一个恒等式：冒泡的交换次数 = 插入的移动次数 = 数组的逆序对数。暴力数是 O(n²)，用树状数组是 O(n log n)：

function countInversions(a) {
  // ⭐ 先离散化：值域可能很大，但我们只关心大小关系
  const sorted = [...new Set(a)].sort((x, y) => x - y);
  const rank = new Map(sorted.map((v, i) => [v, i + 1]));   // 🚨 从 1 开始

  const bit = new BIT(sorted.length);
  let count = 0;
  for (let i = a.length - 1; i >= 0; i--) {     // ⭐ 从右往左
    count += bit.sum(rank.get(a[i]) - 1);       // 右边已出现的、比它小的个数
    bit.add(rank.get(a[i]), 1);
  }
  return count;
}

⭐ 思路：从右往左扫，每个元素问一句「我右边有几个比我小的」 —— 那就是以它为左端的逆序对数。BIT 在这里当的是「计数器数组的前缀和」。

📌 那个离散化（把值映射成 1..k 的排名）是 BIT 题的标配 —— BIT 的下标就是值，值域太大就得先压缩。

实测 n = 60000：

                  基本操作次数        实测耗时
暴力 O(n²)         1.8×10⁹ 次比较      3101 ms
树状数组           1.9×10⁶ 次跳转      18.6 ms

操作次数比 937×

⚠️ 200 组随机数据与暴力结果完全一致，含空数组、单元素、完全逆序、已排序、以及带重复值的情形（相等不算逆序对）。 📌 归并排序也能数逆序对（在 merge 时统计），复杂度一样 —— 两种解法都值得会，BIT 的写法更短。

⚠️ 面试里的定位

说实话：这两个在面试里出现频率很低。 学习计划那篇把它们列在「可以先跳过」里，现在也不改这个判断。

值得投入的程度按顺序：

必须知道：前缀和不支持修改，需要修改就上树状数组/线段树 —— 一句话
值得会写：树状数组（12 行，lowbit 想通了就不用背）
知道原理即可：线段树的懒标记（能讲清「欠账、用到时再还」就够）
基本不用碰：可持久化线段树、树链剖分之类

📌 ⭐ 更实际的价值在于它们体现的那个思路：当「预处理换查询」因为修改而失效时， 退一步、让两边都变成 O(log n)，往往比死守某一边的 O(1) 划算得多。 文章开头那个「5.0×10⁹ 次 vs 2.6×10⁶ 次」就是这句话最直白的注脚。

下一步

字典树 —— 下一篇，另一种「用结构换查询速度」
前缀和 —— 回去看那张对照表，现在它完整了

练习

勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

307. 区域和检索 - 数组可修改中等⭐ 模板题。前缀和过不了（修改 O(n)），树状数组 12 行搞定
315. 计算右侧小于当前元素的个数困难⭐ 本篇讲的数逆序对的完整版；先离散化，再从右往左扫
493. 翻转对困难和 315 同套路但条件是 nums[i] > 2*nums[j]；⚠️ 离散化时要把 2*x 也放进去
729. 我的日程安排表 I中等⚠️ 用有序集合/二分就够，别一上来上线段树 —— 判断「该不该用」也是考点
732. 我的日程安排表 III困难这题才真的需要线段树（动态开点）或差分 + 有序表求最大重叠
1649. 通过指令创建有序数组困难树状数组当「计数器的前缀和」用，同时数比它小和比它大的
327. 区间和的个数困难前缀和 + 树状数组/归并；⚠️ 先想清楚要统计的是前缀和之差落在区间里

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。