线段树与树状数组实战：从零构建高性能区间查询引擎

当你需要在百万级数据上执行 区间求和、区间最值 或 动态排名查询 时，暴力遍历的时间复杂度是 O(n)，这在高并发场景下是不可接受的。线段树（Segment Tree）和树状数组（Fenwick Tree / Binary Indexed Tree）是两种经典的数据结构，能将这类操作优化到 O(log n)——数据量从 100 万降到 20 次操作。

这两种结构在实时排行榜、金融风控、游戏服务器、IoT 数据聚合等场景中被广泛使用。本文将从零实现这两种数据结构，对比它们的性能特征，并给出真实业务场景的落地方案。

🚀 一、树状数组（Fenwick Tree）：简洁高效的前缀利器

1.1 核心原理

树状数组由 Peter Fenwick 于 1994 年提出，核心思想是利用 二进制低位（Lowbit） 将数组元素分组，用一个辅助数组 tree[] 维护部分和。每个位置 i 负责管理的区间长度等于 i 的二进制表示中最低位 1 所代表的值。

例如位置 12 = 1100₂，lowbit 是 100₂ = 4，所以 tree[12] 管理原数组中 [9, 12] 这 4 个元素的和。

📌 记住： 树状数组的本质是一种压缩的前缀和结构，它用 O(log n) 的代价维护动态前缀和，同时只使用 O(n) 的空间。

1.2 TypeScript 完整实现

// 树状数组（Fenwick Tree）完整实现
class FenwickTree {
  private tree: number[];
  private n: number;

  constructor(size: number) {
    this.n = size;
    this.tree = new Array(size + 1).fill(0);
  }

  // 计算 lowbit：最低位的 1 及其后面的 0
  private lowbit(x: number): number {
    return x & (-x);
  }

  // 单点更新：将位置 index 的值增加 delta
  // 时间复杂度：O(log n)
  update(index: number, delta: number): void {
    for (let i = index + 1; i <= this.n; i += this.lowbit(i)) {
      this.tree[i] += delta;
    }
  }

  // 前缀查询：求 [0, index] 的和
  // 时间复杂度：O(log n)
  prefixSum(index: number): number {
    let sum = 0;
    for (let i = index + 1; i > 0; i -= this.lowbit(i)) {
      sum += this.tree[i];
    }
    return sum;
  }

  // 区间查询：求 [left, right] 的和
  // 时间复杂度：O(log n)
  rangeSum(left: number, right: number): number {
    return this.prefixSum(right) - this.prefixSum(left - 1);
  }
}

// 使用示例
const fw = new FenwickTree(10);
fw.update(0, 3);  // arr[0] = 3
fw.update(2, 5);  // arr[2] = 5
fw.update(4, 7);  // arr[4] = 7
console.log(fw.rangeSum(0, 4)); // 15 (3 + 0 + 5 + 0 + 7)
console.log(fw.rangeSum(1, 3)); // 5  (0 + 5 + 0)

1.3 支持区间更新的树状数组

标准树状数组只支持单点更新 + 区间查询。通过 差分数组 技巧，我们可以实现区间更新 + 单点查询，甚至区间更新 + 区间查询。

// 支持区间更新 + 区间查询的树状数组（双数组技巧）
class RangeFenwickTree {
  private b1: FenwickTree; // 差分数组的树状数组
  private b2: FenwickTree; // 辅助数组
  private n: number;

  constructor(size: number) {
    this.n = size;
    this.b1 = new FenwickTree(size);
    this.b2 = new FenwickTree(size);
  }

  // 区间更新：将 [left, right] 每个元素增加 val
  // 利用差分数组：d[left] += val, d[right+1] -= val
  rangeUpdate(left: number, right: number, val: number): void {
    this.b1.update(left, val);
    this.b1.update(right + 1, -val);
    this.b2.update(left, val * left);
    this.b2.update(right + 1, -val * (right + 1));
  }

  // 前缀查询：求 [0, index] 的和
  prefixSum(index: number): number {
    return (index + 1) * this.b1.prefixSum(index) - this.b2.prefixSum(index);
  }

  // 区间查询：求 [left, right] 的和
  rangeSum(left: number, right: number): number {
    return this.prefixSum(right) - this.prefixSum(left - 1);
  }
}

💡 提示： 差分数组技巧的核心思想是：区间加值 [l, r] += v 等价于在差分数组上执行 d[l] += v, d[r+1] -= v。两个树状数组配合可以将前缀和公式展开，从而支持区间更新 + 区间查询。

