成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【轉(zhuǎn)載】史上最簡單的平衡樹——無旋Treap

崔曉明 / 753人閱讀

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

【轉(zhuǎn)載】史上最簡單的平衡樹——無旋Treap
作者:fzszkl 博客地址:https://ac.nowcoder.com/discu... 使用此PDF文件時(shí)請保留上述信息!謝謝合作!覺得文章不錯(cuò)請點(diǎn)擊鏈接為博客點(diǎn)贊! 高能預(yù)警:所有示例代碼都是數(shù)組版的,歡迎copy!

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

一、簡介

無旋Treap,又稱fhq_treap,是范浩強(qiáng)大佬發(fā)明的一種強(qiáng)力數(shù)據(jù)結(jié)構(gòu).

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

對于初學(xué)者來說,它比Splay好學(xué),比Treap好用,實(shí)在不失為一個(gè)性價(jià)比極高的數(shù)據(jù)結(jié)構(gòu).

二、詳解

首先讓我們來復(fù)習(xí)一下平衡樹們的祖宗——二叉搜索樹的性質(zhì):

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

二叉搜索樹的插入,刪除,搜索等操作都容易被極端數(shù)據(jù)卡滿復(fù)雜度,這時(shí)我們就需要各種神奇操作來確保它的樹高期望大小為log級別.我們直接看無旋Treap是如何操作的(因?yàn)槠渌麕追N我不大會):

無旋Treap有兩種基本操作:

(1)分裂Split

將樹分為兩棵樹,其中樹A的最大點(diǎn)權(quán)小等于樹B的最小點(diǎn)權(quán).因?yàn)闃涓咂谕麨閘og,所以單次操作的復(fù)雜度期望為log.

(2)合并Merge

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

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

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

以下實(shí)例代碼中,0代表空節(jié)點(diǎn),Pushdown代表下傳標(biāo)記,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為當(dāng)前準(zhǔn)備拆開的節(jié)點(diǎn),A和B為左右子樹根節(jié)點(diǎn)的指針,Siz為拆分出的左子樹的大小.

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

首先確保你對指針有初步的認(rèn)識(因?yàn)槲乙仓挥谐醪降恼J(rèn)識),然后確保你牢記了二叉搜索樹的性質(zhì)(這樣你才能理解為什么要這樣拆分,不論如何拆分都不能改變節(jié)點(diǎn)從小到大中序排序的定律).

如果是按照權(quán)值拆分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是隨機(jī)權(quán)值,這樣我們就可以保證樹高的期望為log(蒟蒻口胡:因?yàn)樾纬砷L度為n的鏈的概率大概為$frac{1}{2^n}$乘一個(gè)組合數(shù)什么的).

兩種合并方法是等價(jià)的.都是把其中一個(gè)節(jié)點(diǎn)當(dāng)作這一步的根節(jié)點(diǎn),另一個(gè)節(jié)點(diǎn)和根節(jié)點(diǎn)的子樹遞歸合并.請?jiān)俅位貞浂嫠阉鳂涞男再|(zhì),所以我們一定要保證A在B的"左邊".

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

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

常規(guī)操作

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

插入節(jié)點(diǎn)

新建一個(gè)節(jié)點(diǎn),然后根據(jù)權(quán)值拆成左右子樹,然后Merge(Merge(左,新節(jié)點(diǎn)),右)即可.

刪除節(jié)點(diǎn)

根據(jù)權(quán)值拆成左右子樹和要拆除的節(jié)點(diǎn),然后直接Merge(左,右)即可.

區(qū)間操作

一般來講是通過Split剖出你需要操作的區(qū)間代表的子樹,然后在根節(jié)點(diǎn)打標(biāo)記,然后合并即可.

三、喜聞樂見小例題 (1)洛谷3369普通平衡樹:https://www.luogu.org/problem...

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

模板題,把上面除了區(qū)間操作以外的東西實(shí)現(xiàn)好即可.

AC代碼:https://www.luogu.org/recordn...
開啟O2優(yōu)化,洛谷更新數(shù)據(jù)后262ms

(2)洛谷3391文藝平衡樹:https://www.luogu.org/problem...

一個(gè)1到N的排列,M次操作,每次翻轉(zhuǎn)一個(gè)區(qū)間,求最后的排列.

只用實(shí)現(xiàn)區(qū)間操作即可,具體如何打標(biāo)記,下傳標(biāo)記請看代碼.

