主席樹與POJ2104

orz fotile主席

2.7 引入

直接甩題：2104 -- K-th Number

這是一道模板題，一看就知道這是劃分樹（其實樹套樹打上癮的我本來是想用線段樹+Treap做的）。不過上次打完線段樹後在@g1n0st的安利之下我去了解了一下主席樹這個東西，於是乎，這道題又變成了主席樹的模板題。

劃分樹在這裡就不多介紹了，大概是把樹劃成左右兩邊，左邊的任意元素都比右邊小。接下來介紹主席樹。

主席樹是一種可持久化數據結構。它的每個節點對應一棵線段樹。它利用函數式編程的思想使得可以訪問歷史版本，並且減少時間和空間消耗。

方便起見，我們定義如下變數：

• L，左孩子結點
• R，右孩子結點
• sum，節點總數
• sz，數據域的大小

對於一個長度為n的序列，主席樹以每個點的前綴[1...i]的區間建立一棵線段樹，統計[L, R]在[1...i]中的節點數。對於區間[l, r]，節點o.sum[r] - o.sum[l-1]就是[l, r]內所有的節點數。

2.71 操作

1. 建樹。啊！我們先建立一棵空樹。然後根據離散值將數據依次插入位置。
2. 更新。根據自己的離散值尋找位置，sz+1，由於更新一個葉節點只會影響根節點到該葉節點的一條路徑，故只需修改該路徑上的信息域sz。每個主席樹的節點即每棵線段樹的結構完全相同，只是對應信息域sz不同。此時可以利用歷史版本，即利用相鄰的上一棵線段樹的信息。相鄰兩顆線段樹只有當前待處理的元素不同，其餘位置完全一樣（前綴）。因此，如果待處理的元素進入線段樹的左子樹的話，右子樹是完全一樣的，可以共用，即直接讓當前線段樹節點的右子樹指針指向相鄰的上一棵線段樹的右子樹；若進入右子樹，同上。
3. 查詢。如果兩個線段樹的左子樹節點數之差大於k，那麼就直接到左子樹里查找，否則，就把k減去sz之差，到右子樹里查找。
4. 時間複雜度分析：建樹的時間複雜度是O(nlogn)，更新和查詢的時間複雜度都是O(logn)，總時間複雜度是O(nolgn)

2.718 代碼

#include <iostream>n#include <cstdio>n#include <cstring>n#include <algorithm>n#define maxn 100100nusing namespace std;nninline char getc(void)n{ntstatic char buf[1000000], *p1 = buf, *p2 = buf;ntif(p1 == p2){nttp2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);nttif(p1 == p2) return EOF;nt}ntreturn *p1++;n}nninline void read(int& x)n{ntx = 0; int f = 1; char ch = getc();ntfor(; !(ch >= 0 && ch <= 9); ch = getc()) if(ch == -) f = -1;ntfor(; (ch >= 0 && ch <= 9); x = x * 10 + ch - 0, ch = getc());ntx *= f;n}nninline void write(int x)n{ntif(x < 0) putchar(-), x = -x;ntif(x > 9) write(x/10);ntputchar(x%10+0);n}nnstruct chairtree{ntint L, R, sum;ntchairtree(void) { L = R = sum = 0; }n}T[maxn*20];nnint sz;nnstruct ID{ntint x, idx;ntbool operator < (const ID& rhs) const { return x < rhs.x; }n}id[maxn];nninline void insert(int& o, int L, int R, int rank)n{ntT[++sz] = T[o]; o = sz; T[o].sum++;ntif(L == R) return;ntint M = L + (R - L) / 2;ntif(rank <= M) insert(T[o].L, L, M, rank);ntelse insert(T[o].R, M+1, R, rank);n}nninline int query(int L, int R, int l, int r, int k)n{ntif(L == R) return L;ntint tmp = T[T[r].L].sum - T[T[l].L].sum;ntint M = L + (R - L) / 2;ntif(k <= tmp) return query(L, M, T[l].L, T[r].L, k);ntelse return query(M+1, R, T[l].R, T[r].R, k - tmp);n}nnint root[maxn], rank[maxn];nint n, m;nnint main()n{nt//freopen("test.in", "r", stdin);nt//freopen("test.out", "w", stdout);ntroot[0] = 0; sz = 1;ntread(n); read(m);ntfor(int i = 1; i <= n; i++){nttread(id[i].x);nttid[i].idx = i;nt}ntsort(id+1, id+n+1);ntfor(int i= 1; i <= n; i++) rank[id[i].idx] = i;ntfor(int i = 1; i <= n; i++){nttroot[i] = root[i-1];nttinsert(root[i], 1, n, rank[i]);nt}ntwhile(m--){nttint l, r, k;nttread(l); read(r); read(k);nttwrite(id[query(1, n, root[l-1], root[r], k)].x);nttputchar(n);nt}nt//fclose(stdin); fclose(stdout);ntreturn 0;n}n

推薦閱讀：