异或线性基

· · 算法·理论

异或线性基

定义与基本操作

序列 a_{1\dots n} 的异或线性基（下文简称线性基）是一个数集 S，满足 a 中任何一个数都可以由 S 的一个子集（可空）异或得到，且 |S| 最小，线性基 p_{0\dots T} 满足 p_i=0 或 p_i 的二进制最高位为 i，其中 T=\lfloor\log{V}\rfloor。定义可重集 A 异或得到数集为 v_A。

换而言之，在 T 维空间中，每一位取 0/1，则 [0,2^T-1] 内数和 T 维 01 向量一一对应，此处定义向量集 \vec v_{1\dots k} 和向量 \vec v 线性相关当且仅当前者存在子集，其对应数的异或和为 \vec v 对应的数，该意义下 S 为空间 a_{1\dots n} 的基。

性质1: 不存在 S 的非空子集异或为 0（换而言之，a_{1\dots n} 取子集能异或出的数的个数即为 2^{|A|}）。

存在则其中存在一个元素无需加入。

插入

在当前基 A=\{p_0,\dots,p_T\} 的基础上插入一个数 x，从高位到低位，对于当前位 i 满足当前 x 该位为 1，若 p_i=0，则 p_i:=x，否则 x:=x\oplus p_i，使最终 x 赋给的 p_j 最高位为 j。若处理完所有位后 x 没有赋给任何 p_i，称本次插入失败，

性质2: v_{\{a_1,\dots,a_n\}}=v_A。

归纳证明，设插入 a_{1\dots i} 时 v_{\{a_1,\dots,a_i\}}=A，证明插入 a_{i+1} 后同样满足。

若 a_{i+1} 插入失败，说明存在 \{a_1,\dots,a_i\} 一个子集异或为 a_{i+1}，无需改变 A。否则，设 a_{i+1} 在异或 p_{b_1},p_{b_2},\dots,p_{b_{m-1}} 后最终赋给 p_{b_m}，则 a_{i+1}\oplus p_{b_{1\dots m-1}}=p_{b_m}，故 p_{b_{1}}\oplus p_{b_2}\oplus\dots\oplus p_{b_m}=a_i。

性质3: |A| 唯一且最小。

相当于改变顺序后 |A| 不变。

对于序列 a_{1\dots n}，若其每一位都成功插入，改变顺序必定可以。

否则，存在 a_i 不能插入，故对于插入 x 之前的 A，有 p_{b_1}\oplus\dots\oplus p_{b_m}=a_i。由性质 2，a_{1\dots i-1} 此处可以等效为 p_{0\dots T}，插入之前位相当于对 p_{0\dots T} 依次插入，只需证改变插入顺序为 p_{b_1},\dots ,p_{b_{j}},a_i,p_{b_{j+1}},\dots,p_{b_m} 后 p_{b_m} 插入失败，显然。

求 \max/\min\{v_A\}

以 \max 为例，从高到低位，对于当前位 i，若 ans 这一位为 0 且 p_i\neq 0，ans:=ans\oplus p_i。

这样的原因是，原序列异或出的数集和 p_{0\dots T} 的相同，只需要在 p 中考虑。你从高到低看异或值第 i 位在 i+1\dots T 位取最大情况下能否为 1，i+1\dots T 这些位由 p_{i+1\dots T} 决定，这些位取最大即为 ans。

求 \min 时需要注意特判结果为 0，即记录是否有数插入失败。

求 \operatorname{kthmin}\{v_A\}

你想要的是情况是无论 p_{i+1\dots T} 是否选，选了 p_i 的异或和均大于不选的情况。于是你将 p_i 定义改为 v_A 中最高位为 i 的最小数，可以 O(\log^2V)-O(\log V)。

线性基求交

有两个基 A,B，求基 C 满足 v_C=v_A\cap v_B。

结论: 对于基 C=B\cap v_A，若满足 v_{B-C}\cap v_A=\{0\}，则 v_C=v_A\cap v_B。