🔧 二、线段树（Segment Tree）：功能更强大的区间引擎

2.1 核心原理

线段树是一棵 完全二叉树，每个节点代表一个区间。根节点代表整个数组 [0, n-1]，每个非叶节点将其区间一分为二，左子节点代表左半区间，右子节点代表右半区间。

线段树的优势在于它天然支持 区间更新 和 多种聚合操作（求和、最值、GCD 等），而树状数组主要用于求和类操作。

⚠️ 警告： 线段树的空间通常是 4n（开 4 倍空间保证足够），而树状数组只需 n+1。在空间敏感的场景下需要注意。

2.2 TypeScript 完整实现（支持懒传播）

// 线段树完整实现：支持区间更新 + 区间查询（带懒传播）
class SegmentTree {
  private tree: number[];    // 线段树节点值
  private lazy: number[];    // 懒传播标记
  private n: number;

  constructor(data: number[]) {
    this.n = data.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.lazy = new Array(4 * this.n).fill(0);
    this.build(data, 1, 0, this.n - 1);
  }

  // 建树：从数组构建线段树
  private build(data: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = data[start];
      return;
    }
    const mid = (start + end) >> 1;
    this.build(data, node << 1, start, mid);
    this.build(data, node << 1 | 1, mid + 1, end);
    this.tree[node] = this.tree[node << 1] + this.tree[node << 1 | 1];
  }

  // 下推懒传播标记
  private pushDown(node: number, start: number, end: number): void {
    if (this.lazy[node] !== 0) {
      const mid = (start + end) >> 1;
      const left = node << 1;
      const right = node << 1 | 1;

      // 更新左子节点
      this.tree[left] += this.lazy[node] * (mid - start + 1);
      this.lazy[left] += this.lazy[node];

      // 更新右子节点
      this.tree[right] += this.lazy[node] * (end - mid);
      this.lazy[right] += this.lazy[node];

      this.lazy[node] = 0;
    }
  }

  // 区间更新：将 [l, r] 每个元素增加 val
  // 时间复杂度：O(log n)
  update(l: number, r: number, val: number, node = 1, start = 0, end = this.n - 1): void {
    if (l > end || r < start) return;
    if (l <= start && end <= r) {
      this.tree[node] += val * (end - start + 1);
      this.lazy[node] += val;
      return;
    }
    this.pushDown(node, start, end);
    const mid = (start + end) >> 1;
    this.update(l, r, val, node << 1, start, mid);
    this.update(l, r, val, node << 1 | 1, mid + 1, end);
    this.tree[node] = this.tree[node << 1] + this.tree[node << 1 | 1];
  }

  // 区间查询：求 [l, r] 的和
  // 时间复杂度：O(log n)
  query(l: number, r: number, node = 1, start = 0, end = this.n - 1): number {
    if (l > end || r < start) return 0;
    if (l <= start && end <= r) return this.tree[node];
    this.pushDown(node, start, end);
    const mid = (start + end) >> 1;
    return this.query(l, r, node << 1, start, mid) +
           this.query(l, r, node << 1 | 1, mid + 1, end);
  }
}

// 使用示例
const data = [1, 3, 5, 7, 9, 11];
const seg = new SegmentTree(data);
console.log(seg.query(1, 4));  // 24 (3+5+7+9)
seg.update(2, 4, 10);           // [2, 4] 每个元素 +10
console.log(seg.query(1, 4));  // 54 (3+15+17+19)

2.3 区间最值线段树

除了求和，线段树还支持最值查询。只需将聚合函数从 sum 改为 max/min：

// 区间最值线段树
class MaxSegmentTree {
  private tree: number[];
  private n: number;

  constructor(data: number[]) {
    this.n = data.length;
    this.tree = new Array(4 * this.n).fill(-Infinity);
    this.build(data, 1, 0, this.n - 1);
  }

  private build(data: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = data[start];
      return;
    }
    const mid = (start + end) >> 1;
    this.build(data, node << 1, start, mid);
    this.build(data, node << 1 | 1, mid + 1, end);
    this.tree[node] = Math.max(this.tree[node << 1], this.tree[node << 1 | 1]);
  }

  // 单点更新
  update(index: number, val: number, node = 1, start = 0, end = this.n - 1): void {
    if (start === end) {
      this.tree[node] = val;
      return;
    }
    const mid = (start + end) >> 1;
    if (index <= mid) this.update(index, val, node << 1, start, mid);
    else this.update(index, val, node << 1 | 1, mid + 1, end);
    this.tree[node] = Math.max(this.tree[node << 1], this.tree[node << 1 | 1]);
  }

  // 区间最大值查询
  query(l: number, r: number, node = 1, start = 0, end = this.n - 1): number {
    if (l > end || r < start) return -Infinity;
    if (l <= start && end <= r) return this.tree[node];
    const mid = (start + end) >> 1;
    return Math.max(
      this.query(l, r, node << 1, start, mid),
      this.query(l, r, node << 1 | 1, mid + 1, end)
    );
  }
}

