The shape a range question is about

The cost that is the size of the answer ended on a number and an apology. The number was thirty-one: the output-sensitive document listing beats a scan only above about thirty-one occurrences per document, because each of its ten or eleven range-minimum queries costs two hundred and fifty node visits inside a segment tree. The apology was that the segment tree is not the structure the method is published with, and that the published one — a range minimum in 2n + o(n) bits answering in constant time — was named there and not built.

This is the first of four essays that build it. It starts where every account of the structure starts, and where the interesting part already is: a range minimum is not a question about numbers.

The tree the array already is #

Take an array. Its leftmost smallest value is the root. Everything to the left of that value forms one subtree, built the same way; everything to the right forms the other. That is the Cartesian tree, and it is determined by the array — there is no choice to make and nothing to tune.

Two properties fall out of the construction and between them they are the whole idea.

The tree is a heap by value: every node’s value is at most its children’s, because a node became a root exactly by being the smallest thing in its own range. And it is a search tree by position: an in-order walk visits the positions in order, because the left subtree is what lay to the left.

Put those together and the minimum of a range is the deepest node that has both endpoints beneath it. Any node covering both endpoints covers everything between them, and among such nodes the deepest is the one whose range is tightest — which is the lowest common ancestor of the two positions.

That is the reduction, and it is worth being precise about what it accomplishes. Before it, answering a range minimum means comparing values. After it, the values are gone: the answer is a position, and it is read off the tree’s shape.

Why losing the values is the point #

A shape is cheaper than a list of numbers, and cheaper by a large factor.

An array of n values, each in its own range, needs n⌈log₂ n⌉ bits to write down — and the segment tree the listing was measured with needs twice that, because it stores an interior node’s minimum beside every leaf. At sixty-five thousand values that is a little over two million bits.

A tree of n nodes needs 2n bits. Not 2n times a logarithm: 2n. One bit per parenthesis, and a tree with n nodes has n opening and n closing parentheses.

The factor between those is the logarithm, and at the sizes a document collection reaches it is a factor of seventeen. That is the promise, and the three essays after this one are about how much of it survives contact with the requirement that the structure also answer questions. The short version is: about a third of it. The long version is more interesting than that, because what eats the rest is not the range-minimum machinery at all.

The stack that builds it #

The construction is one left-to-right pass over the array with a stack, and it is worth writing out because the parenthesis sequence falls out of it for free.

Hold a stack of positions. For each new position, pop every position on top whose value is strictly larger, and let the last one popped become the new position’s left child. If the stack is not empty after the popping, the position now on top becomes the new position’s parent. Push the new position.

The stack holds what is called the right spine: the positions whose values nothing to their right has yet undercut. Reading it from bottom to top gives a non-decreasing run of values, which is exactly the sequence of prefix minima ending at the current position.

Every position is pushed once and popped at most once, so the total work is linear however the values are ordered — the same amortised argument what amortised means makes about a dynamic array’s copies, and measured the same way rather than quoted.

The tree’s height is not bounded — an array sorted ascending gives a path of n nodes, which is the tree that is a list with a different cause — and nothing here depends on it being small. That is worth saying plainly, because every structure in this collection built on a balanced tree pays for the balancing, and this one does not have to: the query rule below never walks the tree.

Ties, and why they matter here #

The popping condition is strictly larger. That one word decides which of several equal minima the tree’s root is, and it has to agree with whatever the caller expects.

The document listing tests whether a row’s previous-occurrence entry falls outside the range, and it walks left and right of the reported position. If two rows tie, reporting the right-hand one rather than the left produces a different — still correct — recursion, but a different count of queries. Two structures that answer “a minimum” rather than “the leftmost minimum” will disagree on a tie and agree everywhere else, which is the kind of difference that shows up as an intermittent count and not as a wrong answer.

So the convention here is the leftmost minimum, matched to the segment tree the listing already used, and checked: every range of every array in a sweep of forty random arrays is answered by both structures and the two positions are required to be equal, not merely equally small.

The sequence, and the one property that is not obvious #

