One cost follows the array and the other does not

One cost follows the array and the other does not

Reads a query, averaged over 80 random ranges at each size. One act is one memory access the structure chose to make: a node visited in the segment tree, a table or array entry read in the succinct one. The tree goes from 23.1 to 41.9 across a 64x growth in the array, which is its two logarithms; the succinct structure goes from 15.4 to 16.9, which is flat, because a query is a fixed number of lookups whatever the array holds. The two answered every range identically.

Drawn at 700 × 420, wide on the page. Everything above is what rmq-work returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

4 essays call rmq-work. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.