// 使用示例：股票价格区间最高价查询
const prices = [12.5, 13.2, 11.8, 14.6, 13.9, 15.1, 12.3];
const maxSeg = new MaxSegmentTree(prices);
console.log(maxSeg.query(0, 3));  // 14.6（第 0~3 天最高价）
console.log(maxSeg.query(2, 6));  // 15.1（第 2~6 天最高价）
maxSeg.update(3, 16.8);           // 第 3 天价格更新为 16.8
console.log(maxSeg.query(0, 6));  // 16.8（全局最高价）

📊 三、性能对比与选型指南

3.1 时间复杂度对比

*需要双数组技巧

3.2 实际性能测试

在 Node.js v24 环境下对 100 万个元素执行 10 万次随机区间查询：

*前缀和查询快但不支持动态更新

⚡ 关键结论： 如果只需要区间求和且数据是静态的，前缀和是最优解。如果需要动态更新，树状数组是最佳选择。如果需要区间最值或更复杂的聚合操作，选线段树。

3.3 选型决策树

需要区间查询？
├── 否 → 直接用数组
└── 是
    ├── 数据是否需要动态更新？
    │   ├── 否 → 前缀和 O(n) 建树，O(1) 查询
    │   └── 是
    │       ├── 只需要区间求和？ → 树状数组
    │       ├── 需要区间最值/GCD？ → 线段树
    │       └── 需要区间赋值（覆盖而非累加）？ → 线段树（懒传播）
    └── 空间是否极度敏感？
        └── 是 → 树状数组（O(n) vs O(4n)）

💡 四、真实业务场景实战

4.1 实时排行榜：动态排名查询

场景：游戏服务器中，玩家分数实时变化，需要快速查询某个玩家的排名（即有多少人分数比他高）。

// 基于树状数组的动态排行榜
// 将分数离散化后，用树状数组维护每个分数段的人数
class DynamicLeaderboard {
  private fw: FenwickTree;
  private scoreMap: Map<number, number>; // 分数 → 离散化索引
  private reverseMap: number[];           // 离散化索引 → 分数
  private playerScores: Map<string, number>;

  constructor(maxScore: number) {
    this.fw = new FenwickTree(maxScore + 1);
    this.scoreMap = new Map();
    this.reverseMap = [];
    this.playerScores = new Map();

    // 简化：假设分数为 0~maxScore 的整数
    for (let i = 0; i <= maxScore; i++) {
      this.scoreMap.set(i, i);
      this.reverseMap[i] = i;
    }
  }

  // 更新玩家分数
  updateScore(player: string, newScore: number): void {
    const oldScore = this.playerScores.get(player);
    if (oldScore !== undefined) {
      this.fw.update(oldScore, -1); // 移除旧分数
    }
    this.fw.update(newScore, 1);    // 添加新分数
    this.playerScores.set(player, newScore);
  }

  // 查询排名（分数 >= score 的人数）
  getRank(score: number): number {
    const totalPlayers = this.fw.prefixSum(this.reverseMap.length - 1);
    const lowerPlayers = score > 0 ? this.fw.prefixSum(score - 1) : 0;
    return totalPlayers - lowerPlayers + 1;
  }

  // 查询前 K 名的分数区间和
  topKSum(k: number): number {
    // 二分查找第 K 名的分数
    let lo = 0, hi = this.reverseMap.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      const rank = this.getRank(mid);
      if (rank <= k) hi = mid;
      else lo = mid + 1;
    }
    return this.fw.rangeSum(lo, this.reverseMap.length - 1);
  }
}

// 使用示例
const lb = new DynamicLeaderboard(1000);
lb.updateScore("player_A", 850);
lb.updateScore("player_B", 920);
lb.updateScore("player_C", 780);
lb.updateScore("player_D", 920);
console.log(lb.getRank(850));  // 3（有 3 人分数 >= 850）

4.2 时间序列数据聚合：IoT 传感器监控

