求1~n数组的最大异或和

求1~n数组的最大异或和也可以使用类似于求一段区间最大异或和的方法。具体步骤如下：

1. 将1~n数组中的所有数以二进制形式插入到字典树中。

2. 对于每个数，从高位到低位依次匹配字典树上的节点，如果当前位为1，就往字典树的右子树走，否则就往左子树走。匹配完整个二进制数后，我们可以得到一个最大的异或值。

3. 对于1~n数组，我们可以将其中的相邻两个数看作一段区间，然后使用类似于求一段区间最大异或和的方法求出最大异或和。

时间复杂度为O(nlogC)，其中n为数组长度，C为数的范围。以下是求1~n数组的最大异或和的C++代码：

#include <iostream>
using namespace std;

const int MAXN = 100010;
const int MAXBITS = 30;

struct TrieNode {
    int cnt;
    int children[2];
} trie[MAXN * MAXBITS];
int root, node_cnt;

void insert(int x) {
    int p = root;
    for (int i = MAXBITS - 1; i >= 0; i--) {
        int idx = (x >> i) & 1;
        if (!trie[p].children[idx]) {
            trie[p].children[idx] = ++node_cnt;
        }
        p = trie[p].children[idx];
        trie[p].cnt++;
    }
}

int query(int x) {
    int p = root, res = 0;
    for (int i = MAXBITS - 1; i >= 0; i--) {
        int idx = (x >> i) & 1;
        if (trie[trie[p].children[idx ^ 1]].cnt > 0) {
            res += (1 << i);
            p = trie[p].children[idx ^ 1];
        } else {
            p = trie[p].children[idx];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    root = 1;
    node_cnt = 1;
    int pre = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        insert(pre);
        pre ^= x;
        ans = max(ans, query(pre));
    }
    cout << ans << endl;
    return 0;
}