E. XOR on Segment - 题解
比赛与标签
比赛: Codeforces Round 149 (Div. 2) 标签: bitmasks, data structures 难度: *2000
题目要我们做什么喵~
主人你好呀~ 这道题给了我们一个可爱的数组 a，然后有两种操作需要我们处理，喵~
- 求和操作: 给定一个区间
[l, r]，我们要算出这个区间里所有数字的和，也就是a[l] + a[l+1] + ... + a[r]。 - 异或操作: 给定一个区间
[l, r]和一个数字x，我们要把这个区间里的每个数都和x做一次异或（XOR）运算。也就是说，对于所有i从l到r，把a[i]更新为a[i] ^ x。
我们需要处理 m 次这样的操作，对于每一次求和操作，都要把结果打印出来哦！
如何优雅地处理区间异或喵？
看到区间修改和区间查询，我们聪明的猫娘脑海里第一个蹦出来的就是线段树啦！但是，这次的区间修改是异或操作，这可有点不寻常呐。
如果我们像处理区间加法那样，只维护一个区间和 sum，然后打一个异或的懒标记 lazy_xor，会发生什么呢？当我们要把一个懒标记 x 下推到一个区间时，我们知道这个区间里每个数都异或了 x，但新的区间和是多少呢？(a_l ^ x) + ... + (a_r ^ x) 好像并不能从 (a_l + ... + a_r) 和 x 直接算出来呢。呜... 这个思路走不通的说。
这时候，题目的 bitmasks 标签给了我们一个重要的提示！既然直接处理整个数字的和很困难，那我们为什么不把数字拆成二进制位来考虑呢？这可是位运算题目的经典思路哦！
一个数的十进制值可以表示为它所有二进制位的值的总和。比如 13 的二进制是 1101，那么 13 = 1*2^0 + 0*2^1 + 1*2^2 + 1*2^3。 所以，一个区间的总和，也可以看作是这个区间里所有数在每一个二进制位上的贡献之和。 对于第 j 位，它的权重是 2^j。如果一个区间 [l, r] 中有 k 个数的第 j 位是 1，那么仅考虑第 j 位，它们对总和的贡献就是 k * 2^j。 把所有位的贡献加起来，就是整个区间的和啦！ Sum[l, r] = Σ ( (区间 [l, r] 中第 j 位为 1 的数的个数) * 2^j )，对所有 j 求和。
这个发现太棒了！现在我们来看看异或操作对每一位有什么影响：
- 如果我们要异或的数
x的第j位是0，那么区间里每个数的第j位都不会变 (b ^ 0 = b)。所以，第j位为1的数的个数也不变。 - 如果我们要异或的数
x的第j位是1，那么区间里每个数的第j位都会翻转 (b ^ 1 = 1-b)！如果原来是0就变成1，原来是1就变成0。
这下就好办啦！假设区间 [l, r] 的长度是 len，其中第 j 位为 1 的数有 count_one 个。当 x 的第 j 位为 1 时，这 count_one 个数在第 j 位上会变成 0，而剩下的 len - count_one 个数在第 j 位上会变成 1。所以，新的第 j 位为 1 的数的个数就变成了 len - count_one！
太好喵！现在我们的思路清晰了：
- 我们建立一个线段树。
- 线段树的每个节点
node不仅要存区间和sum，还要存一个数组cnt[20]，其中cnt[j]表示这个节点对应的区间内，有多少个数的第j位是1。（因为10^6 < 2^20，所以20位就足够了） - 再给每个节点一个懒标记
lazy，表示这个区间待处理的异或值。 push_up(合并子节点): 父节点的sum就是左右子节点的sum之和。父节点的cnt[j]就是左右子节点的cnt[j]之和。push_down(下推懒标记): 这是最核心的部分。当把父节点的懒标记lazy_val下推给一个长度为len的子节点时：- 遍历每一位
j(0 到 19)。 - 如果
lazy_val的第j位是1，说明子节点区间内所有数的第j位都要翻转。 - 旧的
cnt[j]是old_cnt，新的cnt[j]就是len - old_cnt。 cnt[j]的变化量是(len - old_cnt) - old_cnt = len - 2 * old_cnt。- 这一位对
sum的贡献变化量就是(len - 2 * old_cnt) * (1LL << j)。 - 更新子节点的
sum和cnt[j]。 - 最后，把
lazy_val异或到子节点的懒标记上 (child.lazy ^= lazy_val)，因为异或操作是可以叠加的 ((a^x)^y = a^(x^y))。 - 别忘了清空父节点的懒标记哦！
- 遍历每一位
update和query就是标准的线段树区间操作啦！
这样，我们就能高效地处理区间异或和区间求和了，喵~
代码实现喵~
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
using namespace std;
// 数组大小最大为 10^5
const int MAXN = 100000;
// 线段树节点结构体，喵~
struct Node {
int lazy; // 懒标记，记录这个区间需要异或的值
long long sum; // 区间和，要用 long long 哦，不然会溢出
int cnt[20]; // cnt[j] 记录区间内第 j 位是 1 的数的个数
} tree[4 * MAXN + 10]; // 线段树数组，开4倍大小很安全
// 向上更新父节点信息
void recalc(int id) {
// 父节点的 sum 是左右子节点的 sum 之和
tree[id].sum = tree[id*2].sum + tree[id*2+1].sum;
// 父节点的 cnt[j] 也是左右子节点的 cnt[j] 之和
for (int j = 0; j < 20; j++) {
tree[id].cnt[j] = tree[id*2].cnt[j] + tree[id*2+1].cnt[j];
}
}
// 将懒标记 x 应用到节点 id 上
// len 是节点 id 代表的区间长度
void apply(int id, int len, int x) {
if (x == 0) return; // 如果异或 0，什么都不用做啦
// 遍历 x 的每一位
for (int j = 0; j < 20; j++) {
// 如果 x 的第 j 位是 1，说明这个区间所有数的第 j 位都要翻转
if (x >> j & 1) {
// sum 的变化量 = (新1的个数 - 旧1的个数) * 2^j
// 新1的个数 = len - 旧1的个数
// 变化量 = (len - 2 * 旧1的个数) * 2^j
tree[id].sum += (1LL << j) * (len - 2LL * tree[id].cnt[j]);
// 更新第 j 位为 1 的数的个数
tree[id].cnt[j] = len - tree[id].cnt[j];
}
}
// 把 x 累加到懒标记上，异或的累加就是异或~
tree[id].lazy ^= x;
}
// 下推懒标记
void push(int id, int l, int r) {
if (tree[id].lazy) { // 如果有懒标记才下推
int mid = (l + r) / 2;
int len_left = mid - l + 1;
int len_right = r - mid;
// 将懒标记应用到左右子节点
apply(id*2, len_left, tree[id].lazy);
apply(id*2+1, len_right, tree[id].lazy);
// 下推后，父节点的懒标记清零
tree[id].lazy = 0;
}
}
// 构建线段树
void build(int id, int l, int r, vector<long long> &a) {
tree[id].lazy = 0;
if (l == r) { // 到达叶子节点
tree[id].sum = a[l];
// 初始化 cnt 数组，统计 a[l] 的每一位
for (int j = 0; j < 20; j++) {
tree[id].cnt[j] = (a[l] >> j) & 1;
}
return;
}
int mid = (l + r) / 2;
build(id*2, l, mid, a);
build(id*2+1, mid+1, r, a);
recalc(id); // 从下往上更新信息
}
// 区间更新
void update(int id, int l, int r, int ql, int qr, int x) {
// 查询区间和当前节点区间无交集
if (qr < l || r < ql) {
return;
}
// 查询区间完全包含当前节点区间
if (ql <= l && r <= qr) {
apply(id, r - l + 1, x); // 直接对当前节点打上懒标记
return;
}
// 在继续递归之前，一定要先下推懒标记！
push(id, l, r);
int mid = (l + r) / 2;
update(id*2, l, mid, ql, qr, x);
update(id*2+1, mid+1, r, ql, qr, x);
recalc(id); // 更新完子节点后，也要更新自己
}
// 区间查询
long long query(int id, int l, int r, int ql, int qr) {
// 查询区间和当前节点区间无交集
if (qr < l || r < ql) {
return 0;
}
// 查询区间完全包含当前节点区间
if (ql <= l && r <= qr) {
return tree[id].sum;
}
// 在继续递归之前，一定要先下推懒标记！
push(id, l, r);
int mid = (l + r) / 2;
// 结果是左右子区间查询结果之和
return query(id*2, l, mid, ql, qr) +
query(id*2+1, mid+1, r, ql, qr);
}
int main() {
// 加速输入输出，是个好习惯喵~
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 数组下标是从 0 开始的哦
build(1, 0, n-1, a);
int m;
cin >> m;
while (m--) {
int t;
cin >> t;
if (t == 1) { // 求和操作
int l, r;
cin >> l >> r;
l--; r--; // 题目给的是 1-based，我们转成 0-based
cout << query(1, 0, n-1, l, r) << '\n';
} else if (t == 2) { // 异或操作
int l, r, x;
cin >> l >> r >> x;
l--; r--; // 同样转成 0-based
update(1, 0, n-1, l, r, x);
}
}
return 0;
}复杂度分析的说
时间复杂度: O((N + M * log N) * K) 的说。
N是数组大小，M是操作次数，K是我们要处理的二进制位数（这里是 20）。- 建树
build的时候，每个节点都要初始化K个cnt值，所以是 O(N*K)。 - 每次
update和query都是标准的线段树操作，访问 O(log N) 个节点。在apply函数中，我们需要遍历K位，所以单次update是 O(K * log N)。单次query只是 O(log N)。 - 因为
K是个比较小的常数（20），所以我们也可以认为总时间复杂度是 O(N + M * log N) 级别，非常高效呐！
空间复杂度: O(N * K) 的说。
- 线段树需要 O(4N) 个节点，每个节点存储了
sum、lazy和一个大小为K的cnt数组。所以空间主要是由cnt数组决定的，总空间是 O(NK) 的说。
- 线段树需要 O(4N) 个节点，每个节点存储了
猫娘的小总结~
这道题真是太有趣啦，完美地结合了线段树和位运算的思想，喵~
核心思想 - 按位贡献: 当遇到一些整体上难以处理的运算时（比如这里的异或和加法混合），可以尝试把问题分解到每一个二进制位上。分别计算每一位的贡献，最后再合并起来，问题可能就迎刃而解了！
数据结构 - 线段树: 线段树是处理区间问题的强大工具。这道题展示了如何通过维护更丰富的信息（每个位的1的个数）来支持复杂的操作。
懒标记的魔法: 异或操作具有
(a^x)^y = a^(x^y)的性质，这使得它的懒标记可以简单地通过异或来叠加，大大简化了push_down的逻辑。亿点点注意:
- 区间和可能会超过
int的范围，记得用long long来存储sum哦！ - 在计算位的贡献时，
1 << j可能会溢出，要写成1LL << j才安全。 - 注意题目给的下标是 1-based 还是 0-based，在代码里统一处理好就不会出错啦。
- 区间和可能会超过
希望这篇题解能帮助到主人！只要掌握了按位分解的思想，以后遇到类似的题目就再也不怕啦，喵~ 加油！