纳米电脑主机：题解¶
解法比较¶
出题人解法的线段树按每一位维护区间整体异或、前缀异或为零和为一的数量，以及子区间异或和。拼接时，右区间前缀要按左区间整体异或翻转；跨边界子区间由左右前缀配对计数。下文的前缀异或恒等式和合并证明适用于出题人解法。
Codex（GPT-6）采用的实现只保存长度与一的数量，用长度推出零的数量，并在迭代查询中分别累计左、右摘要以保持拼接顺序。设位数为 \(B\) 、操作数为 \(q\) ，两者时间均为 \(O(nB+qB\log(n+1))\) ，空间为 \(O(nB)\) .收益是减少冗余字段、明确非交换合并次序，两种摘要使用同一前缀异或原理。
前缀异或¶
设初始值和所有赋值的非负整数上界为 \(U\) ，所需二进制位数为 \(B=\max\{1,\lceil\log_2(U+1)\rceil\}\) .所有前缀异或也只需这 \(B\) 位表示。
对一个查询区间，设局部前缀异或为 \(p_0=0,p_1,\ldots,p_k\) .子区间异或等于两个不同下标的前缀异或之异或，每对前缀唯一对应一个非空子区间。
对二进制位 \(b\) ，设这 \(k+1\) 个前缀中有 \(o_b\) 个为 \(1\) ，其余 \(k+1-o_b\) 个为 \(0\) .异或后该位为 \(1\) 的前缀对数为 \(o_b(k+1-o_b)\) ，因此答案为
可合并的区间信息¶
线段树节点维护区间长度 \(k\) 、整个区间的异或值 \(z\) ，以及每一位上非空前缀异或为 \(1\) 的数量 \(o_b\) .合并左区间 L 和右区间 R 时：
- 长度相加，整段异或为 \(z_L\oplus z_R\) .
- 左侧前缀不变。右侧每个非空前缀要先异或整个左区间；若 \(z_L\) 的第 \(b\) 位为 \(1\) ，右侧这一位的零和一交换。
所以合并后的一计数为
空前缀不在节点内重复保存；查询得到整段信息后，用公式中的 \(k+1-o_b\) 把它加入零计数。
正确性与实现¶
合并公式枚举了所有非空前缀：它们要么完全位于左区间，要么由整个左区间接上右侧非空前缀。因此节点信息正确。单点赋值更新叶节点并重新合并；查询按从左到右顺序合并所覆盖的节点，就能得到查询区间的准确前缀计数。前缀对公式随即给出每个子区间的异或值总和。
参考程序使用迭代线段树，查询有左右两个累积结果，分别按正确的拼接方向合并。该合并不满足交换律，不能随意改变顺序。
本题允许取到上界 \(U=65536=2^{16}\) ，因此参考程序维护 \(B=17\) 位。答案使用 64 位整数。
复杂度¶
每次合并需要遍历 \(B\) 个二进制位，耗时 \(O(B)\) .建树时间为 \(O(nB)\) ，每次单点赋值或区间查询的时间为 \(O(B\log n)\) ，空间复杂度为 \(O(nB)\) .