【老鼠看不懂的數據結構】FHQTreap 初識

来源:https://www.cnblogs.com/o2mouse/p/18206986
-Advertisement-
Play Games

title: Django與前端框架協作開發實戰:高效構建現代Web應用 date: 2024/5/22 20:07:47 updated: 2024/5/22 20:07:47 categories: 後端開發 tags: DjangoREST 前端框架 SSR渲染 SPA路由 SEO優化 組件庫 ...


Treap 弱平衡的隨機性很強的老鼠看不懂的平衡樹

Q:為什麼叫 Treap?
A:看看二叉搜索樹(BST)和堆(Heap),組合起來就是 Treap

其中,二叉搜索樹的性質是:
左子節點的值 (val) 比父節點小
右子節點的值 (val) 比父節點大

如果這些節點的值都一樣,這棵樹就會退化成一顆(?)鏈。

對, 我知道你在想什麼——並查集。
雖然都會被傻老鼠亂搞退化成鏈,但優化方式大有不同。

優化 - Priority - 玄學抽卡

笨蛋老鼠可能還有疑惑,為什麼鏈是naive的而樹是超棒的呢?
從OIwiki偷兩張圖來解釋:
看,這是一顆正常的樹,基本上可以看作滿二叉樹,一次查詢只需要 \(O(\log_2{n})\)的時間複雜度
正常的樹
這是一顆(?)被老鼠亂搞以後形成的鏈,一次查詢的時間複雜度劣化到了 \(O(n)\)
鏈
那麼,既然屑老鼠已經說了這棵樹有堆的性質,所以就要給每一個結點上一個隨機的優先順序\(Priority\)
讓它同時成為一個堆,在雙重特征下保持完全二叉樹的形狀

PS:傻老鼠腦子糊塗了,首先樹得滿足BST的性質,然後空下來時維護Heap的性質

大功告成,現在該知道節點裡面應該放什麼了。

node節點(為什麼不用類封裝?因為老鼠不會)
struct node{
	node *child[2];
	int val,ranf,cnt,siz;
	node(int __val) : val(__val), cnt(1), siz(1){
		child[0] = child[1] = nullptr;//左右兒子初始化 
		ranf = rand();//玄學抽卡 
	} 
	node(node *__node){
		val = __node->val, ranf = __node->ranf, cnt = __node->cnt, siz = __node->siz;
	}
	void ud_siz(){
		siz = cnt;
		if(child[0] != nullptr)siz += child[0]->siz;
		if(child[1] != nullptr)siz += child[1]->siz; 
	}
};

Treap的重要操作 Split & Merge

分裂過程接受兩個參數:根指針 \(\textit{cur}\)、關鍵值 \(\textit{key}\)。結果為將根指針指向的 treap 分裂為兩個 treap,第一個 treap 所有結點的值\(\textit{val}\)小於等於 \(\textit{key}\),第二個 treap 所有結點的值大於 \(\textit{key}\)
該過程首先判斷 \(\textit{key}\) 是否小於 \(\textit{cur}\) 的值,若小於,則說明 \(\textit{cur}\) 及其右子樹全部大於 \(\textit{key}\),屬於第二個 treap。當然,也可能有一部分的左子樹的值大於 \(\textit{key}\),所以還需要繼續向左子樹遞歸地分裂。對於大於 \(\textit{key}\) 的那部分左子樹,我們把它作為 \(\textit{cur}\) 的左子樹,這樣,整個 \(\textit{cur}\) 上的節點都是大於 \(\textit{key}\) 的。
相應的,如果 \(\textit{key}\) 大於等於 \(\textit{cur}\) 的值,說明 \(\textit{cur}\) 的整個左子樹以及其自身都小於 \(\textit{key}\),屬於分裂後的第一個 treap。並且,\(\textit{cur}\) 的部分右子樹也可能有部分小於 \(\textit{key}\),因此我們需要繼續遞歸地分裂右子樹。把小於 \(\textit{key}\) 的那部分作為 \(\textit{cur}\) 的右子樹,這樣,整個 \(\textit{cur}\) 上的節點都小於 \(\textit{key}\)
下圖展示了 \(\textit{cur}\) 的值小於等於 \(\textit{key}\) 時按值分裂的情況. ——OIWIKI

老鼠才不會解釋,因為老鼠沒腦子。

Split
pair<node *, node *> split(node *rt,int key){
	if(rt == nullptr)return {nullptr, nullptr};
	if(rt->val <= key){
	auto temp = split(rt->child[1],key);
		rt->child[1] = temp.first;
		rt->ud_siz();
		return {rt,temp.second};
	}
	else{
		auto temp = split(rt->child[0],key);
		rt->child[0] = temp.second;
		rt->ud_siz();
		return {temp.first,rt};
	}
	}

