Range Minimum Query (RMQ) structures over a slice: given i and j, where is the smallest element of x[i..j]?

Tabulation is the extensive tabulation construction based on this: it numbers each block by the shape of its Cartesian tree and tabulates every answer once per shape. Sparse is the simplest, and is the reference the other two are tested against, but its table dominates memory on large inputs.

BlockMask is the one to reach for by default. Blocks of 32, a sparse table over the block minima, and in-block queries read out of a per-position bitmask of the block's suffix minima. At a million elements it needs 5.9MB against Tabulation's 14.8MB and Sparse's 80MB, and answers roughly 1.8x more queries per second than Tabulation (see cargo bench).

Note that all three return the index of a minimum in the range, and not its value. When several elements tie for the minimum, which of their indices comes back is unspecified and differs between the implementations.

All three borrow the slice rather than copying it, and are generic over any Ord type. Slices are limited to u32::MAX elements: indices are stored as u32, which is much of what keeps the tables small.

For the theoretical background, I did enjoy this course by Sebastian Wild.