场景：IoT 平台每秒采集温度数据，需要快速查询任意时间段的最高温度和总温度。

// IoT 传感器数据聚合：双线段树方案
class SensorAggregator {
  private maxTree: MaxSegmentTree;
  private sumTree: SegmentTree;
  private data: number[];

  constructor(initialData: number[]) {
    this.data = [...initialData];
    this.maxTree = new MaxSegmentTree(initialData);
    this.sumTree = new SegmentTree(initialData);
  }

  // 更新某个时间点的温度
  update(timestamp: number, temperature: number): void {
    const delta = temperature - this.data[timestamp];
    this.data[timestamp] = temperature;
    this.maxTree.update(timestamp, temperature);
    this.sumTree.update(timestamp, timestamp, delta);
  }

  // 查询时间段内的最高温度
  getMaxTemp(start: number, end: number): number {
    return this.maxTree.query(start, end);
  }

  // 查询时间段内的平均温度
  getAvgTemp(start: number, end: number): number {
    const sum = this.sumTree.query(start, end);
    return sum / (end - start + 1);
  }
}

// 使用示例：24 小时温度数据（每小时一个采样点）
const hourlyTemp = [18, 17, 16, 15, 15, 16, 19, 22, 25, 28, 30, 31,
                    32, 33, 32, 30, 28, 25, 23, 21, 20, 19, 18, 18];
const sensor = new SensorAggregator(hourlyTemp);

console.log(sensor.getMaxTemp(6, 14));  // 33（6:00~14:00 最高温）
console.log(sensor.getAvgTemp(0, 5));   // 16.17（凌晨平均温度）

sensor.update(12, 36);  // 12:00 温度更新为 36°C
console.log(sensor.getMaxTemp(0, 23));  // 36（全天最高温）

4.3 逆序对计数：数据一致性校验

场景：在分布式系统中，检测数据同步的偏移量——如果两个副本的元素顺序差异越大，说明数据越不一致。逆序对数量是衡量"有序程度"的经典指标。

// 基于树状数组的逆序对计数
// 时间复杂度：O(n log n)，优于暴力 O(n²)
function countInversions(arr: number[]): number {
  // 离散化：将值映射到紧凑的索引空间
  const sorted = [...new Set(arr)].sort((a, b) => a - b);
  const rank = new Map(sorted.map((v, i) => [v, i + 1]));

  const fw = new FenwickTree(sorted.length);
  let inversions = 0;

  for (let i = 0; i < arr.length; i++) {
    // 查询已处理元素中，比当前元素大的个数
    const r = rank.get(arr[i])!;
    inversions += i - fw.prefixSum(r - 1);
    fw.update(r - 1, 1);
  }

  return inversions;
}

// 使用示例
console.log(countInversions([3, 1, 4, 1, 5, 9]));  // 5
console.log(countInversions([1, 2, 3, 4, 5]));      // 0（完全有序）
console.log(countInversions([5, 4, 3, 2, 1]));      // 10（完全逆序）

⚠️ 五、常见坑点与避坑指南

❌ 坑点 1：线段树数组越界

// ❌ 错误写法：只开 n 倍空间
const tree = new Array(this.n).fill(0);  // 一定不够用！

// ✅ 正确写法：开 4 倍空间
const tree = new Array(4 * this.n).fill(0);

线段树是一棵完全二叉树，叶子层有 n 个节点，总节点数约为 4n。开 4 倍空间是最安全的做法。

❌ 坑点 2：树状数组的 1-indexed 陷阱

// ❌ 错误写法：直接用 0-indexed
update(0, value);  // tree[0] 永远不会被更新，lowbit(0) = 0 死循环！

// ✅ 正确写法：内部转为 1-indexed
update(index: number, delta: number): void {
  for (let i = index + 1; i <= this.n; i += this.lowbit(i)) { ... }
}

⚠️ 警告： 树状数组的内部实现必须使用 1-indexed，因为 lowbit(0) = 0 会导致死循环。对外接口可以保持 0-indexed，只需在内部加 1 即可。

❌ 坑点 3：懒传播忘记下推

// ❌ 错误写法：查询时不下推懒标记
query(l, r, node, start, end) {
  if (l <= start && end <= r) return this.tree[node];
  // 缺少 pushDown！子节点的值可能是过时的
  const mid = (start + end) >> 1;
  return this.query(l, r, node << 1, start, mid) + ...
}

