字典树写法模板1
(前缀和 + 字典树)
1.求前缀异或和
2.从左到右枚举所有前缀和,记录最大的异或值
3.现在把 + 换成 异或,异或运算的逆运算还是异或本身, 区间[i, j]异或和:sum = pre[j] ^ pre[i - 1]。
4.贪心:贪心性质
题目要求输出长度最小的区间,并且右端点也应该最小。
首先区间长度最小。我们每次向Trie树中插入一个数后,应当把它在原数组中的坐标也保存下来,而且如果该数重复出现,应当覆盖掉原来的坐标。比如求出前缀和数组为:[0,1,2,2,2,3],当向Trie树插入第三个2时,对应的2的坐标应该更新为5(假设下标从1开始)。这样做保证了每次查询返回的最大异或配对的坐标都是离当前遍历坐标最近的,因此保证了最小区间。
右端点最小。由于我们是从左向右遍历,让异或值严格大于当前最大值时及时更新最大值就可以了。
时间复杂度
1.单趟遍历建树:O(n*h),h是建树高度,树高可以设置为21。
2.每个结点根据字典树查找最大的异或值,O(n*h)。
3.所以总共时间复杂度就是O(n)。
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 20, M = 1e5 * 22;
int id[M], son[M][2], idx;
int num[N], s[N];
int n;
//记录前缀和 + 前缀和取两个异或最大
void insert(int x, int v)
{
int p = 0;
for (int i = 20; i >= 0; i--) {
int u = x >> i & 1;
if (!son[p][u]) {
son[p][u] = idx++;
}
p = son[p][u];
}
id[p] = v;
}
int search(int x)
{
int p = 0;
for (int i = 20; i >= 0; i--) {
int u = x >> i & 1;
if (son[p][u ^ 1]) {
p = son[p][u ^ 1];
}else{
p = son[p][u];
}
}
return id[p];
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> num[i];
s[i] = s[i - 1] ^ num[i];
}
int l = 1, r = 1, ans = -1;
insert(s[0], 0);
for (int i = 1; i <= n; i++) {
int k = search(s[i]);
int t = s[i] ^ s[k];
if (t > ans) {
ans = t;
l = k + 1;
r = i;
}
insert(s[i], i);
}
cout << ans << ' ' << l << ' ' << r << endl;
return 0;
}
字典树写法模板2
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 20;
int num[N], s[N];
int n;
class Trie{
public:
int idx;
Trie* next[2];
Trie() {
idx = 0;
next[0] = nullptr;
next[1] = nullptr;
}
};
Trie* root = new Trie();
void insert(int x, int j)
{
Trie* p = root;
for (int i = 20; i >= 0; i--) {
int u = x >> i & 1;
if (p->next[u] == nullptr) {
p->next[u] = new Trie();
}
p = p->next[u];
}
p->idx = j;
}
int search(int x)
{
Trie* node = root;
for (int i = 20; i >= 0; i--) {
int u = x >> i & 1;
if (node->next[u ^ 1]) {
node = node->next[u ^ 1];
}else{
node = node->next[u];
}
}
return node->idx;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> num[i];
s[i] = s[i - 1] ^ num[i];
}
int l = 1, r = 1, ans = -1;
insert(s[0], 0);
for (int i = 1; i <= n; i++) {
int k = search(s[i]);
int t = s[i] ^ s[k];
if (t > ans) {
ans = t;
l = k + 1;
r = i;
}
insert(s[i], i);
}
cout << ans << ' ' << l << ' ' << r << endl;
return 0;
}