×

zbMATH — the first resource for mathematics

Storing a sparse table with O(1) worst case access time. (English) Zbl 0629.68068
A data structure for representing a set of n items from a universe of m items, which uses space \(n+o(n)\) and accommodates membership queries in constant time is described. Both the data structure and the query algorithm are easy to implement.

MSC:
68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI