一个长度为 2^n 的数组先把相邻元素做 OR，下一轮把相邻结果做 XOR，再继续交替，直到只剩一个值。数组发生单点修改后，需要立刻输出新的最终值。

若每次都从头执行所有归约轮次，绝大部分没有变化的区间会被重复计算。线段树恰好保存了这套二叉归约结构：叶子是原数组，内部节点保存两个孩子的合并结果；一次修改只影响一条从叶子到根的路径。

1. 官方信息与约束

339D · Xenia and Bit Operations 官方题目 于 2026-09-14 核对：难度 1700，官方标签为 data structures、trees，时间限制 2 秒，内存限制 256 MB。

输入中的 n 是归约层数，实际数组长度为 N=2^n。第一轮对相邻原始元素做按位 OR，第二轮做按位 XOR，之后交替；每次把位置 p 改成 b，输出整棵归约后的唯一结果。

官方约束 对实现的影响
1≤n≤17 真实数组长度最多 131072
1≤m≤10^5 每次修改必须远快于重算整个数组
0≤a[i],b<2^30 int 足以保存所有 OR/XOR 结果
长度恒为二次幂 每层都能完整两两配对

2. 朴素重算浪费在哪里

一次完整归约需要计算：

1
N/2 + N/4 + ... + 1 = N - 1

所以每次修改后重算是 O(N)，十万次修改在最大数据下无法通过。

修改一个叶子时，与它无关的兄弟子树完全没有变化。真正需要重算的只有：叶子的父节点、父节点的父节点，直到根，共 n=log₂N 个内部节点。

这就是线段树的更新路径。与普通“区间和线段树”相比，本题的特殊点只有一个：不同高度使用不同合并运算。

3. OR 和 XOR 分别做了什么

对某一二进制位：

左位 右位 OR XOR
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 0

OR 表示“至少一个孩子拥有这一位”，XOR 表示“两个孩子在这一位不同”。两种运算都只依赖左右孩子的当前结果，因此满足树形自底向上合并的条件。

但是 OR 与 XOR 不满足可以随意换括号的统一结合规则。例如 (1 OR 2) XOR (3 OR 4) 不能改写成对四个数连续使用同一个操作。树的层次是题意的一部分，必须保存。

4. 用节点高度决定运算

从叶子向上计数：

  • 高度 1，即叶子的父层，使用 OR；
  • 高度 2，使用 XOR；
  • 高度 3，再使用 OR；
  • 此后持续交替。

因此根节点用什么操作取决于 n 的奇偶：n 为奇数时根用 OR，n 为偶数时根用 XOR。实现不必专门判断根；建树和更新都从最底层的 OR 开始，每上升一层就翻转操作。

为什么节点区间长度也能决定运算

高度 1 的节点覆盖 2 个叶子，高度 2 覆盖 4 个，高度 3 覆盖 8 个。节点覆盖长度的二进制指数就是它离叶子的高度。因此无论写递归树还是迭代树，只要合并时知道当前层，就能唯一确定运算。

5. 官方样例手工演算

初始数组是 [1,6,3,5]，n=2：底层使用 OR，根使用 XOR。

状态 左半 OR 右半 OR 根 XOR 输出
初始 [1,6,3,5] `1 6=7` `3 5=7`
a[1]=4 `4 6=6` 7 6^7=1
a[3]=4 6 `4 5=5` 6^5=3
a[1]=2 `2 6=6` 5 6^5=3
再令 a[1]=2 6 5 3 3

第二次修改只需要重算右半节点和根，左半的 6 可以直接复用。最后一次虽然新旧值相同，沿路径重算仍然正确，复杂度也不变。

6. 迭代线段树的数组布局

令 base=N，使用大小 2N 的数组 tree：

  • tree[base..2*base-1] 保存原数组；
  • tree[i] 的孩子是 tree[2*i] 与 tree[2*i+1]；
  • 根是 tree[1]。

建树时从区间 [base/2, base-1] 计算第一层 OR，再处理 [base/4, base/2-1] 的 XOR。因为 base 是二次幂，同一层节点编号正好形成连续区间 [layerStart, 2*layerStart)。

