国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【轉載】史上最簡單的平衡樹——無旋Treap

崔曉明 / 732人閱讀

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

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

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

一、簡介

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

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

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

二、詳解

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

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

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

無旋Treap有兩種基本操作:

(1)分裂Split

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

(2)合并Merge

將兩棵樹合為一棵樹,其中樹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剖出你需要操作的區間代表的子樹,然后在根節點打標記,然后合并即可.

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

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

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

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

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

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

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

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

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

區間加,區間求和.

這個例子是為了方便大家理解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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31839.html

相關文章

  • LuxTdmZtIC

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

    CoffeX 評論0 收藏0

  • LuxTdmZtIC

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

    tuantuan 評論0 收藏0

  • LuxTdmZtIC

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

    roundstones 評論0 收藏0

  • 架構～微服務 - 收藏集 - 掘金

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

    church 評論0 收藏0

  • 史上最簡單的SpringCloud教程 | 第三篇: 服務消費者（Feign）

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

    0x584a 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<