Proof:

若 \exist x\notin v_{C},x\in v_A\cap v_B，由 x\in v_B，必有 p_1\oplus\dots\oplus p_n\oplus q_1\oplus\dots\oplus q_m=x，其中 p_i\in C,q_i\in B-C。设 s=\oplus_{i=1}^np_i,t=\oplus_{j=1}^mq_i，则 s\in v_C\subseteq v_A,t\in v_{B-C}。

又 x\in v_A，t=s\oplus x\in v_A。故 t\in v_A\cap v_{B-C}=\{0\}，x=s\in v_C，矛盾。

若 \exist x\notin v_A\cap v_B,x\in v_C，由 x\in v_C，有 x=p_1\oplus\dots\oplus p_m，其中 p_i\in C 即 p_i\in B 且 p_i\in v_A，两者分别说明 x\in v_A 和 x\in v_B，矛盾。

考虑如何找到这样的 C（因为用 B 直接求未必合法，需要用 B 的某个等效线性基）。

设 A,B 中数分别为 a_{0,\dots,M} 和 b_{0,\dots,M}，对每个 b_i，若其可以表示为 b_{0,\dots,i-1} 和 a_{0,\dots,M} 子集异或和，取其中 a_{0,\dots,M} 贡献的部分加入 C，最终所得即为所求 C，证明易。

前缀线性基

静态询问区间内选子集异或最大值。

离线按 r 升序，维护线性基，设 lst_i 为给 p_i 赋值的 a 下标，则 lst_i\ge l 的 p_i 一定可以给当前询问贡献。但不同插入顺序可能导致 lst 不同，你想要对每个 i 在保证 lst_{i+1,\dots, M} 最大的前提下使 lst_i 最大，考虑插入时记录插入数 x 的编号 id，若 x 的 i 位为 1，b_i\neq 0 且 lst_i<id，则将 (lst_i,id),(p_i,x) 两对分别交换后继续插入。

带撤销线性基

和前者类似，每个已经插入的元素有一个删除时间，支持查询某个时刻信息，遂对线性基每一位记录为其赋值的元素的删除时间，记作 lst_i，想在 lst_{i+1,\dots,M} 最大前提下使 lst_i 尽量大，后面的做法和前者相同。

应用

求异或出 x 的子集个数:

设插入失败的个数为 p，判断能否异或出 x，若能则所求为 2^p，即在任一个异或和为 x 的集合的基础上加入若干异或和为 0 的子集（某个元素原先已经加入则删除之）。

无向图路径边权异或和相关问题:

任取原图一棵生成树，处理 d_u 为 u 到树根这条链上所有边权异或和，将所有返祖边形成的环的异或和加入到线性基 A 中，则 u,v 之间所有路径异或和的集合为 \{x\oplus d_u\oplus d_v|x\in v_A\}。

树上路径部分边权/点权异或和相关问题:

线性基可以快速合并，对每个点倍增维护 O(\log n) 个线性基，复杂度 O((n+q)\log^3n)，可以处理不带修的。

带修则分析性质，如 P5556 中点有点权，支持路径点权 \oplus x 和查询路径上是否可以取一部分点点权异或为 0，你发现 ^1 大小 >\lfloor \log V\rfloor 的集合必定有一个子集异或和为 0（每次给一位赋值），只需处理路径长度极小情况。

区间修改/选数异或问题:

考虑数据结构套线性基，如线段树套线性基，树上每个点维护一个线性基，可以 O(q\log n\log^2V) 维护单点修改（注意线性基合并 O(\log^2V)）。对于区间异或，考虑转化到异或差分数组上单点修改，此时 [l,r] 的基即为 [l+1,r] 这段差分和 a_l 的基。

参考资料

【学习笔记】浅谈异或线性基——RP_INT_MAX

神秘算法 —— 线性基求交——Charlie-Vinnie