Emit an opening parenthesis at every push and a closing one at every pop. The result is a balanced sequence of 2n parentheses, and it is the tree: a node’s pair encloses exactly the pairs of its descendants.

Here is the property the next three essays live on. The pushes happen in index order, so the k-th opening parenthesis belongs to position k. That is not true of the encoding everybody writes first.

The obvious way to write a tree down is to walk it — visit a node, recurse into its children, come back — and emit a parenthesis at each step. That is an Euler tour, and its openings come out in preorder, which is the order the values put the positions in. Getting from position 7 to its parenthesis then needs a table saying where it is, and that table is n entries of ⌈log₂ 2n⌉ bits.

Written in index order the table is not needed: position 7’s opening is the seventh one, and finding the seventh one is a select, which select is not rank backwards prices at a small fraction of the vector it supports. The whole difference between a structure that is genuinely 2n + o(n) and one that is 2n plus half a segment tree is which order the parentheses were written in.

The excess, and why it is a walk #

The number of parentheses open at each point is the sequence’s excess. It starts at zero, ends at zero, never goes negative, and moves by exactly one at every step — up for an opening, down for a closing.

That last property is what makes the structure possible at all, and the table that fits inside a block is entirely about it. A sequence whose steps are ±1 has only 2^b possible shapes per block of b positions, and a small integer identifies which shape a block has, so every question about a block can be answered by a table computed once.

The rule the figure draws is one line: the minimum of a range is the opening at the rightmost lowest point of the excess between the two endpoints’ openings, and its index is the number of openings before it.

The reason is the stack again. An opening still unclosed at a point is a position still on the stack — an ancestor — and an opening is unclosed exactly when the excess never comes back down to its own value. The outermost such opening inside the range is therefore where the excess was last at its minimum. There is nothing more to it, and it took three attempts to get right.

The rule that nearly shipped #

The first two rules tried were the leftmost lowest point, in two variations. Both are wrong on two ranges in five, and the way they are wrong is the reason this essay says the rule was checked before it was believed.

They do not return nonsense. They do not return a position outside the range — not once in four thousand two hundred ranges. They return a position inside the range that is simply not the smallest one there. A caller receives an index it can use, holding a value it can read, and every downstream test that asks whether the answer is well formed passes.

The check that catches it is exhaustive: every range of every array, against a minimum found by looking at each element. That is quadratic in the array’s length and trivial at the length used, which is the right trade for a rule that everything else is built on. Forty arrays of twenty-four values is a hundred and fifteen thousand ranges, and a rule wrong on two in five fails on the first array.

This is the shape the pruning that loses an occurrence records for a different structure: a defect that produces plausible output is caught by comparison against something that does not share its mistake, and by nothing else.

What this buys, and what it does not #

The reduction is complete: a range minimum over n values is a lowest common ancestor in a tree of n nodes, the tree is 2n bits, and there is a rule for reading the answer out of those bits.

None of that yet answers a query. A rule that says “find the rightmost lowest point of the excess between here and there” has replaced one range-minimum problem with another — over a sequence with a very particular structure, but a range minimum all the same. What has been gained is that the new problem’s input is ±1, which is the property the table that fits inside a block turns into a lookup.

And the 2n bits are the payload, not the size. Two bits a value, and what undoes them is about everything else the structure has to hold, which at sixty-five thousand values comes to five times the payload — and about the encoding choice above, which is worth more than every other decision in the structure put together.

Where the factor of seventeen goes, and why the sixth that survives is a constant #

“About a third of it survives” is the summary this essay gives of the promise, and the arithmetic behind it is worth having now rather than three essays later, because it says which term is worth attacking.

The promise is a ratio of widths per value: $2\lceil\log_2 n\rceil$ bits for the segment tree against 2 for the parentheses, which is $\lceil\log_2 n\rceil$ — seventeen at sixty-five thousand values. What the structure delivers is 2 bits of payload plus about 9.5 bits of machinery per value, measured: 131,072 bits of parentheses against 651,800 of overhead at 65,536 values, and the same ratio at twice the size.

