線段樹 — Lazy Propagation 與區間查詢完整實作 | 資料結構與演算法

2026/06/26
javascript 資料結構&演算法 線段樹 Segment Tree
線段樹 — Lazy Propagation 與區間查詢完整實作 | 資料結構與演算法

線段樹（Segment Tree） 是一種基於分治思想的二元樹型資料結構，能以 O(log n) 時間同時支援區間查詢與區間更新。搭配 Lazy Propagation（延遲傳播） 機制，它成為競技程式設計與系統工程中處理動態區間問題的首選工具。

前言

想像你管理一座圖書館，書架上有 10,000 本書，每本書都有一個分數。你需要頻繁回答以下問題：

  • 第 100 到 500 號書架的總分是多少？
  • 把第 200 到 300 號的所有書加 5 分。
  • 再次查詢第 100 到 500 號的總分。

如果每次都從頭掃描，複雜度是 O(n)，1000 次查詢就是百萬次運算。前綴和（Prefix Sum） 能讓查詢降到 O(1)，但更新後必須重建，更新本身回到 O(n)。

線段樹 在這兩個操作之間取得最佳平衡：無論查詢還是更新，都穩定在 O(log n)。

學習本文後你將能夠：

  • 理解線段樹的結構設計與節點對應關係
  • 實作 build、query、update 三大核心操作
  • 掌握 Lazy Propagation 的原理與 pushDown 機制
  • 用 TypeScript 與 C++ 寫出完整的線段樹類別
  • 解決 LeetCode 上常見的區間問題

為什麼需要線段樹

先看各種方法的時間複雜度比較：

操作暴力法前綴和線段樹
單點更新O(1)O(n) 重建O(log n)
區間查詢O(n)O(1)O(log n)
區間更新O(n)O(n) 重建O(log n)

前綴和（Prefix Sum）的弱點在於：一旦陣列元素被修改，整個前綴和陣列就必須重建，使得更新代價高昂。線段樹則以 O(log n) 完成所有操作，是動態修改場景的最佳選擇。

線段樹的結構設計

核心思想：遞迴分割區間

線段樹使用陣列模擬完全二元樹。對於原始陣列 [2, 1, 5, 3, 4]：

  • 根節點（節點 1）管理整個區間 [0, 4]，儲存總和 15
  • 節點 2 管理左半 [0, 2]，總和 8
  • 節點 3 管理右半 [3, 4]，總和 7
  • 以此類推，直到葉節點只管理單一元素
原始陣列: [2, 1, 5, 3, 4]

                [0,4] sum=15
               /            \
        [0,2] sum=8      [3,4] sum=7
        /       \          /       \
   [0,1] sum=3  [2,2]  [3,3]    [4,4]
   /       \    sum=5  sum=3    sum=4
[0,0]   [1,1]
sum=2   sum=1

節點編號（1-indexed）:
       1 (sum=15)
      / \
    2     3
   / \   / \
  4   5 6   7
 / \
8   9

節點索引規則

線段樹採用 1-indexed 的陣列儲存：

  • 節點 i 的左子節點是 2 * i
  • 節點 i 的右子節點是 2 * i + 1
  • 節點 i 的父節點是 ⌊i / 2⌋
  • 對於長度 n 的陣列，需要 4n 的空間（預留充足避免越界）

再看一個更完整的例子（8 個元素）：

陣列索引:  0    1    2    3    4    5    6    7
值:        3    1    4    1    5    9    2    6

線段樹（區間求和）:

                    node[1]=[0,7]=31
                   /                \
      node[2]=[0,3]=9          node[3]=[4,7]=22
      /           \            /              \
node[4]=[0,1]=4  [5]=[2,3]=5  [6]=[4,5]=14  [7]=[6,7]=8
  /     \         /     \       /     \       /     \
[0,0]=3 [1,1]=1 [2,2]=4 [3,3]=1 [4,4]=5 [5,5]=9 [6,6]=2 [7,7]=6

三大核心操作

Build（建樹）

自底向上建構：葉節點儲存原始值，內部節點合併左右子節點的結果。時間複雜度 O(n)。