// ✅ 正确写法：查询前先下推
query(l, r, node, start, end) {
  if (l <= start && end <= r) return this.tree[node];
  this.pushDown(node, start, end);  // 先下推！
  const mid = (start + end) >> 1;
  return this.query(l, r, node << 1, start, mid) + ...
}

❌ 坑点 4：聚合函数不满足结合律

线段树和树状数组要求聚合函数满足 结合律，即 (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)。

// ✅ 满足结合律的操作
// 求和：(a + b) + c = a + (b + c)
// 最大值：max(max(a, b), c) = max(a, max(b, c))
// GCD：gcd(gcd(a, b), c) = gcd(a, gcd(b, c))

// ❌ 不满足结合律的操作
// 平均值：avg(avg(a, b), c) ≠ avg(a, avg(b, c))
// 中位数：不能直接用线段树维护

💡 提示： 如果需要求区间平均值，可以维护区间和 + 区间长度两个线段树。中位数需要使用 权值线段树 + 二分 或 可持久化线段树（主席树），这是更高级的话题。

🔐 六、进阶：可持久化线段树简介

可持久化线段树（Persistent Segment Tree / Chairman Tree）是线段树的高级变体，它支持 历史版本查询——你可以查询任意历史时刻的区间信息。

核心思想：每次修改只创建被修改路径上的新节点，未修改的节点与旧版本共享。这样空间复杂度为 O(n log n)，而非 O(n²)。

典型应用：

• ✅ 区间第 K 大 / 第 K 小查询
• ✅ 区间不同元素个数
• ✅ 历史版本回溯

// 可持久化线段树骨架（区间第 K 大查询）
class PersistentSegmentTree {
  private roots: number[] = [];  // 每个版本的根节点
  private nodes: { sum: number; left: number; right: number }[] = [];
  private nodeCount = 0;

  private newNode(sum = 0, left = 0, right = 0): number {
    this.nodes.push({ sum, left, right });
    return this.nodeCount++;
  }

  // 建树：初始空树
  build(l: number, r: number): number {
    const node = this.newNode(0);
    if (l === r) return node;
    const mid = (l + r) >> 1;
    this.nodes[node].left = this.build(l, mid);
    this.nodes[node].right = this.build(mid + 1, r);
    return node;
  }

  // 单点更新：返回新版本的根节点
  update(prevRoot: number, l: number, r: number, pos: number): number {
    const node = this.newNode(this.nodes[prevRoot].sum + 1);
    if (l === r) return node;
    const mid = (l + r) >> 1;
    if (pos <= mid) {
      this.nodes[node].left = this.update(this.nodes[prevRoot].left, l, mid, pos);
      this.nodes[node].right = this.nodes[prevRoot].right;
    } else {
      this.nodes[node].left = this.nodes[prevRoot].left;
      this.nodes[node].right = this.update(this.nodes[prevRoot].right, mid + 1, r, pos);
    }
    return node;
  }

  // 区间第 K 大查询
  queryKth(uRoot: number, vRoot: number, l: number, r: number, k: number): number {
    if (l === r) return l;
    const mid = (l + r) >> 1;
    const leftCount = this.nodes[this.nodes[vRoot].left].sum -
                      this.nodes[this.nodes[uRoot].left].sum;
    if (k <= leftCount) {
      return this.queryKth(
        this.nodes[uRoot].left, this.nodes[vRoot].left, l, mid, k
      );
    }
    return this.queryKth(
      this.nodes[uRoot].right, this.nodes[vRoot].right, mid + 1, r, k - leftCount
    );
  }
}

✅ 总结

线段树和树状数组是处理动态区间查询的两大核心数据结构。选型原则很明确：

• 🎯 树状数组：代码简洁（~20 行）、空间高效（O(n)）、适合区间求和场景
• 🎯 线段树：功能强大（最值/区间赋值/懒传播）、适合复杂聚合操作
• 🎯 前缀和：静态数据的最优解，O(1) 查询
• 🎯 可持久化线段树：需要历史版本查询时的终极武器

在实际项目中，排行榜用树状数组、监控聚合用线段树、静态报表用前缀和——根据场景选择最合适的数据结构，而不是最复杂的。

🔧 相关工具推荐

• jsjson.com — 在线 JSON 数据分析工具，快速验证数据结构的输入输出
• LeetCode — 区间查询类题库，推荐 #307 (Range Sum Query - Mutable)、#315 (Count of Smaller Numbers After Self)
• VisuAlgo — 数据结构可视化工具，直观理解线段树的建树和查询过程