高階數據結構

• 并查集
• • “邊代權的并查集”
  • 帶“擴展域”的并查集
• 樹狀數組
• • 查詢前綴和
  • 單點增加
  • 樹狀數組求逆序對
  • 樹狀數組的擴展應用
  • • 區間修改和區間查詢
  • 維護一個01序列
• 線段樹
• • 區間最大連續子段和
  • 維護長度為n的01串
  • 掃描線
• 分塊

并查集

并查集是一種可以動態維護若干個不重疊的集合。具體來說善長動態維護許多具有傳遞性的關系。同時也可以在一張無向圖中維護節點之間的連通性。

既然是高階我們重點來講帶有‘’擴展域“和“邊帶權”的并查集。

“邊代權的并查集”

在這類題中我們通常要維護的是集合中點的一些權值問題。如一個節點到父節點距離是x，另一個節點到父節點距離為y。那么它們兩個的距離就是abs(x - y)。因此在該類問題上我們用一個數組d，用d【x】保存節點x到父節點fa【x】之間的邊權。

如何在路徑壓縮的時候更新d數組呢？
我們回想路徑壓縮的過程。對于d數組，我們只需要在回溯的時候加上其父節點的d即可，即

int find(int x){if(x == fa[x])return x;int root = find(fa[x);d[x] += d[fa[x]];return fa[x] = root; }

以下圖為例，我們尋找5的父節點的時候，root 的值先為 3 ，當前層的x為4 。 d[x] += d[fa[x]] ; 由于d[fa[x]] 為0 ， 所以d[x] 還是4 。然后到x為5的層數，root 由于 上一層返回值是 fa[x] = root;所以還是3 ， 不過由于fa[3] 沒有更新還是4 ，所以d[x] += d[fa[x]]; 后d[x] = 4 + 2 = 6 ，最后 d[5] = 3 。很好我們完成了路徑的壓縮和更新問題。


那合并什么說法呢？
為了方便能得到最全面的情況，以下面為例，假設現在多了 7 5 20
那么我們如何合并呢？我們看圖很容易知道缺 1 和 3 之間的邊 ， 同時邊權也容易知道是 5 。 那么如何能得到一個通用的公式呢。我們先回想一下一般的合并，我們先得到 7 和 5 的父節點分別為 1 和 3 ，我們讓 1 為 3 的兒子節點。那么現在我們缺的是 1 到 3 的邊的權值 ，即 d[1]。 對于在一個節點中的兩個節點的距離為 abs(d[x] - d[y])，所以，現在20 = d[7] - d[5] ,對于現在以3為根節點后，而 d[7] = 之前的d[7] + d[1] . 所以我們得到
$d[1]=20+d[5]?d[7]$ . 加粗的地方請留意，不是 d[x] + d[y] 。

void merge(int x, int y, int z ) {int fx = get(x), fy = get(y);if (fx != fy) {fa[fx] = fy, d[fx] = z + d[y] - d[x];} }

帶“擴展域”的并查集

帶權值的并查集和帶“擴展域”的并查集都是為了解決傳遞關系不止一個的問題。帶“擴展域”的并查集是擴展了多個域來應對多種關系。也就是說將原本的一個點拆分成幾個點來進行處理。具體的話建立看一下 食物鏈 這個經典題目。

要正確理解好，就需要將題面上的表示關系的動作轉化為關系。

就以食物鏈為例，將 一個節點分為三的目的是，能處理好多對關系。
這些是以關系建立起來的域，是關系
X: 本身域
X+n :捕食域
X + 2n : 天敵域

這是什么意思呢？本身域就是與自己同類的一個集合， x + n ：域里構成的集合是由x的捕食的節點組成的。 x + 2n :域里構成的集合是由x的天敵的節點組成的。

對于每一種關系我們都需要在三個域中建立起相應的關系。
如 x 吃 y ,那么就應該有 x 是 y 的天敵 ， y 是 x 的 捕食對象。同時由三邊有 ， y 的 捕食對象是 x 的天敵。

即, merge(x , y+ 2n) 的含義是 x 和 y + 2n 是同一個集合。
Merge(x + n , y ) ,
Merge(x + 2n , y + n)

下面這個題和食物鏈類似
題目轉送們

由于是剪刀石頭布這個比較常見的東西我們就可以更好的來理解擴展并查集了。 我們對于其中一個節點x ， 與它同為一個域（集合）的是x本身 ， 比它小的我們 用x + n , 那么x + 2n 就表示大于x的關系的集合。我們通過舉一個例子來說明把。 x > y . 那么 表示什么呢？ x 本社應該與 y的 大于關系的域(y+2n)在同一個集合 ，（對于擴展域我們有一個小技巧，我們對于每一個域中都要考慮），因此先我們考慮一下 x + n 這個域，這個里邊是比x小的集合，那么在這里y比x小，因此應該是y本身這個域與x + n 同在一個集合。我們再來考慮一下 x + 2n ，我們由剪刀石頭布很容易知道 , 比 x 大的 應該是哪些與y有小于關系的點。 在這個問題，還有一個點就是裁判的數量。我們就枚舉一下裁判是誰 ， 當且僅當我們在不講i這個人的關系加入其中的時候任然沒有矛盾就說明，這個i是一個裁判。

樹狀數組

樹狀數組的基本用途是維護一個序列的前綴和。首先我們需要理解這個數組的含義是什么。假設數組為c[x] ， 這個里邊維護的值是區間$[x?lowbit(x)+1,x]$中數的和。有以下三個性質：

每一個內部節點c[x]保存以它為根的所有子樹的和。

每一個內部節點c[x]的子節點個數等于lowbit(x)的位數。

除樹根外，每一個內部節點c[x]的父節點為c[x+lowbit(x)]

樹的深度為 O（logn）

查詢前綴和

對于每一個數x ， 可以將區間[1,x] 利用二進制拆分為log(x)個小區間。具體來說，好比12 = 1100 , 那么可以分為兩個區間，[1 , 8 ] , [9 , 12]. 回想c[x] 的定義 ， 那么c[12] 存儲的是區間[9 , 12] 的和，那么還缺[1,8]的什么辦，而這正好是12 - lowbit(12) = 8 , 的c[8]對應的區間。因此我們由如下操作:

int ask(int x){int sum = 0 ;for( ; x ; x-=lowbit(x)) sum += c[x];return sum; }

因為樹的深度為log(n)因此我們就可以在O（logn）的時間內求出前綴和了。
當然我們要求[ l ,r ] 區間內數的和的時候 ， 只需要aks(r) - ask(l - 1 )即可。

單點增加

就是說我們要對原序列a[i] + y , 同時又要正確的維護前綴和和。有與包含a[i]的區間只有c[i]以及其父節點。由性質3我們就可以得到以下代碼：

void add(int x , int val){for( ; x <=n ; x += lowbit(x)) c[x] +=val;

初始化樹狀數組

樹狀數組求逆序對

利用樹狀數組求序列的逆序對個數是利用在集合a上的數值進行樹狀數組的技巧。為什么這么說呢？我們對于位置i ， 查找后邊比它小的個數。我們不一定需要詢問具體的a[i]的值，我們只需要查詢，后邊是否有值為[0,a[i] - 1 ] 這個區間內。
因此我們就可以后序遍歷整個數組，每一次進行一次詢問，之后將a[i]值得個數加1.在這里樹狀數組記錄c[x] 記錄的是$[x?lowbit(x)+1,x]$中數出現過的總次數。

代碼：

int res = 0; for(int i = n ; i ; --i){res += ask(a[i] - 1 );add(a[i], 1); }

樹狀數組的擴展應用

區間修改和區間查詢

對于區間修改：因為維護的是前綴和，那么我們就可以利用前綴和的技巧，對于修改一個區間[l,r] ,我們只需要在l處加上d ， 在r+1處減去d即可。將區間修改轉變為兩個單點修改。具體來說我們維護的不再是具體的值而是維護指令（修改）的累積影響.具體來說，我們維護的這個數組初始為0，b數組對于位置x的前綴和就是經過這些指令后a[x]添加的值。
對于詢問第x個數的值我們只需要 a[x] + ask(x) ;

上面說的是區間修改后單點詢問，那么如何區間修改和區間詢問呢，對于區間詢問也就是a[1~x]的前綴和如何求，如果直接用上面的，我們也是可以求的，這不過時間復雜度為上升。我們想想如何優化，對于區間 a[1~x] 整體增加的值為 1 ~ x 沒一個b的前綴和.

維護一個01序列

這是一個很經典的一類題目，很具有思維性，因此就拿出來講一下。
題目轉送們

解題思路：

首先我們容易知道，對于同一個編號，在最后出現的，肯定是放在編號對應的位置的。難點在于哪些和它同編號的但是在被插隊之后往后移動的情況。對于這些編號，我們知道一個是它受限于前邊的編號，即它不可能出現在自己初始編號的前邊，第二個就是后邊與其同一編號的人。它會因為這些人而被一直往后移動。由于該題編號是0開始我們可以在讀入的時候就都加上1.之后考慮維護一個01序列，起始全是1。然后后序遍歷，對于每一個編號，二分來查看01前綴和恰好為其編號的位置是多少，然后將這個位置add(pos , -1)；

線段樹

以下是線段樹講得比較好的一篇博客了就不繼續講了。
線段樹
下面我們主要講的是線段樹維護區間最大連續子段和 ，以及維護區間的眾數和掃描線。

區間最大連續子段和

先以下篇博客，
區間最大子段和
下面就來具體的對博客進行補充一下。首先是ls和rs，由于兩者類似因此就講講ls。想想我們在求一個以左端點為起始點的最大連續字段和會什么求呢？由于線段樹是將該區間分為了左右兩部分，那么我們想到的一個就是左半邊的ls和左半邊的sum加右半邊的ls（是為了保證區間的連續性）。
而m s msms有三種情況：

該區間內的ms是左兒子的ms
該區間內的ms是右兒子的ms
該區間內的ms是左兒子的rs+右兒子的ls.（也是為了保證區間的連續性）

具體來說我們一個線段樹的節點維護了四個信息：區間和，緊靠左端的最大連續子段和lmax , 緊靠右端的最大連續子段和rmax , 以及區間最大字段和。

t[u].sum = t[u<<1].sum + t[u<<1|1].sum; t[u].lmax = max(t[u<<1].lmax , t[u<<1].sum + t[u<<1|1].lmax]; t[u]rmax = max(t[u<<1|1].rmax , t[u<<1|1].sum + t[u<<1].rmax]; t[u].dat = max(max(t[u<<1].dat , t[u<<1|1].dat) , t[u<<1].rmax + t[u<<1|1].lmax);

維護長度為n的01串

題目轉送們

與上一題類似的思想因此決定要進行總結一下。
題目大意：

然我們動態的維護一些區間，之后詢問是否有連續為0（即沒有人住）的長度為n，有的話取出開頭最小的編號。

解題思路：

• 對于線段樹的題目我們首先需要想的是我們的線段樹維護的是區間的什么？且維護的這個東西要滿足區間可加性。首先對于每一個區間我們感興趣的是這個區間中0字符的長度，因此我們就維護這個東西。那么如何維護呢？
  首先，我們類似上題的思想，我們用len 表示這個區間最長的0子串長度，用ld表示靠近左端點最長的0子串長度，用rd表示靠近右端點最長的0子串長度。這里可能有人會疑惑如果最長的在中間什么辦？這其實沒有關系，中間這個部分在拆分為區間的時候一定會出現在某一個區間的左端點開始或者右端點開始。因此我們采用左，右兩端一個是可以涵蓋中間的情況，另一個是了可以更好的利用線段樹來進行維護。
• 那么這個長度是什么得到的呢？這個最大長度我們一般是在左區間的最大長度，右區間的最大長度和左區間的右端點開始的最大長度和右區間左端點開始的最大長度（滿足連續）三者中取一個最大值。
  講完區間最大長度我們就來講講，以左右端點開始的最大長度。我我們就以左端點為例。 對于左端點，首先我們賦值為其左區間的ld，當左區間的ld = 最區間的節點個數的時候，說明左區間是全為0的，那么我們就將右區間的ld與其合并。
• 同樣在這里涉及到了區間修改，因此我們利用lazy標記來維護。我們將lazy標記分為兩種，因為這個維護的是區間是否被覆蓋的問題（不需要加減值）。例如當為1的時候就表明這個區間為空，那么就讓這個區間的len = ld = rd = r - l + 1 .因為全為0l，如果為2就表示被覆蓋了那么就都賦值為0.
• 還有一個難點是

掃描線

我們需要知道掃描線維護的是什么
假設有以下矩形我們要求出它們的面積和。

現在我們用掃描線劃分后的圖形為下

當我們掃到黃顏色的坐標的是后我們需要知道打問號的線段的長度是多少，很明顯是前一個矩形的邊長加上第一個的邊長然后減去公共部分。我們要維護的就是當前線段的長度。那么我們要如何維護呢一個就是直接利用區間來進行維護，也就是魔改線段樹，另一個就是離散化y坐標后再進行。這里我們講講如何離散后用線段樹維護能得到正確的線段長度。
魔改線段樹版本

首先我們離散化后用來建樹的下標是不同縱坐標的個數。

上面是離散化后的坐標，不過為了正確維護線段的長度，我們每一個節點存儲的長度是 ys[t[p].r + 1] - ys[t[p].l] 也就是區間 [l,r+1]的和。好處是葉子節點存儲的就不是0這個無用的信息了，就以 第一個邊長( 6 , 8) 和 (1,7) , 在修改的時候變為了(6,7),(1,6)（是便于讀取下標從0開始）之后為例，那么它更新后的線段樹如下，

當詢問到我在上邊標記黑色的線段的長得的時候，在詢問的時候就會將我在圖中標出的藍色的區域的長度進行累加到根節點，而這就是黑色線段的長度了。

代碼如下：

#include<stdio.h> #include<vector> #include<algorithm> #include<cstring> #include<vector> using namespace std;const int N = 1E5 + 10; int n , m; double res; struct segment{double x , y1,y2;int k;bool operator < (const segment & t)const{return x < t.x;} }seg[N*2];struct stree{int l , r , cnt ;double len; }tr[N*8];vector<double>ys;void build(int p , int l , int r){tr[p].l = l , tr[p].r = r;if(l == r){tr[p].cnt = tr[p].len = 0;return ;}int mid = (l + r )>> 1;build(p<<1 , l , mid);build(p<<1|1 , mid+1,r);}// 二分查找一個值對應的離散后的值 ， 即線段樹中的下標 int find(double y){return lower_bound(ys.begin() , ys.end() , y) - ys.begin(); }void pushup(int p){//tr[p].r 和 tr[p].l 就是下標所有是直接拿來取值if(tr[p].cnt) tr[p].len = ys[tr[p].r + 1] - ys[tr[p].l];else if(tr[p].l == tr[p].r)tr[p].len = 0;else tr[p].len = tr[p<<1].len + tr[p<<1|1].len ; // 如果沒有被覆蓋過肯定可以直接通過左右兩邊求 }void modify(int u , int l , int r, int k){if(l <= tr[u].l &&tr[u].r <= r){tr[u].cnt += k ;pushup(u);return ;}else{int mid = (tr[u].l + tr[u].r) >>1;if(l <= mid) modify(u*2 , l , r , k);if(r > mid) modify(u<< 1 | 1 , l , r ,k);pushup(u);} }int main(){int T = 1;while(scanf("%d",&n) , n ){ys.clear();for(int i = 0 ; i < n ; ++i){double x1 , x2 , y2 ,y1;scanf("%lf%lf%lf%lf",&x1,&y1 , &x2,&y2);ys.push_back(y1) , ys.push_back(y2); // ys 里邊存的是值，到時候去建線段樹用的是元素個數seg[i*2] = {x1 , y1,y2 , 1} , seg[i<< 1 | 1] = {x2 , y1,y2,-1};}sort(ys.begin() , ys.end());ys.erase(unique(ys.begin() , ys.end()) , ys.end()); // 去重m = ys.size();build(1 , 0 , m - 2); // 那去重后的元素個數來建立線段樹sort(seg , seg + n*2); //res = 0;for(int i = 0 ; i < 2*n ;){ // 遍歷所有的節點int j = i ;while(j < 2*n&& seg[i].x == seg[j].x) j ++;if(i) res += tr[1].len * (seg[i].x- seg[i - 1].x); // 根節點是當前區間的高度？while(i < j){modify(1 , find(seg[i].y1) , find(seg[i].y2) - 1 , seg[i].k);i++;}}printf("Test case #%d\n", T ++ );printf("Total explored area: %.2lf\n\n", res);}return 0; }

分塊

博主先咕咕下，需要去訓練了。訓練完會盡快更新的。

總結

以上是生活随笔為你收集整理的高阶数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。