平衡樹總結

平衡樹剛看的時候覺得很不好評價。

但它畢竟就是個數據結構，跟線段樹的用途一樣，都是用來維護數據。想想你剛看線段樹時候的感受，是不是和現在剛看平衡樹差不多。

事實來看，平衡樹也不復雜。本質都是二叉搜索樹，只不過維護平衡的方式不一樣罷了。平衡樹的類型看似那么多，實際上也就學兩種：FHQ Treap 和 Splay。實在不行，還有 pb_ds 兜底。

那就開干。

二叉查找樹 (Binary Search Tree, BST)

特征

BST 有以下特征。

每個節點有唯一的鍵值，可以比較大小。
任意節點的鍵值大于其左子樹所有節點的鍵值，小于其右子樹所有節點的鍵值。
以任意節點為根的一棵子樹，仍然是 BST。

優點

可以輕松地插入節點、刪除節點
可以輕松地查詢節點的排名或根據排名查找節點
可以查詢節點的前驅后繼

尤其是第一點，相較于線段樹等數據結構，BST 的輕松插入刪除節點是其最大優勢。

時間復雜度的退化

理論上來說，BST 的單次操作時間復雜度都是 \(O(\log N)\)。但是，在構造數據下，BST 會退化成鏈，時間復雜度退化至 \(O(N)\)。

平衡樹就是為了解決這個問題的。平衡樹有很多種，都是通過不同的方式維護 BST 的平衡。所以，平衡樹就是 BST。

FHQ Treap

它是 Treap 的變體，由范浩強巨佬發明，救無數 OIer 于平衡樹水火。

話說到平衡樹要維護 BST 的平衡，Treap 就是其中一種維護方式。Treap 是 Tree 和 Heap 的合成詞，顧名思義，就是給每個節點人為添加一個『優先級』，隨機生成即可。對于鍵值，這棵樹是一棵 BST；對于優先級，這棵樹是一個堆。隨機生成的優先級保證了時間復雜度從概率期望上看是 \(O(\log N)\)。

平衡樹題目都需要動態維護樹的平衡，在 FHQ 發明以前一直用的是旋轉法。FHQ 相較于旋轉法，不僅編碼簡單，還能用于區間翻轉、移動、可持久化等多種場合，并一舉代替了許多原本只能用 Splay 完成的題目。

FHQ 來維護所有平衡樹操作的方法都只用到了分裂和合并這兩個基本操作。而分裂的方法也有兩種：按鍵值分裂和按排名分裂。

按鍵值分裂

分裂方法：將原樹分裂為鍵值小于等于當前元素和鍵值大于當前元素的兩棵。

這種適用于維護元素排名、不強調元素順序的基本場合。

~~為什么說是基本呢？因為在呂教練給我們的平衡樹題單中，所有的這種場合都被我用 pb_ds 水掉了~~

