字典树（前缀树）求区间异或和（异或对）最大值

kurish / 2023-08-23 / 原文

字典树（前缀树）求区间异或和（异或对）最大值

求子区间异或对最大值

求子区间异或对的最大值，利用前缀树可以在每次询问对子区间内的每个元素在O(log n)的时间内得到答案，执行n此的时间花费为O(n logn)，而得到答案需要已经建立前缀树，而每次询问答案都需要重新建立一棵前缀树，每次建树最坏情况下的时间花费为O(n)。总的时间为O(n^2 logn)，对于这题来说已经足够了。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<vector<int>> son;
vector<int> a;
int idx;

void insert(int x){
    int p = 0;
    for(int i = 10; i >= 0; i--){
        int u = ((x >> i) & 1);
        if(!son[p][u]){
            son[p][u] = ++idx;
        }
        p = son[p][u];
    }
}

int query(int x){
    int p = 0;
    int ret = 0;
    for(int i = 10; i >= 0; i--){
        int u ((x >> i) & 1);
        if(son[p][!u]){
            ret = ret * 2 + 1;
            p = son[p][!u];
        }
        else{
            ret = ret * 2;
            p = son[p][u];
        }
    }
    return ret;
}

void solve(){
    int n, m;
    cin >> n >> m;
    a.resize(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    son.resize((n + 10) * 10, vector<int>(2));
    while(m--){
        idx = 0;
        int l, r;
        cin >> l >> r;
        for(int i = l; i <= r; i++){
            insert(a[i]);
        }

        int maxv = 0;
        for(int i = l; i <= r; i++){
            maxv = max(maxv, query(a[i]));
        }

        cout << maxv << endl;

        for(int i = 0; i < idx; i++){
            son[i][0] = son[i][1] = 0;
        }
    }

}

int main(){
    solve();
    return 0;
}

求子区间异或和最大值C. Vampiric Powers, anyone?

分析性质可以知道，只要求出子区间所能得到的最大异或和即可。而求一段连续子区间的异或和，可以利用前缀和：

s[n] = s[1] ^ s[2] ^ s[3] ^ ... ^ s[i] ^ s[i + 1] ^ ... ^ s[n]

s[i] = s[1] ^ s[2] ^ s[3] ^ ... ^ s[i] = s[n] ^ s[i - 1]

把这样处理得到的前缀和序列作为对象，求子区间异或和最大值的问题就被转换成了求区间异或对最大值问题。利用前缀树处理，就能在O(log n)的时间内得到子区间异或和的最大值。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> a;
vector<vector<int>> son;
int idx;

void insert(int x){
    int p = 0;
    for(int i = 8; i >= 0; i--){
        int u = ((x >> i) & 1);
        if(!son[p][u]){
            son[p][u] = ++idx;
        }
        p = son[p][u];
    }
}

int query(int x){
    int p = 0;
    int ret = 0;
    for(int i = 8; i >= 0; i--){
        int u = ((x >> i) & 1);
        if(son[p][!u]){
            ret = ret * 2 + 1;
            p = son[p][!u];
        }
        else{
            ret = ret * 2;
            p = son[p][u];
        }
    }
    return ret;
}

void solve(){
    idx = 0;
    int n;
    cin >> n;
    a.resize(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = a[i] ^ a[i - 1];
    }

    son.resize((n + 10) * 8, vector<int>(2));

    int maxv = 0;
    for(int i = 0; i <= n; i++){
        insert(a[i]);
        maxv = max(maxv, query(a[i]));
    }
    
    cout << maxv << endl;

    for(int i = 0; i <= idx; i++){
        son[i][0] = son[i][1] = 0;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}