XOR Basis / Linear Basis Ladder¶
Use this lane when xor tasks stop being about one clever bit trick and start asking about the full space generated by the numbers.
Who This Is For¶
Use this ladder if:
- prefix xor basics already feel comfortable
- you can distinguish "xor with one partner" from "xor of any subset"
- you want one exact basis route before reopening harder graph or segment-based basis variants
This lane is intentionally focused:
- one exact starter
- one direct in-repo flagship rep
- strong compare points back into
Binary Trieand xor-heavy graph reductions
Warm-Up¶
- explain why dependent vectors add no new xor values to the span
- explain what "highest set bit pivot" means
- show why one number either enlarges the basis dimension by
1or by0
Target skill:
- see subset-xor tasks as linear independence over
GF(2)
Core¶
- greedy insertion by highest set bit
- representability test by elimination
- greedy maximum-subset-xor query
- exact flagship rep: XMAX - XOR Maximization
Target skill:
- build one compact xor span and answer the first canonical subset-xor questions from it
Stretch¶
- xor path with cycle-space reduction -> Codeforces 845G - Shortest Path Problem?
- rank/independence over prefix xors -> Codeforces 1101G - (Zero XOR Subset)-less
- only go there after plain max-subset-xor and representability feel routine
Target skill:
- distinguish the plain basis lane from graph, DP, or segment-level reductions that merely reuse the same algebraic object
Retrieval Layer¶
- exact quick sheet -> XOR Basis hot sheet
- exact starter -> xor-basis.cpp
- compare pair-xor route -> Binary Trie hot sheet
Exit Criteria¶
You are ready to move on when:
- you can explain why the basis has one pivot per highest set bit
- you know why representability reduces to the same elimination process as insertion
- you can state clearly when xor basis is right and when binary trie is the correct family instead