Skip to content

Data Structures -> Binary Trie / XOR Queries

Fixed-width bit-prefix trie for live insert / erase / maximum-xor queries against one multiset of non-negative integers.

  • Topic slug: data-structures/binary-trie-xor
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 5
  • Curated external problems: 3

Microtopics

  • binary-trie
  • xor-queries
  • fixed-bit-width
  • subtree-counts
  • max-xor-greedy
  • prefix-xor-insertions

Learning Sources

Source Type
OI Wiki Trie Reference
USACO Guide Trie Reference
Competitive Programmer's Handbook Reference

Practice Sources

Source Type
Codeforces problemset Practice
CSES Maximum Xor Subarray Practice
SPOJ SUBXOR Practice

Repo Companion Material

Material Type
Binary Trie hot sheet quick reference
Binary Trie starter route starter route
Vasiliy's Multiset note anchor note
Trie tutorial compare point
Prefix Sums tutorial adjacent tutorial

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Vasiliy's Multiset Codeforces Medium Binary Trie, XOR Queries Data-Structure-Heavy; Bitwise Bitwise Prefix Walk; Subtree Counts; Dynamic Multiset Dynamic-Multiset; Maximum-XOR The cleanest first dynamic benchmark where insert, erase-one, and maximum-xor queries are the whole problem.

Stretch

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
SUBXOR SPOJ Hard Binary Trie, Counting Variant, Classic Bitwise; Classic Prefix XOR; Bitwise Counting Prefix-XOR; Counting A classic stretch problem showing that the same family extends beyond maximum-xor queries into richer counting variants.

Bridge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Maximum Xor Subarray CSES Hard Bitwise Operations, Prefix XOR, Binary Trie Bitwise; Array Transformation Maximum XOR Query Maximum-XOR The canonical bridge from one dynamic xor set to prefix-xor scans over an array.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
VASILIYSMULTISET Vasiliy's Multiset primary medium - Note Code

Regeneration

python3 scripts/generate_problem_catalog.py