支持区间求和的线段树

功能说明

该示例实现数组上的线段树，支持区间求和与单点更新。构建一次后，任意区间的和以及任意位置的新值都能在对数时间内完成，适合频繁查询与修改交替出现的场景，例如统计面板、排行榜分数、时间序列聚合。相比每次遍历求和，数据量大时优势明显。

关键代码

构造函数把数组长度记为 size，并分配四倍长度的 tree 数组，从根节点开始递归建树。叶节点保存原值，内部节点保存左右子节点之和。sum 校验左右边界为整数且落在范围内后调用 query，query 在完全覆盖时直接返回节点值，否则按中点拆分并累加相交部分。update 沿根到目标叶的路径更新，再逐层重算父节点。

使用注意

该实现只支持求和，若需要最小值、最大值或异或，应替换合并逻辑并调整空区间单位元。数组长度为零时构造成功但任何查询都会抛 RangeError。数值使用 JavaScript 双精度浮点，超大累计和可能丢失精度，金额场景应改用整数分。tree 使用四倍空间，内存敏感时可改为迭代式线段树。

验证方式

对 2、4、6、8、10 断言区间 1 到 3 的和为 18。把下标 2 更新为 0 后断言全区间和为 24、单点查询为 0。测试空树查询抛错、越界区间抛错、左右颠倒抛错。再与朴素循环求和在一百次随机更新后逐区间对比。

代码示例

export class SegmentTree {
  private readonly size: number;
  private readonly tree: number[];

  constructor(values: readonly number[]) {
    if (!Array.isArray(values)) throw new TypeError("values must be an array");
    for (const value of values) {
      if (typeof value !== "number" || !Number.isFinite(value)) {
        throw new TypeError("values must contain finite numbers");
      }
    }
    this.size = values.length;
    this.tree = new Array<number>(Math.max(4, this.size * 4)).fill(0);
    if (this.size > 0) this.build(values, 1, 0, this.size - 1);
  }

  sum(left: number, right: number): number {
    if (!Number.isInteger(left) || !Number.isInteger(right)) {
      throw new TypeError("range bounds must be integers");
    }
    if (left < 0 || right >= this.size || left > right) throw new RangeError("invalid range");
    return this.query(1, 0, this.size - 1, left, right);
  }

  update(index: number, value: number): void {
    if (!Number.isInteger(index) || index < 0 || index >= this.size) {
      throw new RangeError("index out of range");
    }
    if (typeof value !== "number" || !Number.isFinite(value)) {
      throw new TypeError("value must be a finite number");
    }
    this.assign(1, 0, this.size - 1, index, value);
  }

  private build(values: readonly number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = values[start] ?? 0;
      return;
    }
    const middle = (start + end) >> 1;
    this.build(values, node * 2, start, middle);
    this.build(values, node * 2 + 1, middle + 1, end);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }

  private query(node: number, start: number, end: number, left: number, right: number): number {
    if (left <= start && end <= right) return this.tree[node];
    const middle = (start + end) >> 1;
    let total = 0;
    if (left <= middle) total += this.query(node * 2, start, middle, left, right);
    if (right > middle) total += this.query(node * 2 + 1, middle + 1, end, left, right);
    return total;
  }

  private assign(node: number, start: number, end: number, index: number, value: number): void {
    if (start === end) {
      this.tree[node] = value;
      return;
    }
    const middle = (start + end) >> 1;
    if (index <= middle) this.assign(node * 2, start, middle, index, value);
    else this.assign(node * 2 + 1, middle + 1, end, index, value);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

const tree = new SegmentTree([2, 4, 6, 8, 10]);
console.log(tree.sum(1, 3));
tree.update(2, 0);
console.log(tree.sum(0, 4));
console.log(tree.sum(2, 2));