给一个区间里的每个数异或 x，然后查询它们的和。修改是位运算，查询却是普通加法：只存一个区间和，无法直接完成更新；把和拆成各位的贡献，问题就变成了若干次整段翻转。

这篇接在线段树三题与子树染色之后。与438D 区间取模不同，242E 确实能整段更新；关键是找对摘要，再证明多个标记可以压成一个掩码。

阅读前

理解区间摘要

会建树、合并和部分区间递归，再复习异或对单个位的作用。

关键问题

怎样翻转整段

把数字之和拆成每一位的一的数量；同一位翻转两次抵消。

完成标志

说明摘要与标记的关系

解释父节点已经更新时，孩子为何可以暂时保留旧值。

官方题目与数值范围

题目为 Codeforces 242E XOR on Segment。以下信息于 2026-10-06 按官方题目页核对，推导与实现为本站原创。

项目 官方信息
难度与标签 2000；bitmasks、data structures
数组长度 n 1 到 100000
操作数 m 1 到 50000
初始元素 0 到 1000000
更新掩码 x 1 到 1000000
1 l r 查询闭区间 [l,r] 的元素之和
2 l r x 对闭区间中的每个元素执行异或 x

输入先给 n 和数组，再给 m，不是第一行同时给 n、m。每个操作按原顺序执行。

因为 1000000 小于 2^20，初始值和所有掩码的第 20 位及更高位都为零。异或不会产生进位，因此任何更新后的元素仍小于 2^20，但不一定仍小于等于 1000000。代码维护第 0 到第 19 位；和的安全上界是 100000 × (2^20−1) = 104857500000，必须用 long long。

相同的和不代表异或后仍有相同的和

朴素做法每次逐项更新、逐项求和，单次最坏 O(n)，整串操作 O(nm)。普通区间和线段树也不能把更新写成 sum ^= x。

原区间 原和 各元素异或 1 后 新和
[0,2] 2 [1,3] 4
[1,1] 2 [0,0] 0

同一个旧和对应两个新和，说明还缺信息。即使题目名字含 XOR，查询要的也不是“所有数的异或值”。不要把更新运算和查询运算混为一谈。

每个位保存一的数量

节点代表 [L,R]，长度 len = R−L+1。定义 ones[b] 为这一段中第 b 位等于 1 的元素个数。该位对和的贡献是 ones[b] × 2^b，所以：

sum = Σ ones[b] × 2^b，其中 b 从 0 到 19。

两个孩子合并时，每一位的计数相加，和也相加。计数不需要知道哪些位属于同一个元素：整数之和可以按位贡献相加，而本题更新也独立地作用于每一位。这种摘要足够回答本题，却不能直接支持区间最大值等需要位间关联的查询。

当 x 的第 b 位为 0，该位不变；当它为 1，每个元素的这一位都翻转。因此整段的计数变为 len−ones[b]。

第 b 位状态 翻转前数量 翻转后数量
一 ones[b] len−ones[b]
零 len−ones[b] ones[b]
对区间和的贡献 ones[b] × 2^b (len−ones[b]) × 2^b

一次翻转对和的增量是 (len−2×ones[b]) × 2^b。代码先用旧计数更新和，再替换计数；乘法使用 1LL << b，避免在转换为 64 位之前就发生溢出。

多次异或怎样压成一个标记

对任意数 a，先异或 x，再异或 y，结果为 a ^ (x ^ y)。于是节点的待下传标记使用 lazy ^= x，而不是赋值、相加或按位 OR。

例如 3 为二进制 011，5 为 101。先做 3 再做 5，相当于 6 即 110：最低位翻转两次抵消，其余两位各翻转一次。相同掩码连续作用两次就恢复原状。累计标记可以变成 0，尽管官方输入的单次 x 不允许为 0。

完整覆盖一个节点时，立即更新它的 ones 和 sum，再合成标记。此时节点摘要已经是最新状态；标记只说明哪些翻转还没有传给孩子，并不是说当前节点还没更新。

若需要继续进入孩子，先把非零标记作用到两个孩子，各自使用自己的区间长度，再清零父标记。随后孩子与父节点表示同一时刻的数组，才能继续局部修改或查询。

只查询整段时可直接取当前和，不需要先下传。局部查询虽然不改变实际数组，也需要下传，因为孩子可能还是旧状态；下传后父摘要仍正确，不必再合并一次。

正确性由三个不变量连接

摘要定义。 建树时叶子的每位计数由元素得到，内部节点逐位相加，因此计数和区间和都满足定义。翻转一个位时，一与零互换，len−ones[b] 恰好是新的一的数量；增量公式恰好修正这一位的贡献。逐个处理掩码中的位，得到整段异或后的精确摘要。

标记语义。 父节点摘要始终包含已经作用在该节点上的全部更新；孩子尚未接收的翻转等于 lazy。新更新与旧标记通过异或合成，来自异或的结合律及同位两次翻转抵消。下传用同一个变换更新孩子，再清空标记，保持这个语义。

递归操作。 不相交区间不改变，查询贡献为 0。完整覆盖使用已证明正确的摘要或变换。部分覆盖先下传，使孩子最新，再按长度归纳完成局部操作；修改后合并恢复父摘要，查询把互不重叠片段的和相加。因此每次更新与查询都正确。

这不是“保存标记就能正确”的模板证明：必须同时说明变换能作用于摘要、标记能正确组合、局部访问之前孩子能恢复到最新状态。

手算整段与局部更新

以下是原创例子，初始数组 [1,2,3,5]。低三位的一的数量从低到高为 [3,2,1]，和为 3×1+2×2+1×4=11。