build(node, start, end):
  if start == end:
    tree[node] = nums[start]   // 葉節點
    return
  mid = (start + end) / 2
  build(2*node, start, mid)    // 建左子樹
  build(2*node+1, mid+1, end)  // 建右子樹
  tree[node] = tree[2*node] + tree[2*node+1]  // 合併

Query（區間查詢）

將查詢區間 [l, r] 與節點管理的區間 [start, end] 比對，分三種情況處理：

  1. 完全不重疊（r < start 或 end < l）：返回零元素（求和返回 0，求最大值返回 -∞）
  2. 完全覆蓋（l <= start 且 end <= r）：直接返回此節點的值
  3. 部分重疊：遞迴查詢左右子樹，合併結果

時間複雜度 O(log n)（最多訪問 4 log n 個節點）。

Update（單點更新）

沿著根到目標葉節點的路徑往下，更新葉節點後，回溯時重新計算每個祖先節點的聚合值。時間複雜度 O(log n)。

Lazy Propagation（延遲傳播）

問題：區間更新的瓶頸

若要對區間 [l, r] 的每個元素都加上常數 k，樸素做法是對每個葉節點個別更新，最壞情況下是 O(n log n)——等同於 n 次單點更新。

Lazy Propagation（懶標記） 解決了這個問題。

核心思想

更新時，不立即把「加 k」傳播到所有子孫節點，而是：

  1. 在當前節點打上懶標記（lazy tag）：「此節點以下的所有子孫都需要加 k」
  2. 同時更新當前節點的聚合值（利用區間長度直接計算）
  3. 只有當真正需要進入子節點時（查詢或更新需要分裂區間），才將懶標記**下推（pushDown）**給兩個子節點

這樣每次區間更新只需訪問 O(log n) 個節點。

懶標記的視覺化

對 [1, 4] 所有元素加 3（陣列長度 8）:

初始狀態:
         [0,7] sum=31 lazy=0
        /                   \
  [0,3] sum=9 lazy=0     [4,7] sum=22 lazy=0

更新過程:
  步驟1: 根節點 [0,7] 部分重疊，往下分
  步驟2: 左節點 [0,3] 部分重疊，往下分
  步驟3:   [0,0] 不重疊，跳過
  步驟4:   [1,3] 完全覆蓋 → sum += 3×3=9，打 lazy=3
  步驟5: 右節點 [4,7] 部分重疊，往下分
  步驟6:   [4,4] 完全覆蓋 → sum += 3×1=3，打 lazy=3
  步驟7:   [5,7] 不重疊，跳過

之後如需訪問 [1,3] 的子節點，才執行 pushDown:
  lazy[1,1] += 3，sum[1,1] += 3×1
  lazy[2,3] += 3，sum[2,3] += 3×2
  清除 [1,3] 的 lazy

pushDown 規則

pushDown(node, start, end):
  if lazy[node] != 0:
    mid = (start + end) / 2
    leftLen  = mid - start + 1
    rightLen = end - mid

    // 更新左子節點
    tree[2*node]   += lazy[node] * leftLen
    lazy[2*node]   += lazy[node]

    // 更新右子節點
    tree[2*node+1] += lazy[node] * rightLen
    lazy[2*node+1] += lazy[node]

    // 清除自身懶標記
    lazy[node] = 0

TypeScript 完整實作

區間求和線段樹（含 Lazy Propagation）

class SegmentTree {
  private n: number;
  private tree: number[];  // 儲存區間聚合值
  private lazy: number[];  // 儲存懶標記

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

