接上文。。。)
函數式(現在又稱主席式。。。)數據結構從來都沒寫過,感覺這個東西可以挖掘出不少東西出來,於是開一組專題。
先根據 Seter 留下的文本做一些記錄。。
主席樹大概是一種離線結構,我以前反正沒看到過這東西,所以就自己給他起名字了!如果誰知道這東西的真名,請告訴我!
現在我們知道,主席樹的全名應該是 函數式版本的線段樹。加上附帶的一堆 technology。。
。。總之由於原名字太長了,而且 “主席” 兩個字念起來冷艷高貴,以後全部稱之為主席樹好了。。。
主席樹的主體是線段樹,準確的說,是很多棵線段樹,存的是一段數字區間出現次數(所以要先離散化可能出現的數字)。舉個例子,假設我每次都要求整個序列內的第 k 小,那麼對整個序列構造一個線段樹,然後在線段樹上不斷找第 k 小在當前數字區間的左半部分還是右半部分。這個操作和平衡樹的 Rank 操作一樣,只是這裡將離散的數字搞成了連續的數字。
先假設沒有修改操作:
對於每個前綴 S1…i,保存這樣一個線段樹 Ti,組成主席樹。這樣不是會 MLE 么?最後再講。
注意,這個線段樹對一條線段,保存的是這個數字區間的出現次數,所以是可以互相加減的!還有,由於每棵線段樹都要保存同樣的數字,所以它們的大小、形態也都是一樣的!這實在是兩個非常好的性質,是平衡樹所不具備的。
對於詢問 (i,j),我只要拿出 Tj 和 Ti-1,對每個節點相減就可以了。說的通俗一點,詢問 i..j 區間中,一個數字區間的出現次數時,就是這些數字在 Tj 中出現的次數減去在 Ti-1 中出現的次數。
那麼有修改操作怎麼辦呢?
如果將詢問看成求一段序列的數字和,那麼上面那個相當於求出了前綴和。加入修改操作後,就要用樹狀數組等來維護前綴和了。於是那個 「很好的性質」 又一次發揮了作用,由於主席樹可以互相加減,所以可以用樹狀數組來套上它。做法和維護前綴和長得基本一樣,不說了。
這段指出了主席樹的主要性質。。
- 線段樹的每個結點,保存的是這個區間含有的數字的個數。
- 主席樹的每個結點,也就是每顆線段樹的大小和形態也是一樣的,也就是主席樹之間可以相互進行加減運算。。
同時我們也枚舉一下主席樹的一些局限:
- 主席樹是一種離線結構。。(必須預先知道所有數字的範圍。。這在一些應用中會成為障礙。。。
- 存在 MLE 問題。。(如果按照定義裡面的方法去寫,對每個結點都需要開一整可線段樹,至少都是 O(n2) 級別的空間。。
——————————————————
開始填坑。由於每棵線段樹的大小形態都是一樣的,而且初始值全都是 0,那每個線段樹都初始化不是太浪費了?所以一開始只要建一棵空樹即可。然後是在某棵樹上修改一個數字,由於和其他樹相關聯,所以不能在原來的樹上改,必須弄個新的出來。難道要弄一棵新樹?不是的,由於一個數字的更改隻影響了一條從這個葉子節點到根的路徑,所以只要只有這條路徑是新的,另外都沒有改變。比如對於某個節點,要往右邊走,那麼左邊那些就不用新建,只要用個指針鏈到原樹的此節點左邊就可以了,這個步驟的前提也是線段樹的形態一樣。
假設s是數字個數,這個步驟的空間複雜度顯然是 O(logs)。用樹狀數組去套它,共有 2logn 棵樹被修改,m 個操作再加上一開始的空樹和 n 個數字,總共就是 O((n+m)lognlogs)。Fotile 大神說如果加上垃圾回收的話,可以去掉一個 log…… ym
至此主席樹結構已經分析清楚了。。
const int N = 50009, M = 10009, NN = 2500009; int l[NN], r[NN], c[NN], total; PII A[N+M]; int B[N+M], Q[M][3]; int S[N], C[N], Null; int n, m, An, Tn; .. .
這裡仍然用池子法保存線段樹的結點,NN 是一個估計值。。(大概是 nlogn 。。。
l[], r[], c[], total 分別是左孩子下標,右孩子下標,該區間的數字個數和當前已分配的結點數。
(線段樹的區間可以在遞歸的時候實時計算,可以不予保存。。。
PII A[]; int B[]; A、B 用於離散化。。。 B 記錄相應數字的 Rank 值。
int Q[]; 記錄詢問。。。
int S[], C[], Null; 是主席樹下標。。
分別對應前綴和,樹狀數組 和 初始時的空樹。
An 是 A 數組的長度,由初始 n 個數字和修改後的數字決定,
Tn 是所有出現的不同數字的個數,用於建立線段樹,由對 A 數組去重後得到。
#define lx l[x] #define rx r[x] #define ly l[y] #define ry r[y] #define cx c[x] #define cy c[y] #define mid ((ll+rr)>>1) #define lc lx, ll, mid #define rc rx, mid+1, rr void Build(int &x, int ll, int rr){ x = ++total; if (ll < rr) Build(lc), Build(rc); } int Insert(int y, int p, int d){ int x = ++total, root = x; c[x] = c[y] + d; int ll = 0, rr = Tn; while (ll < rr){ if (p <= mid){ lx = ++total, rx = ry; x = lx, y = ly, rr = mid; } else { lx = ly, rx = ++total; x = rx, y = ry, ll = mid + 1; } c[x] = c[y] + d; } return root; }
這裡是主席樹主要支持的操作。。前面一堆 Macro 方便敲代碼。。。
注意由於 l[], r[], 還有 m 全部有衝突乾脆用 ll, rr, mid 代替區間下標。。。
這裡 Insert() 過程就是前面所說的插入單鏈的操作。。。以 y 為基礎,形成一棵新的主席樹 x。
。。。沒有修改的鏈仍然指向 y 的相對應部分。複雜度為樹高。。。。
。。。下面是 int main(); 函數代碼了。。。完整程序移步這裡。。。。
int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif #define key first #define id second RD(n, m); REP(i, n) A[i] = MP(RD(), i); An = n; char cmd; REP(i, m){ RC(cmd); if(cmd == 'Q') RD(Q[i][0], Q[i][1], Q[i][2]); else RD(Q[i][0]), Q[i][2] = 0, A[An++] = MP(RD(), An); } sort(A, A + An), B[A[0].id] = Tn = 0; FOR(i, 1, An){ if(A[i].key != A[i-1].key) A[++Tn].key = A[i].key; B[A[i].id] = Tn; } Build(Null, 0, Tn); REP_1(i, n) C[i] = Null; S[0] = Null; REP(i, n){ S[i+1] = Insert(S[i], B[i], 1); } An = n; REP(i, m) if (Q[i][2]){ OT(A[Query(Q[i][0], Q[i][1], Q[i][2])].key); }else{ Modify(Q[i][0], B[Q[i][0]-1], -1); Modify(Q[i][0], B[Q[i][0]-1] = B[An++], 1); } }
待討論問題:
- …
由於每棵線段樹的大小形態都是一樣的,而且初始值全都是 0,那每個線段樹都初始化不是太浪費了?所以一開始只要建一棵空樹即可。
事實上由於當一個結點的 c[] 結果為 0 時。。無論它向左還是向右遞歸下去結果都會是0 。。。
所以初始時甚至不是建立空樹。。而是只需要一個空結點即可。。。(如何實現這層。。。 - 仍然沒有將 Lazy Evalutaion 的理念做到完美。。。這題中的 Lazy Evaluation 體現在兩個方面。。
主席樹的單鏈修改和主席樹與主席樹之間的運算。。主席樹與主席樹之間的運算如果全部做的話一次是 O(n)。。。但是因為詢問時只需要計算一條到葉子的路徑。。。
。。。上面的代碼中,這種運算是通過 Struct Pack; 結構體現的。。。一種多顆主席樹結點的打包。。
。。全部在同一層的同一個位置。。向同一個方向遞歸下降。。一個 Pack; 的值為該結構內所有結點值的和。。。。現在實現的不足之處:
- 無法很好的處理減運算。。因此這裡才還要保存了 S[] 前綴和,讓 C[] 逐個逐個修改。。。
。。。然後每次回答詢問的時候還要一併帶上 S[] 。。Orz。(雖然說有助於預處理。。 - 對計算過後結果無法有效利用。。(換句話說沒有體現出主席式 Memorization 的一面。。。
- 對單個鏈的插入操作也不是要即時處理的。。(。。如何用數據結構把所有操作先 Hold 下來 。。?。。這樣的好處是有一些操作對結果沒有影響是可以忽略。。另外把一堆操作放在一起當做一個操作處理的話有時也能得到 Bonus 。。。
- 無法很好的處理減運算。。因此這裡才還要保存了 S[] 前綴和,讓 C[] 逐個逐個修改。。。
-
…
Fotile 大神說如果加上垃圾回收的話,可以去掉一個 log…… ym
(另外正一個誤。。。加上回收並不能去掉一個 log 。。。。