線段樹動態開點詳解

線段樹是一種用於處理區間問題的數據結構，其應用非常廣泛。但在實際應用過程中，線段樹的空間複雜度往往是固定的，而事實上，我們並不總是需要處理整個區間，這樣就導致了空間浪費。動態開點線段樹就是為了解決這個問題而誕生的。本文將從多個方面對線段樹動態開點做詳細的闡述。

一、讀入數據

為了實現動態開點，首先需要我們先讀入數據。一個線段樹最大的葉子結點編號為n，如果我們已知了需要處理區間的右端點r，那麼這棵線段樹空間就可以直接開到2n。但是如果我們不知道r的值，線段樹的空間就不能提前開到2n，否則就會造成空間浪費。正確的做法是使用動態開點技術，根據需要動態的開啟和關閉每一個節點，這樣就可以避免空間浪費了。

下面是讀入數據的代碼示例：

struct SegmentTree {
    int l, r, sum; // sum 表示該區間內元素的和
    int lt, rt; //左右兒子的編號
    #define lson tr[u].lt
    #define rson tr[u].rt
} tr[MAXN*40]; //開到足夠大的數量

int n, m, idx; //idx 表示當前空閑結點編號
int root[MAXN]; // root[i] 表示以第 i 個數為右端點建立的線段樹的根節點

void build(int u, int l, int r) {
    if(l == r) return; //到達葉節點，返回
    int mid = (l + r) >> 1;
    lson = ++idx; // 左兒子編號為 idx + 1，並將 idx 加 1
    rson = ++idx; // 右兒子編號為 idx + 2，並將 idx 再次加 1
    build(lson, l, mid);
    build(rson, mid + 1, r);
}

int modify(int u, int l, int r, int x, int k) {
    int p = ++idx; // 開啟新的結點 p
    tr[p] = tr[u]; // 複製原節點的內容
    if(l == r) {
        tr[p].sum += k; // 到達葉子結點，直接修改數據
        return p;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) tr[p].lt = modify(lson, l, mid, x, k);
    else tr[p].rt = modify(rson, mid + 1, r, x, k);
    tr[p].sum = tr[tr[p].lt].sum + tr[tr[p].rt].sum;
    return p;
}

二、動態開點線段樹區間修改

在線段樹上做區間修改的時候，我們需要先找到要修改的區間的左右端點，然後不斷遞歸地向下處理，直到到達葉子節點，最後再遞歸回來更新每個節點的信息。由於我們使用了動態開點技術，所以在遍歷的時候，我們不能像普通線段樹一樣通過左右兒子的編號訪問它們，而是需要使用動態開點得到它們的實際編號。

下面是區間修改的代碼示例：

