Canonical density control

The Sparse Table is a data structure for controlling density in an array which was first proposed in 1981 and has recently reappeared as a component of cache-oblivious data structures. All existing variants of the Sparse Table divide the array into blocks that have a calibrator tree above them. We show that the same amortized complexity can be achieved without this auxiliary structure, obtaining a canonical data structure that can be updated by conceptually simpler algorithms.