摘要：轉載史上最簡單的平衡樹無旋作者博客地址使用此文件時請保留上述信息謝謝合作覺得文章不錯請點擊鏈接為博客點贊高能預警所有示例代碼都是數組版的歡迎前置知識線段樹請確保你完全理解最基礎的線段樹和區間加法和區間求和一簡介無旋又稱是范浩強大佬發明的一種

前置知識:線段樹!請確保你完全理解最基礎的線段樹和LazyTag(區間加法和區間求和).

無旋Treap,又稱fhq_treap,是范浩強大佬發明的一種強力數據結構.

總的來說,它可以支持一切Treap和Splay等平衡樹的操作,支持可持久化(但是這篇博客不會講),常數遠小于Splay,但是處理LCT問題略比Splay遜色,以至于我到現在還不會.

對于初學者來說,它比Splay好學,比Treap好用,實在不失為一個性價比極高的數據結構.

首先讓我們來復習一下平衡樹們的祖宗——二叉搜索樹的性質:

遞歸定義,空樹是一棵二叉搜索樹,二叉搜索樹的左子樹的最大點權小等于根的點權小等于右子樹的最小點權,二叉搜索樹的左右子樹也是二叉搜索樹.

二叉搜索樹的插入,刪除,搜索等操作都容易被極端數據卡滿復雜度,這時我們就需要各種神奇操作來確保它的樹高期望大小為log級別.我們直接看無旋Treap是如何操作的(因為其他幾種我不大會):

無旋Treap有兩種基本操作:

將樹分為兩棵樹,其中樹A的最大點權小等于樹B的最小點權.因為樹高期望為log,所以單次操作的復雜度期望為log.

將兩棵樹合為一棵樹,其中樹A的最大點權小等于樹B的最小點權.為了保證樹高期望為log,我們要想辦法隨機合并.

沒了(臥槽你啥都沒說啊).

好吧,為了博客過審,還是再來仔細講一下.

以下實例代碼中,0代表空節點,Pushdown代表下傳標記,Pushup代表向上更新.

先來看一眼Split:

void Split( int Nod , int Siz , int &A , int &B ) {
    if( Nod == 0 ) return (void)( A = B = 0 ) ;
    Pushdown( Nod ) ;
    if( Siz <= Size[Ls[Nod]] ) B = Nod , Split( Ls[Nod] , Siz , A , Ls[Nod] ) ;
        else A = Nod , Split( Rs[Nod] , Siz - Size[Ls[Nod]] - 1 , Rs[Nod] , B ) ;
    Pushup( Nod ) ;
}

Nod為當前準備拆開的節點,A和B為左右子樹根節點的指針,Siz為拆分出的左子樹的大小.

翻譯成人話:當拆分的大小不超過左子樹大小時,當前節點會被分配到右子樹(B=Nod),然后進入左子樹進行拆分,拆分下來的左子樹仍舊傳到A,拆下來的右子樹則作為當前節點的左子樹,否則同理.

首先確保你對指針有初步的認識(因為我也只有初步的認識),然后確保你牢記了二叉搜索樹的性質(這樣你才能理解為什么要這樣拆分,不論如何拆分都不能改變節點從小到大中序排序的定律).

如果是按照權值拆分Split,稍微改一下就好了.

然后看一眼Merge:

int Merge( int A , int B ) {
    if( A == 0 or B == 0 ) return A | B ;
    register int Ans ;
    Pushdown( A ) ;
    Pushdown( B ) ;
    if( Pos[A] > Pos[B] ) Rs[A] = Merge( Rs[A] , B ) , Ans = A ;
        else Ls[B] = Merge( A , Ls[B] ) , Ans = B ;
    Pushup( Ans ) ;
    return Ans ;
}

Pos是隨機權值,這樣我們就可以保證樹高的期望為log(蒟蒻口胡:因為形成長度為n的鏈的概率大概為$frac{1}{2^n}$乘一個組合數什么的).

兩種合并方法是等價的.都是把其中一個節點當作這一步的根節點,另一個節點和根節點的子樹遞歸合并.請再次回憶二叉搜索樹的性質,所以我們一定要保證A在B的"左邊".

一定要注意啊,Merge(A,B)和Merge(B,A)天差地別啊!

有了這兩種看上去就特別nb的操作,我們組合一下,就可以完成很多nb的事情啦~

查排名,查前驅后繼等操作同普通平衡樹,在樹上dfs即可.不過為了體現無旋Treap的優越,下方給出的實例代碼是利用兩種基本操作實現的,優點在于直觀,好寫,缺點在于比起直接dfs的話常數略大.

新建一個節點,然后根據權值拆成左右子樹,然后Merge(Merge(左,新節點),右)即可.

根據權值拆成左右子樹和要拆除的節點,然后直接Merge(左,右)即可.

一般來講是通過Split剖出你需要操作的區間代表的子樹,然后在根節點打標記,然后合并即可.

需要支持插入,刪除,查元素排名和排名元素,查前驅后繼.

模板題,把上面除了區間操作以外的東西實現好即可.

AC代碼:https://www.luogu.org/recordn...
開啟O2優化,洛谷更新數據后262ms

一個1到N的排列,M次操作,每次翻轉一個區間,求最后的排列.

只用實現區間操作即可,具體如何打標記,下傳標記請看代碼.

AC代碼:https://www.luogu.org/recordn...
開啟O2優化,洛谷更新數據后488ms

區間加,區間求和.

這個例子是為了方便大家理解LazyTag,做好線段樹到平衡樹,或者普通平衡樹到區間平衡樹的銜接,特意忍辱負重寫了這篇代碼.是不是超級良心~

AC代碼:https://www.luogu.org/recordn...
開啟O2優化,洛谷更新數據后642ms

為什么最水的一題代碼反而最慢啊,新數據也太強了吧.

什么?博客太爛了看不懂?

推薦閱讀:http://iwo.im/?q=%E6%97%A0%E6...

(↑↑↑看完你會回來點贊的.)

本文PDF文件:

鏈接：https://pan.baidu.com/s/1vR9d...

提取碼：mnc4

僅供學習交流使用!!!謝謝配合!!!