合併過程接受兩個參數:左 treap 的根指針 \(\textit{u}\)、右 treap 的根指針 \(\textit{v}\)。必須滿足 \(\textit{u}\) 中所有結點的值小於等於 \(\textit{v}\) 中所有結點的值。一般來說,我們合併的兩個 treap 都是原來從一個 treap 中分裂出去的,所以不難滿足 \(\textit{u}\) 中所有節點的值都小於 \(\textit{v}\)
在旋轉 treap 中,我們藉助旋轉操作來維護 \(\textit{priority}\) 符合堆的性質,同時旋轉時還不能改變樹的性質。在無旋 treap 中,我們用合併達到相同的效果。
因為兩個 treap 已經有序,所以我們在合併的時候只需要考慮把哪個樹「放在上面」,把哪個「放在下麵」,也就是是需要判斷將哪個一個樹作為子樹。顯然,根據堆的性質,我們需要把 \(\textit{priority}\) 小的放在上面(這裡採用小根堆)。
同時,我們還需要滿足搜索樹的性質,所以若 \(\textit{u}\) 的根結點的 \(\textit{priority}\) 小於 \(\textit{v}\) 的,那麼 \(\textit{u}\) 即為新根結點,並且 \(\textit{v}\) 因為值比 \(\textit{u}\) 更大,應與 \(\textit{u}\) 的右子樹合併;反之,則 \(\textit{v}\) 作為新根結點,然後因為 u 的值比 \(\textit{v}\) 小,與 v 的左子樹合併。——OIWIKI
老鼠懶,自己看。

Merge
node *merge(node *u,node *v){
		if(u == nullptr && v == nullptr)return nullptr;
		if(u != nullptr && v == nullptr)return u;
		if(u == nullptr && v != nullptr)return v;
		if(u->ranf < v->ranf){
			u->child[1] = merge(u->child[1],v);
			u->ud_siz();
			return u;
		}
		else{
			v->child[0] = merge(u, v->child[0]);
			v->ud_siz();
			return v;
		}
	}

不好用,才不用——⑨老鼠

作為笨蛋老鼠,能看懂這個東西怎麼用才奇怪吧,只能分裂和合併的數據結構,鬼才用嘞!
笨蛋老鼠!這個東西可以整很多活的

查詢小於等於val的數的個數:考察根節點的值和val,如果val小於根節點,遞歸進左子樹,否則遞歸進右子樹。
插入val:先查詢Rank(val),然後按照rank把整個TreapSplit成兩個,把val做成一個新節點,Merge到裡面。
刪除val:先查詢Rank(val),然後按照rank把整個TreapSplit成三個,刪除需要的點,最後Merge剩下兩個。
查詢第K個值:把整個TreapSplit成三個,輸出需要的值,最後合併起來。

好啊,你的區間呢?

