主席樹學習筆記 Lv. 1

接上文。。。)

函數式(現在又稱主席式。。。)數據結構從來都沒寫過,感覺這個東西可以挖掘出不少東西出來,於是開一組專題。
先根據 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);
    }
}

待討論問題:


  1. 由於每棵線段樹的大小形態都是一樣的,而且初始值全都是 0,那每個線段樹都初始化不是太浪費了?所以一開始只要建一棵空樹即可。

    事實上由於當一個結點的 c[] 結果為 0 時。。無論它向左還是向右遞歸下去結果都會是0 。。。
    所以初始時甚至不是建立空樹。。而是只需要一個空結點即可。。。(如何實現這層。。。

  2. 仍然沒有將 Lazy Evalutaion 的理念做到完美。。。這題中的 Lazy Evaluation 體現在兩個方面。。
    主席樹的單鏈修改和主席樹與主席樹之間的運算。。

    主席樹與主席樹之間的運算如果全部做的話一次是 O(n)。。。但是因為詢問時只需要計算一條到葉子的路徑。。。
    。。。上面的代碼中,這種運算是通過 Struct Pack; 結構體現的。。。一種多顆主席樹結點的打包。。
    。。全部在同一層的同一個位置。。向同一個方向遞歸下降。。一個 Pack; 的值為該結構內所有結點值的和。。

    。。現在實現的不足之處:

    • 無法很好的處理減運算。。因此這裡才還要保存了 S[] 前綴和,讓 C[] 逐個逐個修改。。。
      。。。然後每次回答詢問的時候還要一併帶上 S[] 。。Orz。(雖然說有助於預處理。。
    • 對計算過後結果無法有效利用。。(換句話說沒有體現出主席式 Memorization 的一面。。。
    • 對單個鏈的插入操作也不是要即時處理的。。(。。如何用數據結構把所有操作先 Hold 下來 。。?。。這樣的好處是有一些操作對結果沒有影響是可以忽略。。另外把一堆操作放在一起當做一個操作處理的話有時也能得到 Bonus 。。。
  3. Fotile 大神說如果加上垃圾回收的話,可以去掉一個 log…… ym

    (另外正一個誤。。。加上回收並不能去掉一個 log 。。。。