  // 建樹：自底向上合併
  private build(nums: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = nums[start];  // 葉節點儲存原始值
      return;
    }
    const mid = (start + end) >> 1;
    this.build(nums, 2 * node, start, mid);
    this.build(nums, 2 * node + 1, mid + 1, end);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];  // 合併
  }

  // 懶標記下推：訪問子節點前必須先呼叫
  private pushDown(node: number, start: number, end: number): void {
    if (this.lazy[node] !== 0) {
      const mid = (start + end) >> 1;
      const leftLen = mid - start + 1;
      const rightLen = end - mid;
      const left = 2 * node;
      const right = 2 * node + 1;

      // 將懶標記傳給左右子節點
      this.tree[left]  += this.lazy[node] * leftLen;
      this.tree[right] += this.lazy[node] * rightLen;
      this.lazy[left]  += this.lazy[node];
      this.lazy[right] += this.lazy[node];
      this.lazy[node] = 0;  // 清除自身懶標記
    }
  }

  // 區間更新：對 [l, r] 所有元素加 val
  update(l: number, r: number, val: number): void {
    this.updateHelper(1, 0, this.n - 1, l, r, val);
  }

  private updateHelper(
    node: number,
    start: number,
    end: number,
    l: number,
    r: number,
    val: number
  ): void {
    if (r < start || end < l) 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.updateHelper(2 * node, start, mid, l, r, val);
    this.updateHelper(2 * node + 1, mid + 1, end, l, r, val);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }

  // 區間查詢：返回 [l, r] 的總和
  query(l: number, r: number): number {
    return this.queryHelper(1, 0, this.n - 1, l, r);
  }

  private queryHelper(
    node: number,
    start: number,
    end: number,
    l: number,
    r: number
  ): number {
    if (r < start || end < l) return 0;      // 完全不重疊
    if (l <= start && end <= r) return this.tree[node];  // 完全覆蓋
    this.pushDown(node, start, end);          // 下推懶標記後再遞迴
    const mid = (start + end) >> 1;
    return (
      this.queryHelper(2 * node, start, mid, l, r) +
      this.queryHelper(2 * node + 1, mid + 1, end, l, r)
    );
  }

  // 單點賦值：將 index 位置設為 val
  set(index: number, val: number): void {
    this.setHelper(1, 0, this.n - 1, index, val);
  }

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

// 使用範例
const st = new SegmentTree([1, 3, 5, 7, 9, 11]);
console.log(st.query(1, 3));  // 輸出：15（3+5+7）
st.update(1, 3, 2);           // 對索引 1~3 各加 2
console.log(st.query(1, 3));  // 輸出：21（5+7+9）
st.set(2, 100);               // 將索引 2 設為 100
console.log(st.query(0, 5));  // 輸出：126

區間最大值線段樹

某些場景需要查詢區間最大值（如股票最高價、網路延遲峰值），只需把合併方式從加法換成 Math.max：

class SegmentTreeMax {
  private n: number;
  private tree: number[];

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

  private build(nums: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = nums[start];
      return;
    }
    const mid = (start + end) >> 1;
    this.build(nums, 2 * node, start, mid);
    this.build(nums, 2 * node + 1, mid + 1, end);
    // 合併改為取最大值
    this.tree[node] = Math.max(this.tree[2 * node], this.tree[2 * node + 1]);
  }

  // 單點更新
  update(index: number, val: number): void {
    this.updateHelper(1, 0, this.n - 1, index, val);
  }

  private updateHelper(node: number, start: number, end: number, index: number, val: number): void {
    if (start === end) {
      this.tree[node] = val;
      return;
    }
    const mid = (start + end) >> 1;
    if (index <= mid) this.updateHelper(2 * node, start, mid, index, val);
    else              this.updateHelper(2 * node + 1, mid + 1, end, index, val);
    this.tree[node] = Math.max(this.tree[2 * node], this.tree[2 * node + 1]);
  }

  // 區間最大值查詢
  queryMax(l: number, r: number): number {
    return this.queryHelper(1, 0, this.n - 1, l, r);
  }

  private queryHelper(node: number, start: number, end: number, l: number, r: number): number {
    if (r < start || end < l) return -Infinity;  // 不重疊返回負無窮
    if (l <= start && end <= r) return this.tree[node];
    const mid = (start + end) >> 1;
    return Math.max(
      this.queryHelper(2 * node, start, mid, l, r),
      this.queryHelper(2 * node + 1, mid + 1, end, l, r)
    );
  }
}

