viii. Fast Set and Integer Structures

When keys are integers in $[0,n)$, word-level tricks beat comparison-based trees. The 64-ary bit tree (“fast set”) gives insert, erase, successor and predecessor in $O({\log }_{64}n)$, at most 4 levels for $n\le 2^{24}$, with $n/63$ words of memory. It’s typically 5-10x faster than std::set.

64-ary bit tree

struct FastSet {
    int n; vector<vector<ull>> s;                  // s[0] = elements, s[h] = non-empty words of level h-1
    FastSet(int n_) : n(n_) { int m = n; do { m = (m + 63) >> 6; s.emplace_back(m); } while (m > 1); }
    bool has(int x) const { return s[0][x >> 6] >> (x & 63) & 1; }
    void insert(int x) { for (auto& v : s) { v[x >> 6] |= 1ULL << (x & 63); x >>= 6; } }
    void erase(int x) { for (auto& v : s) { v[x >> 6] &= ~(1ULL << (x & 63)); if (v[x >> 6]) break; x >>= 6; } }
    int next(int x) const {                        // smallest element >= x, or -1
        if (x < 0) x = 0;
        if (x >= n) return -1;
        for (int h = 0; h < sz(s); h++) {
            if ((x >> 6) >= sz(s[h])) break;
            ull d = s[h][x >> 6] >> (x & 63);
            if (!d) { x = (x >> 6) + 1; continue; }
            x += __builtin_ctzll(d);
            for (int g = h - 1; g >= 0; g--) x = x << 6 | __builtin_ctzll(s[g][x]);
            return x;
        }
        return -1;
    }
    int prev(int x) const {                        // largest element <= x, or -1
        if (x >= n) x = n - 1;
        for (int h = 0; h < sz(s) && x >= 0; h++) {
            ull d = s[h][x >> 6] << (63 - (x & 63));
            if (!d) { x = (x >> 6) - 1; continue; }
            x -= __builtin_clzll(d);
            for (int g = h - 1; g >= 0; g--) x = x << 6 | (63 - __builtin_clzll(s[g][x]));
            return x;
        }
        return -1;
    }
};

Proof: the 64-ary bit tree is $O({\log }_{64}n)$ per operation, $O(n/64)$ memory

Level $0$ has $\lceil n/64\rceil$ words; level $h$ has $\lceil (\text{level }h-1\text{’s word count})/64\rceil$ words, so level $h$ has $O(n/64^{h+1})$ words, and the number of levels until this shrinks to $1$ is $O({\log }_{64}n)$. Total memory is ${\sum }_{h}O(n/64^{h+1})=O(n/64)\cdot {\sum }_{h}64^{-h}=O(n/64)$ (geometric series). insert/erase touch exactly one word per level (the ancestor-word chain of $x$), so both are $O({\log }_{64}n)$. next/prev climb at most one level up to find a non-empty word (each level up covers $64\times$ more ground, so within $O({\log }_{64}n)$ levels a set bit must exist if any element $\ge x$ exists at all, since the top level has $O(1)$ words covering the whole universe), then descend the same number of levels reading one word each — so both are $O({\log }_{64}n)$ as well. $■$

Uses: set of alive indices in simulations (“delete $x$, find nearest alive neighbours”), “next free slot”, Dijkstra or BFS with small integer keys (bucket queue over a fast set), sweep lines over compressed coordinates, Mo’s algorithm needing a successor structure with $O(1)$-ish updates.

For “$k$-th smallest” or counts you still need a Fenwick tree over the universe; the fast set only does membership, successor and predecessor.

Other integer structures

Structure	Operations	Notes
van Emde Boas	pred/succ/insert/delete in $O(\log \log U)$	recursion $T(U)=T(\sqrt{U})+O(1)$ (split each key into a high half and low half over $U=2^w$); memory $O(U)$ naively, $O(n)$ with hashing (a “y-fast trie”-style implementation); beats a balanced BST when $U$ is small — $U=2^{32}$ gives $\log \log U=5$ vs. $\log n\approx 20$. In practice a bitset with _Find_next is faster for small universes, and a hash set plus a BIT usually beats both in code length
x-fast / y-fast trie	pred/succ in $O(\log \log U)$	binary search over prefix lengths using hash tables of prefixes
fusion tree	pred in $O({\log }_{w}n)$	a $B$-tree with branching factor $w^{1/5}$; each node compares a key against $O(w^{1/5})$ stored keys in $O(1)$ via a “sketch and multiply” word trick, beating comparison-based bounds; combined with integer sorting gives $O(n\log n/\log \log n)$ sorting — theory, not contest code
bucket queue	monotone priority queue over small keys	Dial’s algorithm
radix heap	monotone priority queue, $O(\log C)$	Heaps
rank/select bit vector	$O(1)$ rank and select in $n+o(n)$ bits	basis of succinct structures below
tango / multi-splay tree	$O(\log \log n)$-competitive with the optimal offline BST for any access sequence	relevant to the open dynamic optimality conjecture (is a splay tree $O(1)$-competitive? open since 1985)
Brodal queue / hollow heap	$O(1)$ worst-case insert, meld, find-min, decrease-key; $O(\log n)$ delete-min	Brodal (1996) is the theoretical optimum for a meldable priority queue but enormously complicated; the hollow heap (2015) reaches the same amortized bounds far more simply
succinct structures (FM-index, succinct trees)	space close to the information-theoretic minimum, still fast queries	FM-index: a compressed full-text index, what DNA aligners use; succinct trees: $2n+o(n)$ bits with $O(1)$ navigation; genuinely used in bioinformatics and search engines where data doesn’t otherwise fit in memory

Proof: $T(U)=T(\sqrt{U})+O(1)$ solves to $T(U)=O(\log \log U)$

Substitute $U=2^{2^k}$, so $\sqrt{U}=2^{2^{k-1}}$ and the recurrence becomes $T(2^{2^k})=T(2^{2^{k-1}})+O(1)$. Writing $f(k)=T(2^{2^k})$, this is $f(k)=f(k-1)+O(1)$, which solves directly to $f(k)=O(k)$. Since $U=2^{2^k}$ gives $k={\log }_2{\log }_{2}U$, substituting back gives $T(U)=O(\log \log U)$. $■$

In contests the 64-ary bit tree covers what vEB would; the others are worth knowing by name.

Ideas that transfer

• Word-level parallelism: packing 64 booleans or 8 bytes into a word and operating on them at once is what bitsets, Shift-Or matching, bit-parallel LCS and the fast set all do (Bitset).
• Four Russians: precompute answers for all small blocks (size $\frac{1}{2}\log n$) and combine. That’s the trick behind $O(n)$-preprocessing RMQ (RMQ), $O(n^3/\log n)$ boolean matrix multiplication and some LCS speedups.
• Trading exactness for speed: soft heaps (constant-time operations, some keys corrupted) underpin Chazelle’s MST. Approximate counting and sketches (Count-Min, HyperLogLog) use bounded error to save memory.
• Retroactive structures support “insert an operation into the past” and see the effect on the present — partially retroactive (query only the present) or fully retroactive (query any point in time). Related to, but stronger than, persistence: persistence lets you read the past, retroactivity lets you change it.
• Dynamic optimality: whether splay trees are $O(1)$-competitive with every BST is open since 1985. Tango trees achieve $O(\log \log n)$-competitiveness.
• Rank/select and succinct structures (wavelet trees, $n\log \sigma$ bits, $O(\log \sigma )$ queries) buy space close to the information-theoretic minimum at a small query-time cost — see the table above.