Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Lookup table — where it appears

Every answer to a small question, computed once and shared. It buys constant time when the answers depend on less than the input does — the position of a minimum inside a block of parentheses depends on the block's shape and not on where its excess started, which is what makes the table finite.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

0000200121200the parenthesis sequencethe minimum excess of each block of 213 blocks · lookup table 72 bits, sharedblock 2 · 24 parentheses13 blocks

The table that fits inside a block

A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.

machine · Range parentheses131,07216.7%select support115,71214.8%superblock minima16,3982.1%superblock table80,97010.3%block minima147,46518.8%block tables291,25537.2%the partsbitstotal 782,872 · the segment tree 2,228,224shared lookup table 82,944, not counted65,536 values · openings in index order, found by select2.85x smaller

Two bits a value, and what undoes them

The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.

space · Range

Named alongside it

The objects these essays reach for when they reach for this one.

Cartesian treeConstant factorMeasurementRange minimumRank directorySegment treeSpace overheadSuccinctTrade offBlock decompositionConstant timeDocument listing

All concepts