線段樹 (Segment Tree) 完全攻略#

基本概念#

假設我們有一個陣列 [1, 3, 5, 7, 9, 11]，要建立一個求區間總和的線段樹：

                    [0,5] = 36
                   /          \
            [0,2] = 9          [3,5] = 27
           /        \          /         \
      [0,1] = 4   [2,2] = 5  [3,4] = 16  [5,5] = 11
     /        \              /         \
 [0,0] = 1  [1,1] = 3   [3,3] = 7   [4,4] = 9

每個節點代表一個區間，儲存該區間的總和（或其他統計值）。

數學性質#

對於一個大小為 (n) 的陣列：

• 線段樹的高度為 (\lceil \log_2 n \rceil + 1)
• 總節點數最多為 (4n)（為了方便實作，通常開 4 倍空間）
• 葉子節點數量為 (n)

基礎結構#

class SegmentTree {
private:
    vector<int> tree;
    int n;
    
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            // 葉子節點
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            // 遞迴建立左右子樹
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            // 合併左右子樹的結果
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n-1);
    }
};

TIP

我們使用編號從 1 開始的完全二元樹，這樣節點 i 的左子節點是 2*i，右子節點是 2*i+1。

區間查詢操作#

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        // 完全不重疊
        return 0;
    }
    if (l <= start && end <= r) {
        // 完全包含
        return tree[node];
    }
    // 部分重疊，遞迴查詢
    int mid = (start + end) / 2;
    int p1 = query(2*node, start, mid, l, r);
    int p2 = query(2*node+1, mid+1, end, l, r);
    return p1 + p2;
}

// 公開介面
int rangeSum(int l, int r) {
    return query(1, 0, n-1, l, r);
}

單點更新操作#

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // 找到要更新的葉子節點
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            // 更新左子樹
            update(2*node, start, mid, idx, val);
        } else {
            // 更新右子樹
            update(2*node+1, mid+1, end, idx, val);
        }
        // 更新當前節點
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

// 公開介面
void pointUpdate(int idx, int val) {
    update(1, 0, n-1, idx, val);
}

1. 區間最大值查詢#

// 修改合併操作
tree[node] = max(tree[2*node], tree[2*node+1]);

// 查詢時返回最大值
return max(p1, p2);

2. 區間最小值查詢#

// 修改合併操作
tree[node] = min(tree[2*node], tree[2*node+1]);

// 查詢時返回最小值  
return min(p1, p2);

3. 懶惰標記 (Lazy Propagation)#

當需要處理區間更新時，我們使用懶惰標記來避免每次都更新所有節點：

class LazySegmentTree {
private:
    vector<int> tree, lazy;
    
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void rangeUpdate(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if (start > r || end < l) return;
        
        if (start >= l && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        
        int mid = (start + end) / 2;
        rangeUpdate(2*node, start, mid, l, r, val);
        rangeUpdate(2*node+1, mid+1, end, l, r, val);
        
        push(2*node, start, mid);
        push(2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
};

LeetCode 相關題目#

1. 307. Range Sum Query - Mutable
2. 315. Count of Smaller Numbers After Self

Codeforces 相關題目#

1. Codeforces 339D - Xenia and Bit Operations
2. Codeforces 380C - Sereja and Brackets

1. 記憶體優化#

// 動態建立節點，節省記憶體
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v = 0) : val(v), left(nullptr), right(nullptr) {}
};

2. 泛型設計#

template<typename T>
class SegmentTree {
private:
    function<T(T, T)> combine;
    T identity;
    
public:
    SegmentTree(vector<T>& arr, function<T(T, T)> op, T id) 
        : combine(op), identity(id) {
        // 建構邏輯
    }
};