A structure never has to store more than the raw input it's built from — but several entries on this site deliberately do, precomputing extra tables purely to make a later query cheaper or more tightly bounded. This page asks the question none of the site's other cross-cutting lenses asks directly: how much extra memory does that actually cost, in real numbers, and does the speed it buys pay that back? Online vs. Offline asks whether the queries are known in advance; Memoization vs. Tabulation asks it only inside one dynamic-programming recurrence. Here the question is general: pick a structure that trades memory for speed, measure the real trade on both sides, not just the Big-O shape of each.
Sparse Table's own Complexity section already
names the shape of the trade: O(n log n) space against Segment Tree's O(n), in exchange for
O(1) queries a mutable tree can't offer at any space budget, since it has to leave room
for update to invalidate exactly the nodes a change touches. Counting the real
reference implementations' own stored values — Sparse Table's log₂n rows, each
shorter than the last, against Segment Tree's one 2·size array — turns "more
memory" into an actual number, and it isn't a fixed constant:
| n | Sparse Table values stored | Segment Tree values stored | ratio |
|---|---|---|---|
| 1,024 | 9,228 (9.0× n) | 2,048 (2.0× n) | 4.5× |
| 131,072 | 2,097,171 (16.0× n) | 262,144 (2.0× n) | 8.0× |
| 1,048,576 | 19,922,966 (19.0× n) | 2,097,152 (2.0× n) | 9.5× |
| 16,777,216 | 385,875,994 (23.0× n) | 33,554,432 (2.0× n) | 11.5× |
(Sizes chosen as exact powers of two so Segment Tree's own array never pads past its tight
2n — off a power-of-two boundary its array can run to nearly 4n, per that
page's own Complexity section, which would blur the comparison with Segment Tree's own internal
waste rather than Sparse Table's.) The ratio keeps climbing because Sparse Table's row count grows
with log₂n while Segment Tree's stays a flat 2× — by sixteen
million keys, Sparse Table is storing over eleven times as many numbers for the same input.
That memory isn't free in build time either: Sparse Table's own
measured comparison found the break-even point — the query count needed before the faster
O(1) lookups actually pay back the slower, larger build — lands at roughly
1.5×–4× the array's own size in queries, growing wider as n
grows, not narrower. Both halves of this trade get more expensive at scale, not just one.
Bit Vector Rank/Select's own
reference implementation precomputes a block/superblock decomposition specifically so
rank1(i) never has to scan — that page's own Space section already asserts the
overhead is o(n) bits for the right choice of block size, but names no actual number.
Instrumenting that exact shipped buildRankSelect function (unmodified) against a
plain linear scan that counts set bits one at a time, at the same block/superblock sizing that
page's own Space section names (block size b ≈ log₂(n)/2, superblock size
S ≈ (log₂n)²) gives a real number, and a real trend:
| n | block size, blocks/superblock | extra words stored | as % of n | rank1 array reads: precomputed vs. naive scan |
|---|---|---|---|---|
| 1,000 | b=5, 20 | 883 | 88.3% | 3 vs. 730 |
| 100,000 | b=8, 35 | 41,187 | 41.2% | 3 vs. 73,000 |
| 1,000,000 | b=10, 40 | 318,885 | 31.9% | 3 vs. 730,000 |
| 10,000,000 | b=12, 45 | 2,596,346 | 26.0% | 3 vs. 7,300,000 |
Correctness checked first, not assumed: the precomputed rank1 matched an
independent naive scan on every one of several hundred random query points at each size above,
zero mismatches, before trusting any of these counts. rank1's own array-access count
never moves — exactly 3 lookups (superRank, blockRankInSuper,
one pattern-table row), at any n and any query position i — while a naive
scan's cost grows with i directly, up to n at the array's far end. The
overhead really is shrinking relative to n as the page's Space section claims
(o(n), not a fixed fraction) — 88% of n at a thousand bits, down to 26%
by ten million — but it's a real, nonzero memory bill the whole way, not a rounding error, and it
shrinks slowly: cutting it in half again would take roughly another hundred-fold increase in
n at this growth rate.
Pick a size and this recomputes the exact same closed-form word count as the table above —
2b·(b+1) + b·2b-1 for the shared pattern tables
plus 3·⌈n/b⌉ for the per-block arrays plus ⌈⌈n/b⌉/(S/b)⌉+1 for
superRank — verified above to match the real shipped structure's own counts exactly,
not an estimate.
O(m) failure-function table
buys an unconditional O(n+m) search bound — that page's own Complexity section names
naive search's alternative directly: no precomputed table at all, but it "can redo up to
m comparisons at every single one of the n starting positions" in the
worst case, O(nm). A few extra pointers' worth of memory closes off an entire class
of pathological input.O(n log n) ancestor table turns a k-th-ancestor or LCA query
into O(log n) jumps instead of walking parent pointers one hop at a time
(O(n) worst case, zero extra memory beyond the tree itself). Online vs. Offline already covers this exact pair from
a different angle — whether the queries are known in advance — named here only because it's also
a clean instance of paying memory for a bound, not because this page re-measures it.The extra memory has to be built before it pays anything back, and that build has a real
cost too — not just a one-time footprint. Sparse Table's own measured comparison above
shows the build gap widening with n exactly as the query-time saving stays roughly
fixed in nanoseconds — "spend memory, get speed" is really "spend memory and build time,
get speed back gradually, one query at a time." A workload that builds the structure once and
queries it only a handful of times never clears that bar, no matter how large the per-query saving
looks in isolation.
"Smaller than a fixed multiple of n" and "small" are different claims. Bit
Vector Rank/Select's o(n) bound is real and measured above, but at a thousand bits the
overhead is still 88% of the raw data it indexes — nowhere near negligible at that size. The
asymptotic claim only becomes a practical win once n is large enough for the shrinking
trend to have actually shrunk; reading an asymptotic space bound as "cheap at any size" skips
exactly the part a real measurement would catch.
The right block/superblock size isn't a free constant choice. Bit Vector
Rank/Select's own Complexity section is explicit that the o(n) bound "only holds for
the right choice of block size b and superblock size S, not any fixed
constant" — the table above recomputes b and S at every n
for exactly that reason, rather than reusing one pair of numbers across every row, which would have
quietly misrepresented the trend at the extremes.