<style> .reveal .slides { text-align: left; font-size:30px } </style> # Advanced Data Structure Introduction to Competitive Programming 2022/5/11 ---- - Treap - 動態開點線段樹 - 偽指標 - Persistent Data Sturcture --- ## 樹堆(Treap) Treap是一顆平衡二元樹 Treap = tree(二元樹) + heap(堆積) 每個節點有兩個重要的值：key, priority key用於存值，priority用來維護treap的平衡 ```cpp= struct Treap{ int key,pri,sz; //key,priority,size Treap *l, *r; //左右子樹 Treap(){} Treap(_key){ key = _key; pri = rand(); //隨機的數維持樹的平衡 sz = 1; l = r = nullptr; } } ``` ---- Treap滿足以下性質 1. 左子樹的 key 小於等於自己，右子樹的 key 大於等於自己(tree) 2. 父節點的 priority 大於其子節點的 priority (heap) 3. 左右子樹也分別是一顆treap 4. 給定 n 個節點的 key,priority 的大小關係，那麼這棵 treap 的形狀唯一。  ---- 做法 Treap分為旋轉式跟非旋轉式 這邊會介紹非旋轉式Treap，也就是merge-split treap 它易實作、期望複雜度好、靈活性高 幾乎每個操作都是 $O(lgN)$ 而主要有兩個函式 - split跟merge split 將一棵treap分成兩顆 merge 將兩棵treap合併成一棵 ---- ## merge-split treap ### merge 將兩棵Treap合併成一棵 (須保證左邊那棵Treap所有節點的key $\le$ 右邊那棵所有節點的key) <div style="margin-left:-140px"> ```cpp= int Size(Treap* x){ return x ? x->sz : 0 ; } void pull(Treap *x){ x->sz = Size(x->l) + Size(x->r) + 1;} Treap* merge(Treap *a,Treap *b){ if(!a || !b) return a ? a : b; //其中一個子樹為空則回傳另一個 if(a->pri > b->pri){ //如果a的pri比較大則a比較上面 a->r = merge(a->r,b); //將a的右子樹跟b合併 pull(a); return a; } else{ //如果b的pri比較大則b比較上面 b->l = merge(a,b->l); //將b的左子樹根a合併 pull(b); return b; } } ``` </div> ---- ## merge-split treap ### split by key 將一棵Treap分成兩棵， key小於等於k的分到左邊那棵a，其他分到右邊那棵b <div style="margin-left:-140px"> ```cpp= void splitByKey(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; } else if(x->key<=k){ a = x; splitByKey(x->r, k, a->r, b); pull(a); } else{ b = x; splitByKey(x->l, k, a, b->l); pull(b); } } ``` </div> ---- ## merge-split treap ### split by k-th 將一棵Treap分成兩棵， 左邊那棵a的節點數有k個，右邊那棵b節點數為n-k個 <div style="margin-left:-140px"> ```cpp= void splitByKth(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; } else if(Size(x->l) + 1 <= k){ a = x; //如果左子樹+自己的size小於等於k則左子樹跟自己為k個以內 splitByKth(x->r, k - Size(x->l) - 1, a->r, b); pull(a); } else{ b = x; //如果左子樹+自己的size大於k個則右子樹跟自己會分到右邊 splitByKth(x->l, k, a, b->l); pull(b); } } ``` </div> ---- 有以上split跟merge操作之後就可以完成大部分了! 像是插入元素或刪除都是在split和merge的基礎下操作 (記得左右順序要處理好!) <div style="margin-left:-165px"> ```cpp= void insert(int val){ //新增一個值為val的元素 Treap *x = new Treap(val); //設一個treap節點 Treap *l,*r; splitByKey(root, val, l, r); //找到新節點要放的位置 root = merge(merge(l,x),r); //合併到原本的treap裡 } void erase(int val){ //移除所有值為val的元素 Treap *l,*mid,*r; splitByKey(root, val, l, r); //把小於等於val的丟到l splitByKey(l, val-1, l, mid); //小於val的丟到l,等於val的就會在mid裡 root = merge(l,r); //將除了val以外的值合併 } ``` </div> ---- ## 複雜度分析 | build | split | merge | | --------- | -------- | -------- | | $O(NlgN)$ | $O(lgN)$ | $O(lgN)$ | <!-- [sample code](https://github.com/jakao0907/contest/blob/master/dataStructure/treap_split_key%26kth.cpp) --> ---- <div style="text-align:left;font-size:26px"> ### Treap and 懶標記 treap在處理序列問題非常強大像是以下題目 兩種操作： 1. 翻轉區間 $[l,r]$ 2. 詢問第 $i$ 格的值 我們可以用treap儲存序列 如果要翻轉一段區間則是將一棵treap交換他的左右子樹，並且他的所有子樹每個節點都交換左右子樹，就能達到翻轉區間 顯然，如果每次翻轉操作直接硬做，複雜度會爛掉 所以我們可以用一個懶標記，把要翻轉的區間記起來，下次走到再反轉，則複雜度就會降到好好的 $O(lgN)$ ```cpp= //記得在Treap結構裡加入變數tag void push(Treap* x){ if(x->tag){ //如果區間要翻轉 swap(x->l,x->r); //交換左右子樹 if(x->l) x->l->tag ^= 1; //加tag到左子樹 if(x->r) x->r->tag ^= 1; //加tag到右子樹 x->tag = NO_TAG; } } ``` </div> --- ## 動態開點線段樹 長度為 $N$ 的序列，每格值都為 0 $Q$ 筆操作 區間 [$l, r$] 加值 $v$ 區間 [$l, r$] 詢問總和 - $1 \le Q \le 10^5$ - $1 \le l \le r \le N \le 10^9$ 一般線段樹陣列不可能開到 $10^9$ 那麼大 ---- 兩種做法 1. 離散化 會發現 $Q$ 只有 $10^5$ 也就是最多只會有 $2 \cdot 10^5$ 那麼多種區間左右界 所以就可以開一個 $2 \cdot 10^5$ 那麼大的線段樹 2. 動態開點線段樹 想法: 線段樹每次 query, update 最多只會經過 $lgC$ 個節點 因此一開始可以只設一個根節點，當有需要遞迴到某個區間時， 再去設一個新的節點給那個區間 $Q$ 筆操作，每次最多只經過 $lgC$ 個節點 複雜度 $O(Q lgC)$ ---- ### 動態開點線段樹 一開始先設一個根節點，為全部區間的總和資訊 當詢問或更新時，在動態新增節點，每次最多只會新增 $lgN$ 個節點 結構如下，包括左右子節點的位置，區間總和以及區間修改的懶標記 ```cpp= struct node{ node *l, *r; int val,tag; }; ``` ---- ### 更新部分程式碼 會發現大部分長差不多，只是遞迴下去時要先判斷是否存在節點 ```cpp= void update(node *x, int l, int r, int ql, int qr, int v){ push(x, l, r); if(ql <= l && r <= qr){ x->tag += v; return; } int mid=(l+r)>>1; if(ql <= mid){ if(x->l == nullptr) x->l = new node(); //判斷是否有節點 update(x->l, l , mid, ql, qr, v); } if(qr > mid){ if(x->r == nullptr) x->r = new node(); //判斷是否有節點 update(x->r, mid+1, r, ql, qr, v); } pull(x, l, r); } ``` --- ## 可持久化資料結構 可持久化資料結構（Persistent data structure）是一種能夠在修改之後其保留歷史版本（即可以在保留原來數據的基礎上進行修改——比如增添、刪除、賦值）的資料結構。這種資料結構實際上是不可變對象，因為相關操作不會直接修改被保存的數據，而是會在原版本上產生一個新分支 --wikipedia ---- - 可持久化線段樹 - 可持久化並查集 - 可復原並查集 --- ## 可持久化線段樹 由於引入者黃嘉泰姓名的縮寫與前中共中央總書記、國家主席胡錦濤(H.J.T.)相同，因此這種資料結構也被稱為「主席樹」 功能：修改值，詢問值，回復歷史版本 如以下操作 1. 更新第 $i$ 格的值為 $v$ 2. 詢問區間 $[l,r]$ 的總和為多少 3. 將序列變回第 $k$ 次操作之前的版本 ---- 當有數值修改，如果每次都重新把整棵線段樹重新存一遍，則會花費過多的空間 操作 $k$ 次，則有 $k$ 個版本，空間複雜度為 $O(nk)$ 而觀察下面的圖會發現，如果我修改一個點的值，他最多只會更新 $lgN$ 個點，其他點不影響，所以其實如果有修改我只需要儲存那 $lgN$ 個點就好 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- 如下圖為例，一樣修改第 3 格的值，則將有變動到的節點重新存一遍，沒變動到的區間直接指向原本的地方 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- ### 實作細節 可持久化結構用指標比較容易實作 ```cpp= struct node{ ll val; node *l, *r; }; vector<node *> version; //用一個vector紀錄全部版本的根節點 void build(node *now_version, l, r); ll query(node *now_version, l, r, ql, qr); node *update_version(node *pre_version,int l,int r,int pos,int v); //回傳新建的節點 void add_version(int x,int v){ //修改位置 x 的值為 v version.push_back(update_version(version.back(), 0, n-1, x, v)); } ``` ---- ### 建新版本 ```cpp= node *update_version(node *pre_version, l, r, pos, v){ node *x = new node(); //當前位置建立新節點 if(l == r){ x->val = v; return x; } int mid = (l+r)>>1; if(pos <= mid){ //更新左邊 x->l = update(pre_version->l, l, mid, pos, v); //左邊節點連向新節點 x->r = pre->version->r; //右邊連到原本的右邊 } else{ //更新右邊 x->l = pre->version->l; //左邊連到原本的左邊 x->r = update(pre_version->r, r, mid, pos, v); //右邊節點連向新節點 } x->val = x->l->val + x->r->val; return x; } ``` ---- ### 用途 除了裸題以外，持久化線段樹還有很大的用途 如果題目的詢問是兩個以上的維度 給定長度為 $n$ 的序列 $a$，詢問 **區間 [l, r]** 之間，第 **$k$** 大的數字 $1 \le n \le 2 \cdot 10^5$ $1 \le a_i \le 10^9$ - 區間 $[l, r]$ - 第 $k$ 大 兩個維度 ---- 而我們其中一個維度可以用新增版本來解決 從原本可能 $O(N^2lgN)$ 的複雜度把一個 $N$ 變成 $lgN$ 第 $i$ 個版本的線段樹為前綴 $i$ 個元素的數字分別的個數， 每次二分搜 $prefix_r - prefix_{l-1}$ 小於某個值 有多少個數字 複雜度 $O(QlgNlgC)$ --- ## 持久化並查集 [例題](https://zerojudge.tw/ShowProblem?problemid=b412) 由於持久化並查集不能路徑壓縮 要使用 [啟發式合併](https://hackmd.io/@jakao/AdvancedTreeAlgorithm1#/2) ---- ### 想法 建一顆線段樹維護並集查，當有新版本的時候用持久化線段樹的方法 建立新版本 線段樹裡面存的就是每個節點的父親 因此我們要找某個點 $x$ 的集合時 就一直 query 線段樹，直到找到 query(x) == x 為止 ---- ### 細節 - build 遞迴到 l == r 的時候，將當前節點的值設為 r (並查集初始化 f[i] == i) - find 不斷 query 線段樹直到找到 x == father[x] 為止 ```cpp= int find(int x){ int fa = query(x); if(fa == x) return x; return find(fa); } ``` - update 建立新版本，將 $x, y$ 其中一個的父節點連到另外一個點 ---- ### 複雜度 - 詢問 找到集合次數均攤為 $O(lgN)$ 每次找父節點複雜度 $O(lgN)$ $\to$ 單筆詢問複雜度 $O(lgNlgN)$ - 修改 建立 $O(lgN)$ 個新結點 $\to$ 單筆詢問複雜度 $O(lgN)$ --- ## 可復原並查集 ## undo disjoint-set 包括以下操作 1. 詢問兩個點是否在同一個集合 2. 將兩個點合併在同一個集合 3. 回復上一個合併操作 一樣不能路徑壓縮，使用啟發式合併 ---- 觀察每次啟發式合併 將其中一個點的父節點連過去，並且把大小加過去 ```cpp= merge(int x,int y){ x = find(x); y = find(y); if(sz[x] > sz[y]){ sz[x] += sz[y]; fa[y] = x; } else{ sz[y] += sz[x]; fa[x] = y; } } ``` ---- 如果是 y 連到 x 每次合併會更新的兩個值 sz[x] fa[y] 因此我們只要每次更新時，記錄更動的值即可 ```cpp= vector<tuple<int,int,int>> version; merge(int x,int y){ x = find(x); y = find(y); if(sz[x] > sz[y]){ version.push_back({x,sz[x],y,fa[y]}); sz[x] += sz[y]; fa[y] = x; } else{ sz[y] += sz[x]; fa[x] = y; version.push_back({y,sz[y],x,fa[x]}); } } ``` ---- ## undo 回復上一次更新操作則將值改回去 ```cpp= void undo(int k=1){ //回復 k 次 auto [u,s,v,f] = version.back(); version.pop_back(); sz[u] = s; fa[v] = f; } ``` ---- 合併複雜度 $O(lgN)$ 回復複雜度 $O(1)$ --- ## Question Time and Practice [Homework Link](https://vjudge.net/contest/493374) 提交期限一星期 5/18 23:59 截止 下星期會是線上模擬賽: 18:30-21:30 詳細資訊 賽前會再公布 ---- ## 2022 海洋盃程式設計競賽 時間: 6/7 (二) 三人一隊 報名網址: https://forms.gle/xt1D5oZNwDvWwX4F8 最新消息: https://www.facebook.com/OceanCupProgrammingContest 有修程式競賽的會算入學期成績 全校各系都可以參加 會有高額獎金將於日後公布 歡迎大家分享給各系好友 >< ---- ## HP CodeWars 要一起去的 5/15 10:00 在系館前公車站集合