void split(int u, int x, int &l, int &r) {
    if (u == 0) return l = r = 0, void();
    if (t[u].key <= x) {
        l = u;
        split(t[u].rs, x, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    update(u);
}

int combine(int l, int r) {
    if (!l || !r) return l | r;
    if (t[l].pri > t[r].pri) {
        t[l].rs = combine(t[l].rs, r);
        return update(l);
    } else {
        t[r].ls = combine(l, t[r].ls);
        return update(r);
    }
}

可以看出，代碼非常巧妙，也簡單易寫。

這里的 update 類似于線段樹的 pushup，主要內容就是將左右節點維護的信息合并到父節點上。在模板題中，我們只需維護一個子樹大小，所以 update 函數中的內容也很簡單：

int update(int u) {
    t[u].sz = t[t[u].ls].sz + t[t[u].rs].sz + 1;
    return u;
}

接下來我們來看分裂和合并是如何維護平衡樹的基本操作的。

插入一個元素：將原樹按鍵值分裂，然后新建一個節點，最后按『左樹、新建節點、右樹』的順序將其合并。

int newnode(int x) {
    t[++tot].sz = 1;
    t[tot].key = x;
    t[tot].pri = rand();
    return tot;
}

void ins(int x) {
    int l, r;
    split(rt, x, l, r);
    rt = combine(combine(l, newnode(x)), r);
}

刪除一個元素：分裂兩次，將原樹分裂為左樹、中樹（鍵值只有待刪除元素）、右樹，將中樹的左右子樹合并（相當于刪除了一個待刪除元素），最后再將其和左右樹合并。（注意順序）

void del(int x) {
    int l, r, p;
    split(rt, x, l, r);
    split(l, x - 1, l, p);
    p = combine(t[p].ls, t[p].rs);
    rt = combine(combine(l, p), r);
}

查詢一個元素的排名：按鍵值分裂，排名即為左樹的大小加一，最后合并（相當于恢復原狀）。

int rnk(int x) {
    int l, r;
    split(rt, x - 1, l, r);
    int res = t[l].sz + 1;
    rt = combine(l, r);
    return res;
}

按排名查詢元素：簡單，從根節點開始，如果排名等于左子樹，即為查詢成功，直接返回；如果排名小于左子樹，向左遞歸查詢；如果排名大于左子樹，向右遞歸查詢（函數參數中的待查排名要減去左子樹大小）。

int kth(int k, int u = rt) {
    if (k == t[t[u].ls].sz + 1) return t[u].key;
    if (k <= t[t[u].ls].sz) return kth(k, t[u].ls);
    return kth(k - t[t[u].ls].sz - 1, t[u].rs);
}

查詢元素前驅：按鍵值分裂，查找左樹中的最大元素（利用 kth 函數操作），最后合并。

int pre(int x) {
    int l, r;
    split(rt, x - 1, l, r);
    int res = kth(t[l].sz, l);
    rt = combine(l, r);
    return res;
}

查詢元素后繼：同理，按鍵值分裂后查找右樹中的最小元素，最后合并。

int nxt(int x) {
    int l, r;
    split(rt, x, l, r);
    int res = kth(1, r);
    rt = combine(l, r);
    return res;
}

可以看出，所有的操作都只需維護一個根節點位置即 \(\mathit{rt}\)，所有的函數都只需傳入一個待查參數即可返回結果，非常地模板化。

例題：P3369，P6136，P2286，P1486。

以上題目全部能用 pb_ds 解決，見下文。

按排名分裂

分裂方法：將原樹分裂為位于當前元素左側和位于當前元素右側的兩棵。

適用于強調元素順序、不強調元素排名的高級場合。

void split(int u, int x, int &l, int &r) {
    if (u == 0) return l = r = 0, void();
    if (t[t[u].ls].sz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].sz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    update(u);
}

實際上也很顯然，有點類似上文 kth 函數的查找方法。

例題：P3391，P4309，P4036。

P3391 中的『翻轉』在二叉樹中的處理方法是：以區間中任意數為軸翻轉左右兩邊，然后對左右兩部分再遞歸處理。所以我們很自然地有類似線段樹的懶標記思想，每次通過分裂提取出翻轉的區間，給這個區間打上懶標記，隨后定期 pushdown 即可。

P4309 是一個 LIS 問題加入動態維護。我們注意到題目中的一個特性：插入元素是從小到大插入的。這意味著我們但凡插入元素，從序列開始到新元素的這個部分的 LIS 長度必定會加一。我們在 pushup 函數中多維護一個變量 \(\mathit{len}\) 表示總樹的 LIS 長度，而 \(\mathit{key}\) 維護當前節點的 LIS 長度，按照如下方法去 pushup \(\mathit{len}\) 即可。

\[\text t[u].\mathit{len}=\max(\text t[\mathit{ls}].\mathit{len},\text t[\mathit{rs}].\mathit{len},\text t[u].\mathit{key}) \]

P4036 題目給定的操作是求最長公共前綴 + 動態插入修改。首先字符串肯定 Hash 存儲沒有問題，插入修改編碼都容易，重點在于如何維護 Hash 值。但前提是我們知道了子樹大小，Hash 值也很好維護了。

\[\text t[u].\mathit{hs}=\text t[\mathit{ls}].\mathit{hs}\times\mathrm P^{\text t[\mathit{rs}].\mathit{sz}+1}+\text t[u].\mathit{key}\times\mathrm P^{\text t[\mathit{rs}].\mathit{sz}}+\text t[\mathit{rs}].\mathit{hs} \]

還是很好理解的。最后就是求 \(\operatorname{LCQ}\) 函數，相較于暴力的比較，由于范圍是確定的，所以可以二分答案解決。時間復雜度 \(O(M\log L)\)。當然此題暴力可過。

Splay

在 FHQ Treap 下被邊緣化的平衡樹。不想講，等到我學某更高級的數據結構時再說吧。

pb_ds

相當于按鍵值分裂的平衡樹模板，簡單講一下它的用法。

頭文件 + 命名空間：

#include <bits/extc++.h>
using namespace __gnu_pbds;

格式：

tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> t;

第一個參數表示要維護的平衡樹的元素類型。這里填成 pii 是因為 pb_ds 默認情況下類似一個 set 而不是 multiset，所以插入相同元素時要賦予不同的第二值。
第二個參數表明你想不想實現 map 的效果，如果不想就填成 null_type。
第三個參數是排序函數，如果填成 greater<pii> 就變成從大到小查找排名了。
第四個參數決定了平衡樹的內部實現類型，一般填 rb_tree_tag 即紅黑樹效率最高。
第五個參數決定了你的平衡樹是否支持上文的 rnk 函數和 kth 函數的功能。很長，但打多了也就記住了。如果你不需要，你就只需填前兩個參數就行了，后三個參數都有默認指定。

下面說一下如何用 pb_ds 的平衡樹通過 P3369 模板題。

插入一個元素：如下，其中 \(i\in[1,n]\)，相當于給相同元素賦予了不同的第二值。

t.insert(make_pair(k, i));

刪除一個元素：題目保證了待刪除的元素一定存在，所以用 lower_bound 可以刪除一個存在于平衡樹中的待刪除的元素。

t.erase(t.lower_bound(make_pair(k, 0)));

查詢一個元素的排名：排名的定義為小于待查詢元素的元素個數加一，所以函數參數不一定需要在平衡樹中存在。

cout << t.order_of_key(make_pair(k, 0)) + 1 << '\n';

按排名查詢元素：注意給出的排名要減一作為函數參數。

cout << t.find_by_order(k - 1)->first << '\n';

查詢元素前驅：pb_ds 對此沒有特定函數，需要我們善用 lower_bound。

cout << (--t.lower_bound(make_pair(k, 0)))->first << '\n';

查詢元素后繼：pb_ds 對此也沒有特定函數，需要我們善用 upper_bound。

cout << (t.upper_bound(make_pair(k, INT_MAX)))->first << '\n';

由此可見，pb_ds 的平衡樹基本可以實現按鍵值分裂的 FHQ Treap 的所有功能了。

pb_ds 的缺點是過于模板化導致不夠靈活，只能拿來做一些板題。pb_ds 默認不支持 multiset 也導致其很麻煩，做樹套樹就更不容易。

番外：ETT (Euler Tour Tree)

posted @ 2024-08-20 19:53 Laoshan_PLUS 閱讀(169) 評論(0) 收藏舉報

刷新頁面返回頂部

laoshan-plus