某島

接上文。。。)

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

Posted by xiaodao
Category: 快晴