So the achieved ratio is

$$\frac{2\lceil\log_2 n\rceil}{2 + c}, \qquad c \approx 9.5,$$

which is 3.19 at a hundred and thirty thousand values — the measured figure — against a promise of seventeen. The promise is divided by $(2+c)/2 \approx 5.75$, and that divisor is a constant in $n$ while the promise is a logarithm, so two things follow that pull in opposite directions.

The fraction of the promise delivered is fixed at about a sixth, at every size. There is no size at which the structure grows into its own advertisement.

And the achieved ratio still grows, slowly, because the numerator does: 3.19 at $2^{17}$, about 3.5 at $2^{20}$, about 5 at $2^{30}$. The structure gets relatively better as the array grows, at one bit per doubling against a fixed eleven and a half — which is a real improvement and a much slower one than $2n + o(n)$ suggests to a reader who takes the second term at its word.

The same expression says where the crossing is, and it is early: the succinct structure is smaller than the segment tree once $2\lceil\log_2 n\rceil > 11.5$, which is $n > 64$. So the choice is never close at any size worth building, and the interesting question is not whether to use it but what the 9.5 is made of.

Which is where the strand’s real target is. The payload cannot be improved: a binary tree of $n$ nodes needs $2n - \Theta(\log n)$ bits to distinguish it from every other one, so the parentheses are already at their information-theoretic floor and the only thing a cleverer encoding could recover is a logarithm. Every remaining bit is machinery, machinery is 82% of the structure, and halving it would move the ratio from 3.19 to 5.1 — a larger improvement than four doublings of $n$ deliver for free.

That is the same accounting a bit for every bit makes about a rank directory, arriving here with the proportions inverted: there the directory is a fifth of the structure and the payload the rest, and here the payload is a sixth and the directory-shaped part is everything else. Two bits a value, and what undoes them is where the 9.5 is opened up, and the reason it is a whole essay is that no part of it is the range-minimum rule.

What is checked #

The tree, the sequence and the rule each carry an assertion, and each has a way of failing that was made to happen before it was trusted.

The sequence is required to be balanced, to be exactly 2n parentheses, and to have its k-th opening at position k. The excess is required to move by exactly ±1 at every step, to end at zero and never to go below it — a sequence that fails any of those is not a tree, and the block machinery would answer questions about it anyway.

The rule is required to agree with exhaustive search on every range of every array in the sweep, and with the segment tree on four hundred random ranges of a three-thousand-element array. The leftmost variant is kept in the checks as a case that must be rejected, reporting how often it is wrong and how often its answer sits inside the range regardless: 39.9% and always.

The array this is all for #

The array in question is not an arbitrary one, and it is worth naming because every size in the next three essays is a size on it.

A collection of documents is indexed by a suffix array, and beside it sits the chain of previous occurrences: for each row, the largest earlier row belonging to the same document, or −1 if there is none. A list of documents is not a list of occurrences is the essay that builds it and explains why it answers the question: inside a range of rows, the rows whose chain entry falls outside the range are exactly the first rows of their documents.

So the array is n entries, each an earlier row number or −1, and the queries against it are ranges of the suffix array. It has no structure worth exploiting — a random-looking sequence of row numbers — and every measurement here is taken on one of that shape rather than on something contrived to be easy.

Three numbers to carry forward #

The tree is what the next three essays are about, and each of them turns on one number that this one has already made available.

Two bits a value. The parenthesis sequence is exactly 2n bits, against the segment tree’s 2n⌈log₂ n⌉. That is the promise, and two bits a value, and what undoes them measures how much of it survives.

A constant number of lookups. The query rule touches the excess in a fixed number of places once the block machinery exists, against a descent that costs two logarithms — which is what the table that fits inside a block builds and what makes the cost independent of the array’s size.

A crossing that moves. The listing’s thirty-one occurrences per document was a property of the segment tree and not of the method, so replacing the tree moves it. Where a crossing moved to is the remeasurement, and the answer is a factor of three rather than the order of magnitude the original essay guessed at.

That is the shape. What it costs is next.