誇下的海口終究會被打qwq。
發現了沒,這些個操作全是區間的,想想你的線段樹怎麼區間修改優化的?
\(LazyTag\)救我狗命對吧!
所以,直接打標記建線段樹到處亂搞,怎麼在樹鏈剖分上整的活大多數都能整!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 基於rake的爬取代碼 require 'nokogiri' require 'json' require 'open-uri' namespace :spider_sbi_code_info do task table_data: :environment do options = Seleniu ...
  • 正文 中午睡得真的好香,一點都不想起床上班。我要鬧了!為什麼世界上會有上班這麼邪惡的事情。 今天開了一個一般戶。剛開始資料散成一堆,得有二十張。各種找。最後還是出了點岔子,讓客戶沒簽字就跑了。算了,無所謂了。 上午綜合各家 AI 和已有的宣傳稿,寫了一篇稿子發出去。能不能被選中投上那就不是我的事了。 ...
  • 在做商城時生成隨機一個頭像,找了一下發現用首個字元直接生成的類也不錯,和用第三方外鏈的話還是有不同的,第三方雖然圖片比較多,但是會有超時問題,所以用首字母生成方式本地搞,代碼如下: 點擊查看代碼 1、方法調用測試 letter_avatar("壹零柒") 2、生成圖片方法 function lett ...
  • Qt具有跨平臺的特性,即Qt數據結構與演算法庫本身跨平臺和編譯腳本(.pro)跨平臺。在同時具有Windows下和Linux開發的需求時,最好的建議是使用QtCreator來開發,雖然也可以使用其他的IDE配合CMake等方式,但使用QtCreator更加方便,並且操作環境完全一致。QtCreator ...
  • 使用Spring Boot開發API的時候,讀取請求參數是服務端編碼中最基本的一項操作,Spring Boot中也提供了多種機制來滿足不同的API設計要求。 接下來,就通過本文,為大家總結6種常用的請求參數讀取方式。如果你發現自己知道的不到6種,那麼趕緊來查漏補缺一下。如果你知道的不止6種,那麼告訴 ...
  • 亮數據,適合大模型數據準備的可視化高效率數據採集工具。 一、大模型訓練需要數據 大模型數據處理的流程,分為數據採集、數據清洗、數據評估和指令數據標註四個主要階段,而這些階段中最重要的就是數據採集階段,需要海量的數據才能讓大模型涌現智能。 訪問點擊: 亮數據加速數據採集。 數據採集 涉及多種數據源,包 ...
  • 相關參考 https://leejjon.medium.com/how-to-allow-cross-origin-requests-in-a-jax-rs-microservice-d2a6aa2df484 https://stackoverflow.com/questions/28065963/ ...
  • 配置 NGINX 和 NGINX Plus 作為 Web 伺服器 設置虛擬伺服器 在 NGINX Plus 配置文件中,必須包含至少一個 server 指令來定義一個虛擬伺服器。 當 NGINX Plus 處理請求時,首先選擇將服務於該請求的虛擬伺服器。 http { server { # 伺服器配 ...
一周排行
    -Advertisement-
    Play Games
  • 通過WPF的按鈕、文本輸入框實現了一個簡單的SpinBox數字輸入用戶組件並可以通過數據綁定數值和步長。本文中介紹了通過Xaml代碼實現自定義組件的佈局,依賴屬性的定義和使用等知識點。 ...
  • 以前,我看到一個朋友在對一個系統做初始化的時候,通過一組魔幻般的按鍵,調出來一個隱藏的系統設置界面,這個界面在常規的菜單或者工具欄是看不到的,因為它是一個後臺設置的關鍵界面,不公開,同時避免常規用戶的誤操作,它是作為一個超級管理員的入口功能,這個是很不錯的思路。其實Winform做這樣的處理也是很容... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他的程式每次關閉時就會自動崩潰,一直找不到原因讓我幫忙看一下怎麼回事,這位朋友應該是第二次找我了,分析了下 dump 還是挺經典的,拿出來給大家分享一下吧。 二:WinDbg 分析 1. 為什麼會崩潰 找崩潰原因比較簡單,用 !analyze -v 命 ...
  • 在一些報表模塊中,需要我們根據用戶操作的名稱,來動態根據人員姓名,更新報表的簽名圖片,也就是電子手寫簽名效果,本篇隨筆介紹一下使用FastReport報表動態更新人員簽名圖片。 ...
  • 最新內容優先發佈於個人博客:小虎技術分享站,隨後逐步搬運到博客園。 創作不易,如果覺得有用請在Github上為博主點亮一顆小星星吧! 博主開始學習編程於11年前,年少時還只會使用cin 和cout ,給單片機點點燈。那時候,類似async/await 和future/promise 模型的認知還不是 ...
  • 之前在阿裡雲ECS 99元/年的活動實例上搭建了一個測試用的MINIO服務,以前都是直接當基礎設施來使用的,這次準備自己學一下S3相容API相關的對象存儲開發,因此有了這個小工具。目前僅包含上傳功能,後續計劃開發一個類似圖床的對象存儲應用。 ...
  • 目錄簡介快速入門安裝 NuGet 包實體類User資料庫類DbFactory增刪改查InsertSelectUpdateDelete總結 簡介 NPoco 是 PetaPoco 的一個分支,具有一些額外的功能,截至現在 github 星數 839。NPoco 中文資料沒多少,我是被博客園群友推薦的, ...
  • 前言 前面使用 Admin.Core 的代碼生成器生成了通用代碼生成器的基礎模塊 分組,模板,項目,項目模型,項目欄位的基礎功能,本篇繼續完善,實現最核心的模板生成功能,並提供生成預覽及代碼文件壓縮下載 準備 首先清楚幾個模塊的關係,如何使用,簡單畫一個流程圖 前面完成了基礎的模板組,模板管理,項目 ...
  • 假設需要實現一個圖標和文本結合的按鈕 ,普通做法是 直接重寫該按鈕的模板; 如果想作為通用的呢? 兩種做法: 附加屬性 自定義控制項 推薦使用附加屬性的形式 第一種:附加屬性 創建Button的附加屬性 ButtonExtensions 1 public static class ButtonExte ...
  • 在C#中,委托是一種引用類型的數據類型,允許我們封裝方法的引用。通過使用委托,我們可以將方法作為參數傳遞給其他方法,或者將多個方法組合在一起,從而實現更靈活的編程模式。委托類似於函數指針,但提供了類型安全和垃圾回收等現代語言特性。 基本概念 定義委托 定義委托需要指定它所代表的方法的原型,包括返回類 ...