// 使用範例
const maxTree = new SegmentTreeMax([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(maxTree.queryMax(2, 5));  // 輸出：9（max(4,1,5,9)）
maxTree.update(5, 0);                 // 將索引 5 改為 0
console.log(maxTree.queryMax(2, 5));  // 輸出：5（max(4,1,5,0)）

C++ 對照實作

struct 封裝的通用線段樹

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
    int n;
    vector<long long> tree, lazy;

    SegmentTree(const vector<int>& nums)
        : n(nums.size()),
          tree(4 * nums.size(), 0),
          lazy(4 * nums.size(), 0) {
        build(nums, 1, 0, n - 1);
    }

    void build(const vector<int>& nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
            return;
        }
        int mid = (start + end) / 2;
        build(nums, 2 * node, start, mid);
        build(nums, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            int left = 2 * node, right = 2 * node + 1;
            tree[left]  += lazy[node] * (mid - start + 1);
            tree[right] += lazy[node] * (end - mid);
            lazy[left]  += lazy[node];
            lazy[right] += lazy[node];
            lazy[node]   = 0;
        }
    }

    // 區間加法更新
    void update(int l, int r, long long val, int node = 1, int start = -1, int end = -1) {
        if (start == -1) start = 0, end = n - 1;
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            tree[node] += val * (end - start + 1);
            lazy[node] += val;
            return;
        }
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        update(l, r, val, 2 * node, start, mid);
        update(l, r, val, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // 單點賦值
    void set(int index, long long val, int node = 1, int start = -1, int end = -1) {
        if (start == -1) start = 0, end = n - 1;
        if (start == end) {
            tree[node] = val;
            lazy[node] = 0;
            return;
        }
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        if (index <= mid) set(index, val, 2 * node, start, mid);
        else              set(index, val, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // 區間求和查詢
    long long query(int l, int r, int node = 1, int start = -1, int end = -1) {
        if (start == -1) start = 0, end = n - 1;
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        return query(l, r, 2 * node, start, mid) +
               query(l, r, 2 * node + 1, mid + 1, end);
    }
};

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 11};
    SegmentTree st(nums);

    cout << st.query(1, 3) << "\n";   // 輸出：15（3+5+7）
    st.update(1, 3, 2);               // 對索引 1~3 各加 2
    cout << st.query(1, 3) << "\n";   // 輸出：21
    return 0;
}

複雜度分析

操作時間複雜度空間複雜度說明
Build（建樹）O(n)O(n)每個節點只訪問一次
單點查詢O(log n)—沿路徑到葉節點
單點更新O(log n)—更新路徑上所有節點
區間查詢O(log n)—最多訪問 4 log n 個節點
區間更新（無懶標記）O(n log n)—等同 n 次單點更新
區間更新（懶標記）O(log n)—攤平後每操作 O(log n)
動態開點線段樹O(log n)O(m log n)m 次操作後的空間

空間說明：線段樹使用 4n 大小的陣列。雖然完全二元樹理論上只需 2n，但線段樹不一定是完全二元樹（n 不為 2 的冪次時），4n 是安全的通用上界。

變體與延伸

動態開點線段樹

當值域極大（如 10^9）但操作數少（如 10^5）時，靜態陣列會浪費大量空間。動態開點線段樹只在真正被訪問時才建立節點，空間從 O(N) 降到 O(m log N)（m 為操作次數）。

// 適用場景：值域 [1, 1e9]，操作數 1e5 次
// 只建立被訪問到的節點，節省 99.99% 空間
struct DynamicSegTree {
    struct Node {
        long long sum = 0, lazy = 0;
        int left = 0, right = 0;  // 子節點 ID（0 表示未建立）
    };

    int N;               // 值域上界
    vector<Node> nodes;
    int root = 1;

    DynamicSegTree(int N) : N(N) {
        nodes.emplace_back();  // nodes[0] 作為 null 節點
        nodes.emplace_back();  // nodes[1] 作為根節點
    }

    int newNode() {
        nodes.emplace_back();
        return nodes.size() - 1;
    }

    void pushDown(int node, int len) {
        if (nodes[node].lazy == 0) return;
        auto pushChild = [&](int& child, int childLen) {
            if (child == 0) child = newNode();
            nodes[child].sum  += nodes[node].lazy * childLen;
            nodes[child].lazy += nodes[node].lazy;
        };
        int mid = len / 2;
        pushChild(nodes[node].left,  mid);
        pushChild(nodes[node].right, len - mid);
        nodes[node].lazy = 0;
    }

    void update(int l, int r, long long val) { update(l, r, val, root, 1, N); }
    long long query(int l, int r)            { return query(l, r, root, 1, N); }

    void update(int l, int r, long long val, int node, int start, int end) {
        if (l <= start && end <= r) {
            nodes[node].sum  += val * (end - start + 1);
            nodes[node].lazy += val;
            return;
        }
        pushDown(node, end - start + 1);
        int mid = (start + end) / 2;
        if (l <= mid) {
            if (!nodes[node].left) nodes[node].left = newNode();
            update(l, r, val, nodes[node].left, start, mid);
        }
        if (r > mid) {
            if (!nodes[node].right) nodes[node].right = newNode();
            update(l, r, val, nodes[node].right, mid + 1, end);
        }
        nodes[node].sum = nodes[nodes[node].left].sum + nodes[nodes[node].right].sum;
    }

    long long query(int l, int r, int node, int start, int end) {
        if (!node) return 0;
        if (l <= start && end <= r) return nodes[node].sum;
        pushDown(node, end - start + 1);
        int mid = (start + end) / 2;
        long long res = 0;
        if (l <= mid)  res += query(l, r, nodes[node].left,  start, mid);
        if (r > mid)   res += query(l, r, nodes[node].right, mid + 1, end);
        return res;
    }
};

持久化線段樹（主席樹）

持久化線段樹（Persistent Segment Tree），又稱主席樹（Chairman Tree），在每次更新時不修改原有節點，而是透過**路徑複製（Path Copying）**建立新版本，共享未修改的節點。每次操作只新增 O(log n) 個節點。

版本 0:         版本 1（更新後）:
   root0              root1
  /    \             /    \
 A      B           A'     B        ← B 共享，A' 是新建的
/ \    / \         / \
C   D E   F       C'  D             ← D 共享，C' 是新建的

典型應用：靜態區間第 K 小值——對陣列從左到右建立 n+1 個版本的線段樹，利用版本差分（root[r] - root[l-1]）在 O(log n) 內查詢任意區間的第 K 小值。

線段樹合併

兩棵線段樹可以合併為一棵，透過遞迴合併對應節點的值。常見於「把子樹的答案合併到父節點」的樹型 DP 場景，時間複雜度 O(m log n)（m 為兩棵樹的節點總數）。

二維線段樹

將一維線段樹的每個節點再掛一棵線段樹，支援二維矩形區間的查詢與更新。時間複雜度 O(log n × log m)，空間複雜度 O(nm)。實際競程中更常用二維 BIT（樹狀陣列），程式碼較簡單。

常見陷阱

在實作線段樹時，以下幾個坑特別容易踩到：

1. 陣列空間不足

線段樹陣列至少需要 4n 空間，若使用 2n 會在 n 不是 2 的冪時發生越界。安全做法是始終開 4n。

2. 忘記在訪問子節點前 pushDown

在 query 和 update 的「部分重疊」分支，遞迴進入子節點之前必須先呼叫 pushDown。漏掉這一步會導致子節點讀到過期的數據。

3. 區間加法 vs 區間賦值的懶標記語義不同

  • 區間加法：lazy[child] += lazy[parent]（可以疊加）
  • 區間賦值：lazy[child] = lazy[parent]（直接覆蓋，舊值作廢）

兩者混用時需要分開維護兩種懶標記，處理優先級（賦值優先於加法）。

4. 1-indexed 與 0-indexed 混用

線段樹內部節點習慣 1-indexed（根節點為 1），但原始陣列通常是 0-indexed。確保邊界 [0, n-1] 的轉換正確，不要搞混。

5. 動態開點的節點池預分配

每次操作最多新建 2 log N 個節點，m 次操作需預分配 m × 2 × log(N) 個節點。若未預留足夠空間，vector 重新分配記憶體時會使舊指標失效，造成難以追蹤的 bug。

面試考點

題型一：區間最小值查詢

在面試中，考官可能會直接問：「如何設計一個支援區間最小值查詢與單點更新的資料結構？」

關鍵點：只需將合併函數從加法換成 Math.min，返回空區間時用 +Infinity 而非 0。

// 合併方式
this.tree[node] = Math.min(this.tree[2 * node], this.tree[2 * node + 1]);

// 不重疊時返回
if (r < start || end < l) return Infinity;

題型二：區間賦值更新

若更新操作是「將 [l, r] 內所有元素設為某個值」（而非加法），懶標記語義需要調整：

// 懶標記表示「設為此值」而非「加上此值」
// pushDown 時直接覆蓋子節點，不累加
private pushDown(node: number, start: number, end: number): void {
  if (this.lazy[node] !== -1) {  // -1 表示無標記
    const mid = (start + end) >> 1;
    const left = 2 * node, right = 2 * node + 1;
    // 賦值：直接覆蓋
    this.tree[left]  = this.lazy[node] * (mid - start + 1);
    this.tree[right] = this.lazy[node] * (end - mid);
    this.lazy[left]  = this.lazy[node];
    this.lazy[right] = this.lazy[node];
    this.lazy[node]  = -1;  // 清除
  }
}

LeetCode 練習題

LeetCode 307 — Range Sum Query - Mutable（Medium）

題意：設計支援單點更新與區間求和查詢的資料結構。這是線段樹最直接的應用題。

class NumArray {
  private tree: number[];
  private n: number;

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

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

  update(index: number, val: number): void {
    this.updateHelper(1, 0, this.n - 1, index, val);
  }

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

  sumRange(left: number, right: number): number {
    return this.queryHelper(1, 0, this.n - 1, left, right);
  }

  private queryHelper(node: number, start: number, end: number, l: number, r: number): number {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];
    const mid = (start + end) >> 1;
    return this.queryHelper(2 * node, start, mid, l, r) +
           this.queryHelper(2 * node + 1, mid + 1, end, l, r);
  }
}

