线性基
369Pai
·
·
个人记录
- 数学
- 线性基
- 性质
- 操作 & 应用
- 动态插入
- 合并
- 撤销、可持久化
- 求线性基的秩
- 子集 k 大异或和
- 带删除线性基
- 线性基求交
- 静态区间线性基 - 猫树
线性空间 - OI-Wiki
（前置知识）
线性基 - OI-Wiki
（定义，性质）
线性基学习笔记 - Menci
（定义，构造与特殊性质，应用）
线性基小记
（例题，带删除线性基）
[UOJ91] [集训队互测2015] 最大异或和 - JCY-std（带删除线性基-离线）
UOJ91 最大异或和 - yhx12243（带删除线性基-在线）
线性基求交详解 - yyyyxh（线性基求交）
浅谈「正交线性基」- Sooke
线性基练习题 - pigstd
线性基的一个小误区
当 V \le 2^{64} 时，赋值、异或时间复杂度为 O(1)，线性基插入是 O(\log V) 的；
当 V > 2^{64} 时，要用 bitset 存储，此时异或时间复杂度为 O(\frac{\log V}{w}) ，插入为 O(\frac{\log^2 V}{w})。
合并操作同理。
撤销，可持久化
如果空间为 O(\log V)，那么可以直接复制。
带删除线性基
离线
套用线段树分治 O(\mathrm{insert(V)}\log n)。
记录删除时间 O(\mathrm{insert(V)})。
在线
线段树+线性基合并 O(\mathrm{merge(V)} \log n)；
维护表示方法 O(\mathrm{insert(V)} n)。
线性基求交
给定两个线性基 B_1,B_2，设其张成空间分别为 V_1,V_2。求 V_1 \cap V_2 的一组基。
令 W = V_1 \cap B_2，则 \operatorname{span}(W) \subseteq V_1 \cap V_2（由线性空间封闭性和线性基定义得到）。
考虑什么时候 W 是 V_1 \cap V_2 的一组基，给出一个结论：当 B_1 \cup (B_2/W) 线性无关时，W 是 V_1 \cap V_2 的一组基。
考虑反证：假设 \exist v \in V_1 \cap V_2 \wedge v \notin \operatorname{span}(W)。由于 v \in V_1 \cap V_2，B_2 可以表出 v，但需要用到 (B_2/W) 中的元素，设其异或和为 t，则 v\oplus t \in \operatorname{span}(W)，所以 v\oplus t\in V_1，即 v\oplus t，能被 B_1 表出。
而 v 又能仅用 B_1 表出，则 v 存在两种表出方式，与 B_1 \cup (B_2/W) 线性无关矛盾。
实现方法参考文章。