可持久化字典樹 詳解

😊 | Powered By HeartFireY | Persistent Trie

📕 | 需要的前導知識：字典樹(Trie)、可持久化資料結構理論(Persistent Data Structure Theory)

一、可持久化字典樹 簡介

首先讓我們來回顧一下字典樹的相關内容：Tire 字典樹 詳解

字典樹是一種利用邊權映射到字元集，将字元串儲存到一棵樹上的資料結構，在查詢公共字首、字元串排序、詞頻統計方面有着十分優秀的性質。

可持久化字典樹在可持久化方式上與可持久化字典樹十分相似，即每次隻修改被添加或值被修改的節點，而保留沒有被改動的節點，在上一個版本的基礎上連邊，使最後每個版本的 Trie 樹的根周遊所能分離出的 Trie 樹都是完整且包含全部資訊的。

在字典樹的拓展部分學習過程中，我們提到了一種特殊的字典樹：0-1 Trie，而在可持久化字典樹中，大部分題目都是以0-1 Trie的形式出現的。

0-1 Trie 是建立在字典樹基礎上，專門用于維護異或和(支援修改、删除、重新插入、全局加一)的資料結構。在維護異或和的時候，我們需要從低位到高位建立0-1 Trie。

二、可持久化字典樹 詳解

我們要對一個長度為 的數組

1. 在數組的末尾添加一個數，數組的長度自增。
2. 給出查詢區間和一個值，要求找到一個，求當時，最大。

我們發現，求區間異或和實際上是一個繁瑣的操作。由于異或操作滿足可減性，是以我們考慮用字首和進行維護，則有：

然後我們隻需要對進行維護，就能很友善的查詢到區間異或值。實際上，我們将問題轉化為：已知，求，使取得最大值。

我們可以延續可持久化線段樹的思路，考慮每次的查詢都查詢整個區間。我們隻需把這個區間建一棵 Trie 樹，将這個區間中的每個樹都加入這棵 Trie 中，查詢的時候，盡量往與目前位不相同的地方跳。

查詢區間，隻需要利用字首和和差分的思想，用兩棵字首 Trie 樹（也就是按順序添加數的兩個曆史版本）相減即為該區間的線段樹。再利用動态開點的思想，不添加沒有計算過的點，以減少空間占用。

struct trie_persistent{
    int cnt;
    int ch[maxn * 24][2], sum[maxn * 24];

    inline int insert(int x, int val){
        int o, y; o = y = ++cnt;
        for(int i = 23; i >= 0; i++){
            ch[y][0] = ch[x][0];
            ch[y][1] = ch[x][1];
            sum[y] = sum[x] + 1;            //更新位置計數
            int tmp = (val & (1 << i)) >> i;
            //建立節點
            x = ch[x][tmp];
            ch[y][tmp] = ++cnt;
            y = ch[y][tmp];
        }
        sum[y] = sum[x] + 1;
        return o;
    }

    inline int query(int l, int r, int val){
        int ans = 0;
        for(int i = 23; i >= 0; i--){
            int c = (val & (1 << i)) >> i;
            if(sum[ch[r][c ^ 1]] - sum[ch[l][c ^ 1]]){
                ans = ans + (1 << i);
                r = ch[r][c ^ 1];
                l = ch[l][c ^ 1];
            }
            else{
                r = ch[r][c];
                l = ch[l][c];
            }
        }
        return ans;
    }
}      

struct Trie_Persistent{
    const static int LetterSize = 5; // 字元集大小
    const static int TrieSize = 20 * ( 1e5 + 50); // 可能的所有節點總數量
    int tot; // 節點總數
    //節點類型
    struct node{
        int ptr[LetterSize]; // trie_node_ptr[]
        int cnt[LetterSize]; // 維護字元集數目
    }tree[TrieSize];
    // 擷取字元集哈希編号 ， 必須在 [0 , LetterSize) 之内
    inline int GetLetterIdx(int c){return c - 'a';}
    // 插入字元串 str , 上一個副本是 f
    int insert(const char * str ,int f){
        int len = strlen( str );
        int res = tot++; // 建立虛拟根結點
        tree[res] = tree[f]; // 初始化
        int cur = res; // 目前指針
        for(int i = 0 ; i < len ; ++ i){
            int idx = GetLetterIdx( str[i] ); // 擷取字元編号
            int p = tot ++ ;  // 建立下一個虛拟節點
            tree[cur].cnt[idx] ++ ;
            tree[cur].ptr[idx] = p;
            f = tree[f].ptr[idx]; // 上一個副本的指針更新
            tree[p] = tree[f];  // updata information;
            cur = tree[cur].ptr[idx]; // updata ptr
        }
        return res;
    }
    // 在 [l ,r] 副本中查找字元串str
    // 參數帶入( str , root[l-1] , root[r])
    int find(const char * str , int l ,int r){
        int len = strlen(str);
        for(int i = 0 ; i < len ; ++ i){
            int idx = GetLetterIdx ( str[i] ); // 擷取字元Hash
            int cnt = tree[r].cnt[idx] - tree[l].cnt[idx];
            if(!cnt) return 0;
            l = tree[l].ptr[idx];
            r = tree[r].ptr[idx];
        }
        return 1;
    }
    //初始化函數
    void init(){ 
        tot = 1;
        for(int i = 0 ; i < LetterSize ; ++ i) tree[0].ptr[i] = 0 , tree[0].cnt[i] = 0;
    } 
}trie;