// 複雜度：建樹 O(n)，更新 O(log n)，查詢 O(log n)，空間 O(n)

LeetCode 303 — Range Sum Query - Immutable（Easy）

題意：陣列不變，只需多次查詢區間和。此題用前綴和即可，不需要線段樹。但可以用本題練習理解「當陣列不可變時，前綴和是更好的選擇」，加深對資料結構選擇的判斷力。

class NumArrayImmutable {
  private prefix: number[];

  constructor(nums: number[]) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

// 複雜度：建表 O(n)，查詢 O(1)，空間 O(n)
// 此題不需線段樹，說明：選對資料結構比盲目用複雜結構更重要

LeetCode 315 — Count of Smaller Numbers After Self（Hard）

題意：對每個 nums[i]，計算右側有多少個元素嚴格小於它。

關鍵洞察：從右往左掃描，用線段樹維護已見元素的計數（值域線段樹）。先離散化壓縮值域，再對每個元素查詢「比自己小的個數」，然後將自己插入線段樹。

function countSmaller(nums: number[]): number[] {
  // 離散化：將值域壓縮到 [1, m]
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));
  const m = sorted.length;

  // 值域線段樹：儲存每個離散值的出現次數
  const tree = new Array(4 * (m + 1)).fill(0);

  const update = (node: number, start: number, end: number, idx: number): void => {
    if (start === end) { tree[node]++; return; }
    const mid = (start + end) >> 1;
    if (idx <= mid) update(2 * node, start, mid, idx);
    else            update(2 * node + 1, mid + 1, end, idx);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
  };

  const query = (node: number, start: number, end: number, l: number, r: number): number => {
    if (r < l || r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    const mid = (start + end) >> 1;
    return query(2 * node, start, mid, l, r) +
           query(2 * node + 1, mid + 1, end, l, r);
  };

  const result: number[] = new Array(nums.length);
  for (let i = nums.length - 1; i >= 0; i--) {
    const r = rank.get(nums[i])!;
    result[i] = query(1, 1, m, 1, r - 1);  // 查詢比自己小的個數
    update(1, 1, m, r);                     // 將自己插入線段樹
  }
  return result;
}