void modify(int p, int u, int l, int r, int ql, int qr, int k) {
    if(ql = r) { // 區間在當前區間內
        tr[p].sum += k * (r - l + 1);
        tr[p].tag += k; // 標記 one
        return;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid) {
        if(!tr[u].lt) tr[u].lt = ++idx; // 左兒子第一次被訪問時才開點
        modify(p < mid) {
        if(!tr[u].rt) tr[u].rt = ++idx; // 右兒子第一次被訪問時才開點
        modify(p << 1 | 1, tr[u].rt, mid + 1, r, ql, qr, k);
    }
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum + tr[u].tag * (r - l + 1); //更新信息
}

三、動態線段樹選取相關特殊操作

動態開點線段樹有一些特殊操作和普通線段樹不同，它們可以提高我們求解某些問題的效率。下面介紹一些比較常見的操作：

1. 求區間某個位置的值

在普通線段樹中，我們可以很輕鬆地求區間 [l, r] 中的最大值或最小值，但是如果要求區間內任意一個位置 i 的值時，就需要使用另外一種方法了。我們可以用一個數組 id 保存每個節點對應的區間範圍，然後根據查詢的位置不斷遞歸向下至葉子結點。如圖3-1所示。

下面是查詢區間某個位置的代碼示例：

int query(int p, int u, int l, int r, int x) {
    if(l == r) return tr[p].sum; // 已經到達葉節點
    int mid = (l + r) >> 1;
    if(x <= mid) {
        if(!tr[u].lt) tr[u].lt = ++idx; // 左兒子第一次被訪問時才開點
        return query(p << 1, tr[u].lt, l, mid, x) + tr[p].tag * (x - l + 1);
    }
    else {
        if(!tr[u].rt) tr[u].rt = ++idx; // 右兒子第一次被訪問時才開點
        return query(p << 1 | 1, tr[u].rt, mid + 1, r, x) + tr[p].tag * (r - x + 1);
    }
}

2. 求區間 [r-i+1, r] 任意數的和

在維護一段數列區間的前綴和時，我們可以直接使用線段樹來維護前綴和。但是，在動態開點線段樹中，如果要求區間 [r-i+1, r] 中任意數的和時，我們可以使用數據結構「主席樹」來維護。

下面是求區間 [r-i+1, r] 任意數的和的代碼示例：

void modify(int p, int u, int l, int r, int x, int k) {
    tr[p].sum += k;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) { // 修改左兒子的值
        if(!tr[u].lt) tr[u].lt = ++idx; // 左兒子第一次被訪問時才開點
        modify(p << 1, tr[u].lt, l, mid, x, k);
    }
    else { // 修改右兒子的值
        if(!tr[u].rt) tr[u].rt = ++idx; // 右兒子第一次被訪問時才開點
        modify(p << 1 | 1, tr[u].rt, mid + 1, r, x, k);
    }
}

int query(int p, int ul, int ur, int l, int r, int k) {
    if(l == r) return l;
    int cnt = tr[tr[p << 1 | 1].lt].sum - tr[tr[p <> 1;
    if(cnt >= k) return query(p << 1 | 1, tr[ul].rt, tr[ur].rt, mid + 1, r, k);
    else return query(p << 1, tr[ul].lt, tr[ur].lt, l, mid, k - cnt);
    // 在左兒子中查找
}

3. 求區間第 k 大/小的數

求解區間第 k 大/小的數，可以用上面的「主席樹」來解決。我們可以對每個節點開一個小根堆，記錄著區間內所有數字，然後就用主席樹的方法求解區間第 k 大/小的數。

下面是查詢區間第 k 大/小的代碼示例：

void pushup(int u) {
    tr[u].sum = tr[tr[u].lt].sum + tr[tr[u].rt].sum;
}
void modify(int p, int u, int l, int r, int x, int k) {
    tr[p].st.push(k); //將當前數加入小根堆中
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) {
        if(!tr[u].lt) tr[u].lt = ++idx; // 左兒子第一次被訪問時才開點
        modify(p << 1, tr[u].lt, l, mid, x, k);
    }
    else {
        if(!tr[u].rt) tr[u].rt = ++idx; // 右兒子第一次被訪問時才開點
        modify(p << 1 | 1, tr[u].rt, mid + 1, r, x, k);
    }
    pushup(u);
}

int query(int p, int ul, int ur, int l, int r, int k) {
    if(l == r) return l;
    int cnt = 0;
    //找出區間 [ul, ur] 中包含的數的個數
    for(int i = 0; i < tr[tr[p << 1].rt].st.size(); i++)
        if(tr[tr[p << 1].rt].st.top() <= r && tr[tr[p <= l) cnt++;
    int mid = (l + r) >> 1;
    if(cnt >= k) return query(p << 1, tr[ul].lt, tr[ur].lt, l, mid, k);
    else return query(p << 1 | 1, tr[ul].rt, tr[ur].rt, mid + 1, r, k - cnt);
}

總結

動態開點線段樹是一種非常實用的數據結構，其空間利用率非常高，能夠滿足很多實際問題的需求。在實現過程中，需要認真分析問題，考慮到各種特殊情況，才能寫出優秀的代碼，提高演算法效率。