← all categories

Xor Basis Time 0c934f7f

XOR linear basis over GF(2), BIT bits wide, tagged with insertion time. On insert, the basis always keeps the newest vector at each pivot bit (displacing an older one further down), so queryMax/checkFrom can restrict to a suffix of insertions (time >= minTime) — the standard trick for "max/any XOR achievable using only elements inserted after time T" without rebuilding the basis per query. Distinct from xor-basis.h (no time dimension, ~40% shorter — use that one if you don't need suffix-of-insertions queries).

Time: O(BIT) per operation. tested

content/math/xor-basis-time.h

template <int BIT>
struct XorBasisTime {
    struct Entry { bitset<BIT> vec; int time = -1; };
    array<Entry, BIT> b{};

    void add(bitset<BIT> x, int t) {
        for (int i = BIT - 1; i >= 0; i--) {
            if (!x.test(i)) continue;
            if (b[i].time == -1) { b[i] = {x, t}; return; }
            if (t > b[i].time) { swap(x, b[i].vec); swap(t, b[i].time); }
            x ^= b[i].vec;
        }
    }

    // max XOR achievable using only vectors with time >= minTime
    bitset<BIT> queryMax(int minTime) {
        bitset<BIT> res;
        for (int i = BIT - 1; i >= 0; i--)
            if (b[i].time >= minTime && !res.test(i)) res ^= b[i].vec;
        return res;
    }

    // is x representable using only vectors with time >= minTime
    bool checkFrom(bitset<BIT> x, int minTime) {
        for (int i = BIT - 1; i >= 0; i--) {
            if (!x.test(i)) continue;
            if (b[i].time < minTime) return false;
            x ^= b[i].vec;
        }
        return x.none();
    }
};