// 複雜度：O(n log n) 時間，O(n) 空間

LeetCode 218 — The Skyline Problem（Hard）

題意：給定一組建築物的 [left, right, height]，求天際線輪廓的關鍵點。

線段樹策略：將建築物的所有 x 座標離散化，以座標為索引建立線段樹（維護區間最大高度）。掃描線（sweep line）從左到右，遇到建築物左端加入高度，遇到右端移除高度，每次變化時查詢當前全局最大高度，高度變化點即為天際線關鍵點。時間複雜度 O(n log n)。

LeetCode 732 — My Calendar III（Hard）

題意：動態插入日程區間 [start, end)，每次插入後回報最多幾個日程重疊（即區間最大重疊數）。

線段樹策略：用動態開點線段樹，對 [start, end-1] 執行區間加 1，然後查詢全局最大值。因為日期範圍可達 10^9，必須使用動態開點。

class MyCalendarThree {
  private tree: Map<number, number> = new Map();
  private lazy: Map<number, number> = new Map();

  private get(map: Map<number, number>, key: number): number {
    return map.get(key) ?? 0;
  }

  private pushDown(node: number): void {
    const lz = this.get(this.lazy, node);
    if (lz !== 0) {
      const left = 2 * node, right = 2 * node + 1;
      this.tree.set(left,  (this.get(this.tree, left)  + lz));
      this.tree.set(right, (this.get(this.tree, right) + lz));
      this.lazy.set(left,  (this.get(this.lazy, left)  + lz));
      this.lazy.set(right, (this.get(this.lazy, right) + lz));
      this.lazy.set(node, 0);
    }
  }

