Linear basis and Gaussian elimination are often intertwined concepts.

Concept

A linear basis is primarily used for finding subsets with maximal XOR sums in (O(\log V)), fundamentally representing a set of bases in high-dimensional vector spaces.

General Linear Basis

Constructing a binary linear basis is straightforward, mainly by verifying each number's suitability as a base element.

Insertion complexity is (O(\log V)), query complexity is (O(\log V)), without supporting modifications.

void addBase(long long num) {
    for (int bit = 60; bit >= 0; --bit) {
        if ((num >> bit) & 1LL) {
            if (!baseArray[bit]) {
                baseArray[bit] = num;
                return;
            } else {
                num ^= baseArray[bit];
            }
        }
    }
}

long long getMaxXor() {
    long long result = 0;
    for (int bit = 60; bit >= 0; --bit) {
        if (((result ^ baseArray[bit]) > result)) {
            result ^= baseArray[bit];
        }
    }
    return result;
}

Merging Bases

Supports unidirectional merging, not splitting, with a single operation copmlexity of (O(\log^2 V)).

Merge one basis into another by inserting all base elements from the first into the second.

basis combine(basis source, basis target) {
    basis merged = source;
    for (int idx = maxBits - 1; idx >= 0; --idx) {
        if (target.base[idx]) merged.addBase(target.base[idx]);
    }
    return merged;
}

Prefix Linear Basis

A common application involves computign the linear basis over an interval.

Example Problem: CF1100F Ivan and Burgers

Variation: P3292 [SCOI2016] Lucky Numbers

• Solution One: Utilize segment trees for intensive merging.
• Solution Two: Apply RMQ for intensive merging.
• Solution Three: Prefix Linear Basis.
• Solution Four: Use cat-trees for maintaining interval linear bases.

Greedy Problems Involving Linear Independence

Given vectors with associated costs, find the minimum-cost set forming a linearly independent basis.

Sort elements ascendingly to insert greedily for minimal cost, descendingly for maximum cost.

Example Problem: P4301 [CQOI2013] New Nim Game

Linear Algebra Perspective

Linear basis can be seen as specific cases within broader linear algebraic contexts.

For higher dimensions, consider Gaussian elimination to derive a linear basis.

Example Problem: P3265 [JLOI2015] Equipment Purchase

#include <cstdio>
#include <cmath>
#include <algorithm>

typedef double db;

const int maxItems = 505;
const db epsilon = 1e-4;

struct Item {
    int price;
    db attributes[maxItems];

    bool operator<(const Item& other) const { return price < other.price; }
} items[maxItems];

int itemCount, attrCount;
int selectedBases[maxItems];

int main() {
    scanf("%d%d", &itemCount, &attrCount);
    for (int i = 1; i <= itemCount; ++i)
        for (int j = 1; j <= attrCount; ++j)
            scanf("%lf", &items[i].attributes[j]);
    for (int i = 1; i <= itemCount; ++i) scanf("%d", &items[i].price);
    std::sort(items + 1, items + itemCount + 1);
    int chosen = 0, totalCost = 0;
    for (int i = 1; i <= itemCount; ++i) {
        for (int j = 1; j <= attrCount; ++j) {
            if (fabs(items[i].attributes[j]) > epsilon) {
                if (!selectedBases[j]) {
                    chosen++, totalCost += items[i].price;
                    selectedBases[j] = i;
                    break;
                }
                db factor = items[i].attributes[j] / items[selectedBases[j]].attributes[j];
                for (int k = j; k <= attrCount; ++k) 
                    items[i].attributes[k] -= items[selectedBases[j]].attributes[k] * factor;
            }
        }
    }
    printf("%d %d\n", chosen, totalCost);
    return 0;
}