# 資讀--資料結構 --- # 前言 我會盡量打得詳細、易懂，但可能沒那麼嚴謹 會持續更新(我要連講兩個禮拜) 0-base/1-base看上下文而定 $[l,r]$：左閉右閉 $[l,r)$：左閉右開 我：22703 王培軒 (身為27如此之弱真是慚愧) 整份講義有任何問題歡迎+我FB(本名)然後私訊我 --- # 資料結構？ 儲存資料的方式。 各種演算法常常需要搭配各種資料結構使用，可以在時間、空間上得到大幅的改善。 --- # 前綴、差分 (這算資料結構嗎？) ---- ## 前綴和(Prefix Sum) 一陣列$a$，定義前綴和陣列$p$，$p_i=\sum^{i}_{j=0}a_j$ ---- 如何建立？ ```cpp= int a[N],p[N]; p[0]=a[0]; for(int i=1;i<n;i++) p[i]=p[i-1]+a[i]; ``` 用途？ $O(1)$求區間和(靜態) $sum[l,r]=p[r]-p[l-1]$ ---- ## 差分 一陣列$a$，定義差分陣列$d$，$d_i=a_i-a_{i-1}$ ---- 如何建立？直接做啊 用途？區間修改->單點修改 將$a$中$[l,r]$全部的值$+x$就是將$d_l+x,d_{r+1}-x$ 最後再做前綴就可得到原序列 ---- ## 例題 [CSES Static Range Sum Queries](https://cses.fi/problemset/task/1646) [TIOJ 1227](https://tioj.ck.tp.edu.tw/problems/1227) (俯拾皆是，去CF戳就有一堆) ---- 酷酷小思考題 給你一個長度為$n$的陣列$a$，請判斷是否能找到一段連續子序列使得其和為$n$的倍數 <span>一定有：前綴和+鴿籠原理！<!-- .element class="fragment" data-fragment-index="1" --></span> --- # 線段樹 (Segment Tree) --- ## 基本線段樹 ---- 萬年不變經典題： 長度為$n$的陣列$a$，$q$筆詢問，每次： 1. 詢問$[l,r]$的總和 2. 將$a_i$設為$x$ $n \leq 10^5,q \leq 10^5$ 暴力做太慢，用前綴和又沒辦法好好修改... ---- 線段樹  (他畫錯了==第三層右邊兩格應該是5-6跟7-8) ---- * 幾乎完全二元樹 * 每個節點維護一個區間的資訊 * $O(\log{N})$層 * 每次修改只會改到$O(\log{N})$個節點！ * 每次查詢在每一層最多取兩個節點！(嚴謹證明就留給讀者自行思考練習) ---- ### 實作 陣列型：1-base，以$seg[1]$為根，對於每個節點$seg[cur]$，左子節點為$seg[2*cur]$，右子節點為$seg[2*cur+1]$ (另外還有指標型、偽指標型、迭代型等等) ```cpp= const int N=2e5+5; int seg[N*4]; void modify(int l,int r,int cur,int ind,int val){ if(r-l<=1){ seg[cur]=val; return; } int mid=(l+r)/2; if(ind<mid) modify(l,mid,cur*2,ind,val); else modify(mid,r,cur*2+1,ind,val); seg[cur]=seg[cur*2]+seg[cur*2+1]; } /* left,right,current,index,value [l,r):目前節點區間 cur:目前節點存在的位置 一開始呼叫modify(1,n+1,1,pos,x) */ int query(int l,int r,int cur,int ql,int qr){ if(ql>=r||qr<=l) return 0;//目前區間與目標區間無交集->return if(ql<=l&&qr>=r) return seg[cur];//目標區間包含目前區間->全取 int mid=(l+r)/2; return query(l,mid,cur*2,ql,qr)+query(mid,r,cur*2+1,ql,qr);//遞迴處理 } ``` ---- ### 應用 基本線段樹中可以維護各種有結合律的操作，如： 1. 和 2. 積 3. XOR SUM 4. 某個數字有幾個 ...不勝枚舉。 沒有交換律的運算也是可以做的。 ---- ### 裸題 看看你寫的東西有沒有bug！ [CSES 裸題](https://cses.fi/problemset/task/1648) --- ## 懶標 (Lazy Tag) ---- 萬年不變經典題加強版： 長度為$n$的陣列$a$，$q$筆詢問，每次： 1. 詢問$[l,r]$的總和 2. 將$[l,r]$的值都$+x$ $n \leq 10^5,q \leq 10^5$ 此類稱為區間加值區間和，也可能是區間改值，或者要同時處理 剛剛的線段樹沒辦法好好做了... ---- 懶懶得做就可以了！ 每次修改時，當目前區間被修改區間包含時，改變那個節點的值並打上標記就return！ 下次走到該節點時，若需要往子樹走，先把標記往下推！(詢問/修改皆同) 標記：在節點上記錄修改資訊 下推：以目前節點的標記，修改子節點並打標記 ---- 為甚麼是好的： 每次修改只會走到$O(\log{N})$個節點，所以最多下推$O(\log{N})$次 詢問時亦同 ---- 實作幾個函數： 1. upd：修改當前節點的值並打上標記 2. push：將懶標下推，即將子節點以目前節點標記的值去修改 3. pull：以左子節點和右子節點上拉更新目前節點的資訊 加上原本的modify跟query 大部分的懶標線段樹套上這個架構後，就能搞定！ (其實寫法很多，有些情況根本不用下推，但這樣的架構是幾乎通用的吧(?) ---- ### 實作 以剛剛的區間加值區間和舉例 ```cpp= const int N=2e5+5; int seg[N*4]{0},tag[N*4]{0}; void update(int l,int r,int cur,int val){ seg[cur]+=(r-l)*val; tag[cur]+=val; } void push(int l,int r,int cur){ int mid=(l+r)/2; upd(l,mid,cur*2,tag[cur]); upd(mid,r,cur*2+1,tag[cur]); tag[cur]=0; } void pull(int cur){ seg[cur]=seg[cur*2]+seg[cur*2+1]; } void modify(int l,int r,int cur,int ql,int qr,int val){ if(ql>=r||qr<=l) return; if(ql<=l&&qr>=r) return update(l,r,cur,val),void(); int mid=(l+r)/2; push(l,r,cur); modify(l,mid,cur*2,ql,qr,val); modify(mid,r,cur*2+1,ql,qr,val); pull(cur); } int query(int l,int r,int cur,int ql,int qr){ if(ql>=r||qr<=l) return 0; if(ql<=l&&qr>=r) return seg[cur]; int mid=(l+r)/2; push(l,r,cur); return query(l,mid,cur*2,ql,qr)+query(mid,r,cur*2+1,ql,qr); } ``` ---- ### 裸題 如此就算是把基本款的線段樹學完了！ [CSES 裸題](https://cses.fi/problemset/task/1651) --- ## 指標型、動態開點 (Sparse Segment Tree) ---- 指標型就是將每個節點寫成一個struct，以pointer儲存連接的資訊 動態開點可以處理你直接開完會MLE的情況，因為每次會碰到的節點就是最多$\log{C}$個，只要修改時有碰到的再開，詢問時沒有就return，就能以時空複雜度$O(N\log{C})$做掉 (或是可以離散化啦，但如果要對值做事的話不方便) ---- ```cpp= struct node{ int l,r,val=0,tag=0; node *ls=nullptr,*rs=nullptr; node(int l,int r,int val):l(l),r(r),val(val) {} void update(int k){ val+=k; tag+=k; } void push(){ ls->upd(tag); rs->upd(tag); tag=0; } void pull(){ val=(ls?ls->val:0)+(rs?rs->val:0); } void modify(int ql,int qr,int k){ if(ql>=r||qr<=l) return; if(ql<=l&&qr>=r){ update(k); return; } int mid=(l+r)/2; if(!ls) ls=new node(l,mid,0); if(!rs) rs=new node(mid,r,0); push(); ls->modify(ql,qr,k); rs->modify(ql,qr,k); pull(); } int query(int ql,int qr){ if(ql>=r||qr<=l) return 0; if(ql<=l&&qr>=r) return val; int mid=(l+r)/2; if(!ls) ls=new node(l,mid,0); if(!rs) rs=new node(mid,r,0); push(); return (ls->query(ql,qr))+(rs->query(ql,qr)); } }; int main(){ node *rt=new node(1,n+1,0); //do something } ``` --- ## 線段樹上的奇技淫巧 ---- ### 掃描線 ---- [TIOJ 1224](https://tioj.ck.tp.edu.tw/problems/1224) 給你$N$個矩形的上下左右邊界$L,R,D,U$，試求全部矩形覆蓋的面積。 $N \leq 10^5,0<=L,R,D,U<=10^6$ ---- 對其中一維開線段樹，另外一維從小到大做事！ 遇到邊界將該區間+1或-1，記錄非0的個數！ ---- [TIOJ 2174](https://tioj.ck.tp.edu.tw/problems/2174) [TIOJ 1905](https://tioj.ck.tp.edu.tw/problems/1905) ---- ### 前後綴相關的東西 ---- [TIOJ 1169](https://tioj.ck.tp.edu.tw/problems/1169) 長度為$n$的陣列$a$，$Q$筆詢問 1. 將$a_i$設為$x$ 2. 詢問$[l,r)$區間最長不包含$y$的長度是多少 $n \leq 10^5,0 \leq a_i,x,y < 2^{24}$ ---- 考慮對每個$x$開一個線段樹(動態開)。 要怎麼樣才能好好維護連續的長度？ 記錄前後綴最長可以多少！ 好好合併兩個節點的資訊！ ---- [CF 1567E](https://codeforces.com/problemset/problem/1567/E) ---- 到這邊你會發現線段樹好像沒那麼死(? 如：李超線段樹、時間線段樹...... --- ## 持久化線段樹 (Persistent Segment Tree) ---- 一開始只有一個陣列$a$，維護以下操作： 1. 各種花式修改 2. 詢問第$k$次修改後的$[l,r]$之資訊 有辦法好好做嗎？ ---- 持久化線段樹來了。  發現每次修改會動到的只有$O(\log N)$個節點，其餘都維持不變。 每一次只新開有動到的$O(\log N)$個節點，其他的就連回去！ ---- ### 實作 你可能會想要寫指標型線段樹。 [Range Queries and Copies](https://cses.fi/problemset/task/1737) 這題的AC code，如果寫出bug可以參考看看！ ```cpp= #include<bits/stdc++.h> #define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define int long long #define pii pair<int,int> #define f first #define s second #define mp make_pair #define pb emplace_back #define all(x) x.begin(),x.end() using namespace std; struct node{ node *left,*right; int val,l,r; node(int li,int ri){ val=0;left=nullptr;right=nullptr;l=li;r=ri; } }; void modify(node *n,int ind,int val){ if(n->r-n->l<=1){ n->val=val; return; } int mid=(n->l+n->r)/2; if(ind<mid){ node *t=new node(n->l,mid); if(n->left){ if(n->left->left) t->left=n->left->left; if(n->left->right) t->right=n->left->right; } n->left=t; modify(n->left,ind,val); }else{ node *t=new node(mid,n->r); if(n->right){ if(n->right->left) t->left=n->right->left; if(n->right->right) t->right=n->right->right; } n->right=t; modify(n->right,ind,val); } n->val=(n->left==nullptr?0:n->left->val)+(n->right==nullptr?0:n->right->val); return; } int query(node *n,int ql,int qr){ if(ql>=n->r||qr<=n->l) return 0; if(ql<=n->l&&qr>=n->r) return n->val; return query(n->left,ql,qr)+query(n->right,ql,qr); } main(){ IO vector<node*> v; int n,q,x,a,b,k; cin >> n >> q; node *root=new node(1,n+1); v.pb(root); for(int i=1;i<=n;i++){ cin >> x; modify(root,i,x); } while(q--){ cin >> k; if(k==1){ cin >> k >> a >> x; modify(v[k-1],a,x); }else if(k==2){ cin >> k >> a >> b; cout << query(v[k-1],a,b+1) << '\n'; }else{ cin >> x; node *t=new node(1,n+1); if(v[x-1]->left) t->left=v[x-1]->left; if(v[x-1]->right) t->right=v[x-1]->right; t->val=v[x-1]->val; v.pb(t); } } return 0; } ``` ---- [Distinct Values Queries](https://cses.fi/problemset/task/1734) 試著在線解決！ --- # BIT (Binary Indexed Tree/Fenwick Tree) ---- 線段樹的缺點： 1. code、遞迴參數又臭又長 2. 遞迴常數大 3. 空間要開到$4n$之多 (不過我還是很喜歡線段樹啦，通用性高) ---- BIT  ---- 可以幹嘛： $O(\log{N})$維護前綴！ (一樣要有結合律) 僅用$O(N)$記憶體！ ---- 實作 ```cpp= const int N=2e5+5; int bit[N];//1-base void update(int i,int val){ for(;i<N;i+=i&-i) bit[i]+=val; } int query(int i){ int ret=0; for(;i>0;i-=i&-i) ret+=bit[i]; return ret; } ``` 就是這麼簡單！ ---- 補充說明： i&-i是啥？ 其實是lowbit(i)：表示成二進位後，最右邊為1的 (大談：二補數) 那為什麼是i+=i&-i？ 看圖！ ---- 用途： 1. 單點修改，區間查詢 2. 區間修改，單點查詢 3. 區間修改，區間查詢(？) (內心萌生為什麼不寫線段樹？) ---- [TIOJ 1080](https://tioj.ck.tp.edu.tw/problems/1080) 用BIT寫寫看 ---- 補充：可$O(N)$建立 留作讀者自行思考練習。 --- # Sparse Table (稀疏表) ----  ---- 可以做到： $O(N\log{N})$建立，$O(1)$查詢 建立： $sp[i][0]=a[i],sp[i][j]=min(sp[i][j-1],sp[i+po[j-1]][j-1])$ 查詢： 將其拆成兩段，每段長度為最接近的2的冪次(才能做到真正$O(1)$) $x=r-l+1$ $min(sp[l][len[x]],sp[r-po[len[x]]+1][len[x]]$ ---- 實作 ```cpp= const int N=2e5+5,lgN=20; int sp[N][lgN],po[20],len[N]; void build_sparse_table(){ po[0]=1; for(int i=1;i<lgN;i++) po[i]=po[i-1]*2; for(int j=1;j<lgN;j++){ for(int i=1;i<=n;i++){ sp[i][j]=min(sp[i][j-1],sp[i+po[j-1]][j-1]); } } //預處理每個長度要怎麼拆 len[1]=0; int cur=1; for(int i=2;i<=N;i++){ if(i>=po[cur+1]) len[i]=++cur; } } void query(int l,int r){//[l,r] int x=r-l+1; return min(sp[l][len[x]],sp[r-po[len[x]]+1][len[x]]); } //我沒有compile過我不知道是不是好的反正大概是這樣 ``` --- # Heap (堆) ---- 樹狀結構！ 堆性質：所有父節點都比子節點大(小) (不一定是二元樹) ----  ---- 實作push跟pop： push：將目前數字插在一個葉節點，並一路上浮！ pop：從根結點開始，與左右兩個子節點較大(小)的交換(維持堆性質)，直到變成葉節點後移除 複雜度：深度$O(\log N)$，push跟pop都是妥妥的$O(\log N)$ ---- ## 實作 有STL誰要自己寫？ ```cpp= priority_queue<int,vector<int>,greater<int> > mnpq;//min heap priority_queue<int,vector<int>,less<int> > mxpq;//max heap ``` ---- 以上這種是基本的Heap，實際上有很多種，如： * 左傾樹(Leftist Tree) * 配對堆(Pairing Heap) * 費波納契堆(Fibonacci Heap) ... 每一種push、pop的複雜度都不盡相同， 有些則可以在$O(\log N)$之內合併兩個堆， 但多半時候我們不會想手刻。 (詳見pbds) ---- [TIOJ 1429](https://tioj.ck.tp.edu.tw/problems/1429) --- # 二元搜尋樹 (BST, Binary Search Tree) ----  ---- 考慮dfs， 前序遍歷：走到的時候就輸出 中序遍歷：走完左子樹後輸出，再走右子樹 後序遍歷：走完左右子樹後輸出 樹性質：BST的中序遍歷就是排序好的原陣列！ ---- ## 實作 插入：比當前節點數字小就往左下走，大就往右下走，走到空節點就新增 查詢：二分搜 複雜度呢？ ---- 最糟情況可能會是一條鍊！複雜度是爛的！ (不過對於隨機的測資可能是$O(\log N)$？) 你想寫的話，可以去這裡：[NEOJ 47](https://neoj.sprout.tw/problem/47/) ---- 變成鍊怎麼辦？ 我們需要自動平衡， 讓期望複雜度$O(\log N)$或更好！ 競程常用的自平衡二元搜尋樹： Splay Tree Treap 其他常用的： AVL Tree Red Black Tree ... --- # Treap (無旋式樹堆) ---- Treap是一種平衡的二元搜尋樹。 在每個節點上維護pri、val， pri為隨機數字，val為值。 pri保堆性質，val保樹性質。 ---- 無旋式Treap又稱分裂合併Treap，主要兩種操作： 1. 分裂(Split)： 將一棵treap以某個值為分界分成左右兩棵， 一邊的數字都比另一邊小， 兩邊都仍然是一個treap 2. 合併(Merge)： 將一棵值比較小、一棵值比較大的treap合併成一棵treap 所有操作都可以用上面兩種操作完成！ ---- push: 假設要推入x，以x把原本的treap分開， 把x當成只有一個節點的treap， 再把三棵兩個兩個合起來。 erase: 切成三棵treap，左、x(一個節點)、右， 把左邊跟右邊合起來。 輕鬆做完！ ---- Split:  遞迴處理！ ---- Merge: (ls=left son, rs=right son)  ---- 照pri值大的在上 遞迴處理！  ---- 複雜度： 由於pri值隨機的特性，高度是穩穩地$O(\log N)$ 所有操作就也都是$O(\log N)$ ---- ## 實作 ```cpp= int ran(){ static int x=20211102; return ++(x*=0xdefaced); } //偽隨機函數 struct node{ int pri,val; node *ls=nullptr,*rs=nullptr; node(int pri,int val):pri(ran()),val(val) {} }; node* merge(node *a,node *b){ if(!a) return b; if(!b) return a; if(a->pri>b->pri){ a->rs=merge(a->rs,b); return a; }else{ b->ls=merge(a,b->ls); return b; } } void split(node *cur,int k,node *&a,node *&b){ if(!cur){ a=b=nullptr; return; } if(cur->val>=k){ b=cur; split(cur->ls,k,a,b->ls); }else{ a=cur; split(cur->rs,k,a->rs,b); } } ``` 你可以再回去寫剛剛BST那題[NEOJ 47](https://neoj.sprout.tw/problem/47/)驗一下。 ---- 進階用法： 1. Treap上可以打懶標 只要每次操作好好push跟pull就行 2. 放棄val域，改維護子樹大小 切出來後，左邊大小為$k$，右邊為$n-k$ 綜合以上，Treap可以取代部分線段樹的功能 大家自行摸索實作>< ---- [TIOJ 1633](https://tioj.ck.tp.edu.tw/problems/1633) --- # __gnu_pbds ~~(平板電視)~~ ---- 剛剛講到的自平衡二元樹、可併堆， 其實在俗稱黑魔法的__gnu_pbds裡面都有了。 但不見得那麼好用，也不見得夠快。 參考就好，比賽可以用。 ---- ```cpp= #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> //使用tree_order_statistics_node_update #include<ext/pb_ds/priority_queue.hpp> //可用#include<bits/extc++.h>，但dev會CE== using namespace std; using namespace __gnu_pbds; using rbtree = __gnu_pbds::tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>; //內部實作為紅黑樹，與map、set同，rb_tree_tag可更換為其他 //可手寫修改函式(tree_order_statistics_node_update)，使其有你想要的功能 rbtree T; T.push(x); T.erase(x); T.find_by_order(k); T.order_of_key(k); //可取代值域線段樹(慢) using pq = __gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag>; //內部實作為配對堆，可O(1)pop跟join pq Q1,Q2; Q1.join(Q2);//將Q2併入Q1; //其餘用法大致與STL同 ``` --- # Useful Resources * [CSES](https://cses.fi/problemset/) 裸題很多，適合拿來測演算法正確性 * [TIOJ](https://tioj.ck.tp.edu.tw/) 有人會不知道TIOJ嗎？ * [OI Wiki](https://oi-wiki.org/) 就一堆東西整理的網站