操作 当前数组 输出或说明
1 1 4 [1,2,3,5] 11
2 1 4 3 [2,1,0,6] 前两位翻转，计数变为 [1,2,1]，和为 9
1 2 3 [2,1,0,6] 1；需要下传整段标记
2 2 3 5 [2,4,5,6] 局部翻转第 0、2 位，再合并
1 1 4 [2,4,5,6] 17
2 2 3 5 [2,1,0,6] 同一局部掩码再做一次，抵消
1 1 4 [2,1,0,6] 9

若第三步直接读未下传的孩子，就可能错误地返回旧数组中 2+3=5。这个例子同时检查整段更新、局部查询、交错更新与抵消。

复杂度与适用边界

设 B=20。建树逐节点处理 B 个计数，时间 O(nB)，空间 O(nB)。每次区间操作访问 O(log n) 个完整片段及其边界祖先，合并、下传或完整更新最多处理 B 位，所以时间 O(B log n)；整串时间 O(nB+mB log n)。这里是每次操作的最坏界，不需要取模问题的均摊分析。

实现使用一个线段树，每个节点放 20 个 int 计数、一个 long long 和与一个 int 掩码。计数最多 n，int 足够；大数组由 vector 分配，递归深度只有 O(log n)。不需要开 20 棵独立的树。

容易出错的位置 正确处理
对 sum 直接异或 异或每位计数对应的零一分布
lazy = x 或 lazy |= x 使用 lazy ^= x，保留抵消
局部递归前没有下传 先让孩子接收父节点累计变换
用父区间长度更新两个孩子 分别使用孩子的实际长度
只开 19 位 第 19 位仍可能为 1；维护 0 到 19
认为更新后仍不超过 1000000 上界是 2^20−1，异或可越过初始上界
把查询写成区间异或 查询运算始终是普通求和
先在 int 中乘再转 long long 在乘法之前使用 64 位权重

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <array>
#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
    static constexpr int B = 20;
    struct Node {
        array<int, B> ones{};
        long long sum = 0;
        int lazy = 0;
    };
    int n;
    vector<Node> tree;

    void pull(int p) {
        tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
        for (int b = 0; b < B; ++b)
            tree[p].ones[b] = tree[p * 2].ones[b] + tree[p * 2 + 1].ones[b];
    }
    void apply(int p, int len, int x) {
        for (int b = 0; b < B; ++b) {
            if ((x >> b) & 1) {
                tree[p].sum += (len - 2 * tree[p].ones[b]) * (1LL << b);
                tree[p].ones[b] = len - tree[p].ones[b];
            }
        }
        tree[p].lazy ^= x;
    }
    void push(int p, int l, int r) {
        if (tree[p].lazy == 0 || l == r) return;
        int mid = l + (r - l) / 2;
        apply(p * 2, mid - l + 1, tree[p].lazy);
        apply(p * 2 + 1, r - mid, tree[p].lazy);
        tree[p].lazy = 0;
    }
    void build(int p, int l, int r, const vector<int>& a) {
        if (l == r) {
            tree[p].sum = a[l];
            for (int b = 0; b < B; ++b) tree[p].ones[b] = (a[l] >> b) & 1;
            return;
        }
        int mid = l + (r - l) / 2;
        build(p * 2, l, mid, a);
        build(p * 2 + 1, mid + 1, r, a);
        pull(p);
    }
    void update(int p, int l, int r, int ql, int qr, int x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(p, r - l + 1, x);
            return;
        }
        push(p, l, r);
        int mid = l + (r - l) / 2;
        update(p * 2, l, mid, ql, qr, x);
        update(p * 2 + 1, mid + 1, r, ql, qr, x);
        pull(p);
    }
    long long query(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[p].sum;
        push(p, l, r);
        int mid = l + (r - l) / 2;
        return query(p * 2, l, mid, ql, qr)
             + query(p * 2 + 1, mid + 1, r, ql, qr);
    }
public:
    explicit SegmentTree(const vector<int>& a)
        : n(static_cast<int>(a.size()) - 1), tree(4 * n + 4) {
        build(1, 1, n, a);
    }
    void update(int l, int r, int x) { update(1, 1, n, l, r, x); }
    long long query(int l, int r) { return query(1, 1, n, l, r); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    SegmentTree seg(a);
    int m;
    cin >> m;
    while (m--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) cout << seg.query(l, r) << '\n';
        else {
            int x;
            cin >> x;
            seg.update(l, r, x);
        }
    }
    return 0;
}

独立验证与复盘

验证程序位于 tests/verify-xor-segment-article.cjs，直接提取上面的 C++17 代码编译。参考模型只保存数组并逐项异或、逐项求和，不使用按位计数或线段树。覆盖官方样例、本文手算、小数组穷举、固定种子随机操作，以及 n=100000、m=50000 的规模与 64 位结果。大规模整段更新另外使用“所有元素相同”的闭式结果核验，避免参考程序重复扫描数十亿次。

复盘 如果修改改成按位 OR 会怎样

掩码为一的位不再翻转，而是全部置一，所以对应计数变成区间长度；同类 OR 标记可以按位 OR 合成。

但若题目混合赋值、OR 与 XOR，单一异或掩码就不够。先定义每位的变换，再按实际先后次序组合，不能沿用本题的抵消结论。

回到算法路线比较三种更新：覆盖标记替换旧颜色，异或标记按位抵消，取模更新则依靠剪枝与势能。节点摘要相似，不代表修改规律相同。

资料来源