  private update(node: number, start: number, end: number, l: number, r: number): void {
    if (r < start || end < l) return;
    if (l <= start && end <= r) {
      this.tree.set(node, (this.get(this.tree, node) + 1));
      this.lazy.set(node, (this.get(this.lazy, node) + 1));
      return;
    }
    this.pushDown(node);
    const mid = (start + end) >> 1;
    this.update(2 * node, start, mid, l, r);
    this.update(2 * node + 1, mid + 1, end, l, r);
    this.tree.set(node, Math.max(
      this.get(this.tree, 2 * node),
      this.get(this.tree, 2 * node + 1)
    ));
  }

  book(start: number, end: number): number {
    this.update(1, 0, 1e9, start, end - 1);
    return this.get(this.tree, 1);
  }
}

// 複雜度：每次 book O(log N)，N = 1e9

LeetCode 推薦練習清單

題號題目難度線段樹應用
303Range Sum Query - ImmutableEasy前綴和（對比用，理解選擇時機）
307Range Sum Query - MutableMedium標準單點更新 + 區間查詢
315Count of Smaller Numbers After SelfHard離散化 + 值域線段樹計數
218The Skyline ProblemHard掃描線 + 區間最大值
732My Calendar IIIHard動態開點 + 區間加法 + 全域最大值

總結

線段樹是資料結構與演算法中「投資報酬率」極高的一個工具：

  • 核心思想是分治遞迴，將區間問題分解到可以直接計算的最小單元
  • 三大操作（build / query / update）各有清晰的邏輯：build 自底向上，query 分三種重疊情況，update 沿路徑修改
  • Lazy Propagation 是線段樹處理區間更新的精髓，以「打標記延遲更新」的策略，將區間更新從 O(n) 優化到 O(log n)
  • 靈活的聚合函數讓線段樹不只能求和，也能求最大值、最小值、GCD、最大公因數等任何滿足結合律的運算

掌握線段樹之後，你會發現許多看似複雜的區間問題都能迎刃而解。

希望這篇文章能幫助你扎實理解線段樹的每個細節。如果在練習過程中遇到問題，歡迎到 聯絡頁面 留言討論！

下一篇：我們將介紹 樹狀陣列（Fenwick Tree / BIT）——線段樹的精簡版，以更短的程式碼在前綴和問題上達到相同的 O(log n) 效能。敬請期待！

BenZ Software Developer

熱愛技術的軟體開發者，在這裡分享程式開發經驗與學習筆記。