線段樹講解 數據結構 C++ 實現 区間查詢與單點更新

線段樹定義

二叉樹結構，每個節點對應一個區間 [l,r]，存儲該區間的聚合信息（和、最大值、最小值等）。根節點對應 [1,n]，葉節點對應單個元素。

核心操作

1. 建樹：遞歸二分區間，葉節點賦值，內部節點合併子節點信息
2. 單點更新：遞歸定位葉節點，更新後回溯合併
3. 區間查詢：遞歸分解查詢區間，合併相關節點信息

模板實現

struct Node {
    int l, r;
    long long sum, mx;
} tree[4*MAXN];
int a[MAXN];

void pushup(int u) {
    tree[u].sum = tree[u<<1].sum + tree[u<<1|1].sum;
    tree[u].mx = max(tree[u<<1].mx, tree[u<<1|1].mx);
}

void build(int u, int l, int r) {
    tree[u].l = l; tree[u].r = r;
    if (l == r) {
        tree[u].sum = tree[u].mx = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
    pushup(u);
}

void update(int u, int pos, int val) {
    if (tree[u].l == tree[u].r) {
        tree[u].sum = tree[u].mx = val;
        return;
    }
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (pos <= mid) update(u<<1, pos, val);
    else update(u<<1|1, pos, val);
    pushup(u);
}

long long querySum(int u, int L, int R) {
    if (L <= tree[u].l && tree[u].r <= R) return tree[u].sum;
    int mid = (tree[u].l + tree[u].r) >> 1;
    long long ans = 0;
    if (L <= mid) ans += querySum(u<<1, L, R);
    if (R > mid) ans += querySum(u<<1|1, L, R);
    return ans;
}

long long queryMax(int u, int L, int R) {
    if (L <= tree[u].l && tree[u].r <= R) return tree[u].mx;
    int mid = (tree[u].l + tree[u].r) >> 1;
    long long ans = LLONG_MIN;
    if (L <= mid) ans = max(ans, queryMax(u<<1, L, R));
    if (R > mid) ans = max(ans, queryMax(u<<1|1, L, R));
    return ans;
}

關鍵技巧

• 數組大小開 4*n 保證足夠
• 位運算 u<<1 (左子), u<<1|1 (右子) 加速
• pushup 統一維護邏輯，易擴展
• 查詢時區間完全包含直接返回，部分重疊遞歸分解

複雜度

延伸：區間修改（懶標記）

需增加 lazy 標記，下推時更新子節點並傳遞標記。本文不展開。