BZOJ 3261 詳解：可持久化 Trie 樹解決區間最大異或和查詢

題目大意

初始序列 A[1..N]，支援兩種操作（M ≤ 300,000）：

• A x：末尾添加 x
• Q l r x：查詢 p ∈ [l, r] 使 A[p] xor A[p+1] xor ... xor A[N] xor x 最大

保證 A[i] ≤ 10⁷（24 位）。

核心轉化

定義前綴異或 S[i] = A[1] xor ... xor A[i]，S[0] = 0。
區間異或 A[p] xor ... xor A[N] = S[N] xor S[p-1]。
查詢目標：max_{p∈[l,r]} ( S[N] xor S[p-1] xor x ) = max_{p∈[l,r]} ( (S[N] xor x) xor S[p-1] )。
設 val = S[N] xor x（查詢時固定），問題轉化為：在 S[l-1..r-1] 中找與 val 最大異或值的元素。

可持久化 Trie 樹

對前綴異或序列 S[0], S[1], ..., S[N] 建立歷史版本 Trie：

• 第 i 版包含 S[0..i]
• 每個節點存儲 ch[2] 子節點索引、cnt 經過此節點的版本計數
• 插入 S[i] 時復用 i-1 版節點，只創建路徑上新節點（O(24) 新節點）

關鍵代碼

const int MAXN = 600005;   // 最大版本數
const int MAXM = 20000005;   // 最大節點數 (版本數 × 24)
int ch[MAXM][2], cnt[MAXM], rt[MAXN];
int tot = 0;

void insert(int preVer, int x, int ver) {
    int cur = rt[ver] = ++tot;
    cnt[cur] = ver;  // 記錄版本號，用於區間查詢判斷
    for (int i = 23; i >= 0; --i) {
        int b = (x >> i) & 1;
        ch[cur][b^1] = ch[preVer][b^1];  // 復用另一分支
        ch[cur][b] = ++tot;               // 創建新節點
        cur = ch[cur][b];
        preVer = ch[preVer][b];
        cnt[cur] = ver;
    }
}

int query(int lVer, int rVer, int x) {
    int ans = 0;
    int u = rt[rVer], v = rt[lVer];
    for (int i = 23; i >= 0; --i) {
        int b = (x >> i) & 1;
        int want = b ^ 1;  // 貪心選擇相反位
        // 檢查 want 分支在 [lVer, rVer] 內是否有節點
        if (cnt[ch[u][want]] - cnt[ch[v][want]] > 0) {
            ans |= (1 << i);
            u = ch[u][want];
            v = ch[v][want];
        } else {
            u = ch[u][b];
            v = ch[v][b];
        }
    }
    return ans;
}

完整流程

int main() {
    int N = read(), M = read();
    int S = 0;
    insert(0, 0, 0);  // S[0] = 0
    for (int i = 1; i <= N; ++i) {
        int x = read();
        S ^= x;
        insert(rt[i-1], S, i);  // 版本 i 包含 S[0..i]
    }
    
    for (int i = N+1; i <= N+M; ++i) {
        char op = readChar();
        if (op == 'A') {
            int x = read();
            S ^= x;
            insert(rt[i-1], S, i);
        } else {  // 'Q'
            int l = read(), r = read(), x = read();
            int val = S ^ x;
            int ans = query(l-1, r-1, val);
            printf("%d\n", ans);
        }
    }
}

關鍵細節

1. 初始插入 0：S[0] = 0 對應版本 0，保證 p=1 時查詢 S[0]
2. 版本號作為節點標記：cnt[node] = version，查詢時 cnt[u] - cnt[v] > 0 判斷區間內是否存在
3. 空節點處理：ch[0][*] = 0，cnt[0] = 0，rt[0] = 0 或插入版本 0
4. 節點數估算：(N+M) × 24 ≈ 720 萬，開 2000 萬 安全

複雜度分析

• 構建：O((N+M) × 24)
• 查詢：O(24)
• 空間：O((N+M) × 24)

總結

BZOJ 3261 是可持久化 Trie 樹的經典入門題。核心流程：前綴異或轉化 → 歷史版本 Trie 維護集合 → 版本差分查詢區間最大異或。版本號標記節點替代傳統的「左/右子樹大小」是簡化區間判斷的關鍵技巧。可持久化數據結構是動態區間查詢的強大工具，掌握 Trie 版本為學習可持久化線段樹、平衡樹奠定基礎。