每日算法 — 使用java实现线性基：异或线性基与最大异或子集

算法概述

线性基（Linear Basis）是线性代数中基的概念在异或运算下的推广，它将一组数表示为一组线性无关的基向量，使得原集合中任意数的异或组合都能由这组基线性表出。线性基是解决最大异或子集、第k大异或值、异或方程组等问题的核心数据结构，单次插入和查询时间复杂度均为O(log MAX)。本文用Java实现高斯消元式线性基，并展示其在经典问题中的应用。

核心原理

将每个整数视为二进制向量，异或运算对应向量空间的加法。线性基的构建过程类似于高斯消元：对于每个数，从最高位到最低位尝试消元，若当前位已存在基向量则进行异或消去，否则将该数作为新的基向量。最终得到的基具有上三角形式——每个基向量有唯一的最高位1。

完整Java实现

import java.util.*;

public class LinearBasis {
    // 假设数值范围在60位以内（适合long类型）
    private long[] basis; // basis[i]表示最高位1在第i位的基向量
    private int size;     // 基的大小（线性无关向量个数）
    private final int MAX_BITS = 60;

    public LinearBasis() {
        basis = new long[MAX_BITS];
        size = 0;
    }

    /**
     * 向线性基中插入一个数
     * 时间复杂度：O(log MAX)
     */
    public void insert(long x) {
        for (int i = MAX_BITS - 1; i >= 0; i--) {
            if ((x >> i & 1) == 0) continue;
            if (basis[i] == 0) {
                basis[i] = x;
                size++;
                // 用新基向量消去其他基向量在当前位的1，保持上三角形式
                for (int j = 0; j < i; j++) {
                    if ((basis[j] >> i & 1) == 1) basis[j] ^= x;
                }
                for (int j = i + 1; j < MAX_BITS; j++) {
                    if ((basis[j] >> i & 1) == 1) basis[j] ^= x;
                }
                return;
            }
            x ^= basis[i];
        }
        // x被消为0，说明线性相关，无需插入
    }

    /**
     * 从数组批量构建线性基
     */
    public static LinearBasis fromArray(long[] arr) {
        LinearBasis lb = new LinearBasis();
        for (long x : arr) lb.insert(x);
        return lb;
    }

    /**
     * 查询集合中能获得的最大异或值
     * 贪心策略：从高到低，能异或出更大值就异或
     */
    public long maxXor() {
        long res = 0;
        for (int i = MAX_BITS - 1; i >= 0; i--) {
            if ((res ^ basis[i]) > res) {
                res ^= basis[i];
            }
        }
        return res;
    }

    /**
     * 查询集合中能获得的最小异或值（非零）
     * 线性基中最小的基向量即为答案
     */
    public long minNonZeroXor() {
        for (int i = 0; i < MAX_BITS; i++) {
            if (basis[i] != 0) return basis[i];
        }
        return Long.MAX_VALUE; // 无有效基
    }

    /**
     * 查询第k小的异或值（包含0）
     * 需先对基进行标准化处理（本insert已实现）
     */
    public long kthXor(long k) {
        // 收集所有非零基向量
        List<Long> vec = new ArrayList<>();
        for (int i = 0; i < MAX_BITS; i++) {
            if (basis[i] != 0) vec.add(basis[i]);
        }
        // 若基向量个数为n，则总共有2^n个不同的异或值（包含0）
        // 标准化后，第k小的异或值 = 将k的二进制表示映射到基向量组合
        if (k >= (1L << vec.size())) return -1; // k超出范围
        long res = 0;
        for (int i = 0; i < vec.size(); i++) {
            if ((k >> i & 1) == 1) res ^= vec.get(i);
        }
        return res;
    }

    /**
     * 判断一个数是否能被基线性表出
     */
    public boolean contains(long x) {
        for (int i = MAX_BITS - 1; i >= 0; i--) {
            if ((x >> i & 1) == 0) continue;
            if (basis[i] == 0) return false;
            x ^= basis[i];
        }
        return true; // x被消为0，说明可被表出
    }

    /**
     * 合并两个线性基
     */
    public LinearBasis merge(LinearBasis other) {
        LinearBasis res = new LinearBasis();
        for (int i = 0; i < MAX_BITS; i++) {
            if (this.basis[i] != 0) res.insert(this.basis[i]);
            if (other.basis[i] != 0) res.insert(other.basis[i]);
        }
        return res;
    }

    public int size() { return size; }

    public static void main(String[] args) {
        long[] arr = {12, 1, 32, 43, 52, 7, 19};
        LinearBasis lb = LinearBasis.fromArray(arr);

        System.out.println("线性基大小: " + lb.size());
        System.out.println("最大异或子集值: " + lb.maxXor());
        System.out.println("最小非零异或值: " + lb.minNonZeroXor());
        System.out.println("是否能表出43: " + lb.contains(43));
        System.out.println("是否能表出100: " + lb.contains(100));
        System.out.println("第5小异或值: " + lb.kthXor(5));
    }
}

经典问题应用

最大异或路径

给定一棵带权树，求从根到任意节点的路径异或值的最大值。解法：DFS求出根到每个节点的路径异或前缀，将所有前缀值插入线性基，查询最大异或值即可。

public class MaxXorPath {
    static List<long[]>[] tree; // [neighbor, weight]
    static LinearBasis lb = new LinearBasis();

    static void dfs(int u, int parent, long xorVal) {
        lb.insert(xorVal);
        for (long[] e : tree[u]) {
            int v = (int) e[0];
            long w = e[1];
            if (v == parent) continue;
            dfs(v, u, xorVal ^ w);
        }
    }
}

复杂度分析

其中MAX为数值范围（通常取60对应long类型）。线性基的空间固定为O(log MAX)，与元素个数无关，是处理大规模异或问题的利器。

应用场景

• 最大异或子集：从数组中选取子集使异或和最大
• 异或方程组求解：判断方程组是否有解及求通解
• 树路径异或最值：树上根到节点路径的最大/第k大异或值
• 区间异或查询：线段树每个节点维护线性基，支持区间最大异或
• 高斯消元替代：在GF(2)域上的线性代数运算