AC代碼:https://www.luogu.org/recordn...
開啟O2優(yōu)化,洛谷更新數(shù)據(jù)后488ms

(3)洛谷3372線段樹:https://www.luogu.org/problem...

區(qū)間加,區(qū)間求和.

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

AC代碼:https://www.luogu.org/recordn...
開啟O2優(yōu)化,洛谷更新數(shù)據(jù)后642ms

為什么最水的一題代碼反而最慢啊,新數(shù)據(jù)也太強(qiáng)了吧.

四、售后保障

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

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

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

本文PDF文件:

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

提取碼：mnc4

僅供學(xué)習(xí)交流使用!!!謝謝配合!!!

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/31839.html

相關(guān)文章

  • LuxTdmZtIC

    摘要：轉(zhuǎn)載史上最簡單的平衡樹無旋作者博客地址使用此文件時(shí)請保留上述信息謝謝合作覺得文章不錯(cuò)請點(diǎn)擊鏈接為博客點(diǎn)贊高能預(yù)警所有示例代碼都是數(shù)組版的歡迎前置知識線段樹請確保你完全理解最基礎(chǔ)的線段樹和區(qū)間加法和區(qū)間求和一簡介無旋又稱是范浩強(qiáng)大佬發(fā)明的一種 【轉(zhuǎn)載】史上最簡單的平衡樹——無旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    CoffeX 評論0 收藏0

  • LuxTdmZtIC

    摘要：轉(zhuǎn)載史上最簡單的平衡樹無旋作者博客地址使用此文件時(shí)請保留上述信息謝謝合作覺得文章不錯(cuò)請點(diǎn)擊鏈接為博客點(diǎn)贊高能預(yù)警所有示例代碼都是數(shù)組版的歡迎前置知識線段樹請確保你完全理解最基礎(chǔ)的線段樹和區(qū)間加法和區(qū)間求和一簡介無旋又稱是范浩強(qiáng)大佬發(fā)明的一種 【轉(zhuǎn)載】史上最簡單的平衡樹——無旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    tuantuan 評論0 收藏0

  • LuxTdmZtIC

    摘要：轉(zhuǎn)載史上最簡單的平衡樹無旋作者博客地址使用此文件時(shí)請保留上述信息謝謝合作覺得文章不錯(cuò)請點(diǎn)擊鏈接為博客點(diǎn)贊高能預(yù)警所有示例代碼都是數(shù)組版的歡迎前置知識線段樹請確保你完全理解最基礎(chǔ)的線段樹和區(qū)間加法和區(qū)間求和一簡介無旋又稱是范浩強(qiáng)大佬發(fā)明的一種 【轉(zhuǎn)載】史上最簡單的平衡樹——無旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    roundstones 評論0 收藏0

  • 架構(gòu)～微服務(wù) - 收藏集 - 掘金

    摘要：它就是史上最簡單的教程第三篇服務(wù)消費(fèi)者后端掘金上一篇文章，講述了通過去消費(fèi)服務(wù)，這篇文章主要講述通過去消費(fèi)服務(wù)。概覽和架構(gòu)設(shè)計(jì)掘金技術(shù)征文后端掘金是基于的一整套實(shí)現(xiàn)微服務(wù)的框架。 Spring Boot 配置文件 – 在坑中實(shí)踐 - 后端 - 掘金作者：泥瓦匠鏈接：Spring Boot 配置文件 – 在坑中實(shí)踐版權(quán)歸作者所有，轉(zhuǎn)載請注明出處本文提綱一、自動(dòng)配置二、自定義屬性三、ran...

    church 評論0 收藏0

  • 史上最簡單的SpringCloud教程 | 第三篇: 服務(wù)消費(fèi)者（Feign）

    摘要：一簡介是一個(gè)聲明式的服務(wù)客戶端，它使得寫服務(wù)變得更簡單。同時(shí)支持可插拔的編碼器和解碼器。對添加了支持，同時(shí)在中次用相同的。 轉(zhuǎn)載請標(biāo)明出處： http://blog.csdn.net/forezp/a...本文出自方志朋的博客 上一篇文章，講述了通過restTemplate+ribbon去消費(fèi)服務(wù)，這篇文章主要講述通過feign去消費(fèi)服務(wù)。 一、Feign簡介 Feign是一個(gè)聲明式的...

    0x584a 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<