单点修改先写入叶子 base+p-1，然后不断除以 2 回到父节点。局部变量 useOr 从 true 开始，每上升一层取反。

7. 正确性证明

引理一：建树后每个节点保存其区间的正确归约值

对节点高度归纳。高度 0 的叶子直接保存原数组值，结论成立。假设高度 h-1 的两个孩子都正确保存各自区间的归约值；题目规定高度 h 使用 OR（h 为奇数）或 XOR（h 为偶数），算法使用同一运算合并两个孩子，所以父节点也正确。归纳到根，tree[1] 是全数组结果。

引理二：单点修改后，更新路径外的节点仍然正确

路径外节点覆盖的区间不包含被修改位置，其中所有叶子均未改变；其原有归约值因此仍正确，无需重算。

引理三：自底向上重算后，更新路径上的节点全部正确

修改后的叶子正确。沿路径向上，每一步的两个孩子都已经正确：一个可能刚刚重算，另一个由引理二保持正确。算法又根据高度使用规定运算，故父节点正确。归纳到根即可。

定理：每次输出都是修改后数组的规定值

由引理二和引理三，更新结束后整棵树所有节点都正确；特别地，根保存全数组按题意逐轮 OR/XOR 的结果。因此输出 tree[1] 正确。

8. 完整 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
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int levels, updates;
    cin >> levels >> updates;

    const int base = 1 << levels;
    vector<int> tree(2 * base, 0);
    for (int i = 0; i < base; ++i) cin >> tree[base + i];

    bool useOr = true;
    for (int layerStart = base / 2; layerStart >= 1; layerStart /= 2) {
        for (int node = layerStart; node < 2 * layerStart; ++node) {
            if (useOr) tree[node] = tree[2 * node] | tree[2 * node + 1];
            else tree[node] = tree[2 * node] ^ tree[2 * node + 1];
        }
        useOr = !useOr;
    }

    while (updates--) {
        int position, value;
        cin >> position >> value;

        int node = base + position - 1;
        tree[node] = value;
        useOr = true;

        while (node > 1) {
            node /= 2;
            if (useOr) tree[node] = tree[2 * node] | tree[2 * node + 1];
            else tree[node] = tree[2 * node] ^ tree[2 * node + 1];
            useOr = !useOr;
        }

        cout << tree[1] << '\n';
    }
}

建树访问 2N-1 个节点，时间 O(N)；一次更新经过 n=log₂N 层，时间 O(log N)，全部查询为 O(N+m log N)。线段树数组占 O(N) 空间。

9. 边界与错误清单

场景 正确处理 常见错误
n=1 根直接对两个叶子做 OR 固定认为根总是 XOR
n 为偶数 根层使用 XOR 从根向下时奇偶判断反转
n 为奇数 根层使用 OR 只按查询次数切换操作
输入位置从 1 开始 叶子为 base+p-1 少减 1，更新相邻位置
修改值与原值相同 结果不变，重算仍合法 特判后漏读或漏输出
值接近 2^30 int 仍安全 误以为位运算会产生进位溢出
建树后更新 每次从叶子父层重新以 OR 开始 沿用建树结束后的 useOr 状态

10. 独立验证

tests/verify-xenia-bit-operations-article.cjs 会提取并以 -std=c++17 -Wall -Wextra -pedantic 编译本文代码，要求零警告。参考实现不建线段树：每次修改后复制整个数组，按题意逐轮把相邻值先 OR、再 XOR，直到剩一个值。

测试覆盖官方样例、最小两元素、全零、重复修改、最高位附近的数、奇偶层数与固定种子随机序列；另用 2^17 个叶子和十万次修改验证复杂度，其中只有一个非零传播路径，期望值可独立直接确定。

这题适合作为线段树入口，因为节点含义和合并规则都很明确。以后遇到区间和、最大值、括号匹配或懒标记时，仍然先回答同一个问题：节点保存什么摘要，两个孩子怎样合并，修改会影响哪些祖先。