rank-select · shipping · also Bitvector rank and select, Rank/select dictionary

Rank/select

Rank counts selected bits in a bitvector prefix, while select locates a selected bit by its occurrence number.

Contract: With zero-based bit positions, R(p) counts ones before p, for 0 <= p <= n. S(j) returns the position of one number j, with occurrences numbered from zero. For valid j, R(S(j)) = j and R(S(j) + 1) = j + 1. These are different coordinate systems, not interchangeable offsets. [1]

Example: In 10010110, one positions are 0, 3, 5, 6. Thus R(3) = 1, S(1) = 3, and the number of ones in positions 3 through 5 is R(6) - R(3) = 2. Empty prefixes are valid; selecting a nonexistent one is outside the operation's domain. [4]

Conventions: SDSL rank excludes its endpoint but select numbers occurrences from one; its second one is select(2) = 3 in the example. SuRF's section 2.6 rank example includes the queried bit. Translate that inclusive rank at p as R(p + 1), not R(p). A formula copied without its endpoint and ordinal conventions can silently address the wrong entry. [2] [3]

Storage: Efficient queries require support structures as well as the bitmap. Vigna's rank9 stores two 64-bit support words per 512 data bits, a 25% layout overhead before boundary handling. The SuRF sparse trie's 10 bits per node likewise excludes auxiliary rank/select bits. Neither figure is a whole-index memory bill. [1] [3]

Relations

related
Succinct data structure, RRR bitvector, Elias-Fano encoding, Succinct range filter, Wavelet tree, Wavelet matrix, FM-index

Citations

  1. Sebastiano Vigna, Broadword Implementation of Rank/Select Queries, author revision 2023-01-31, sections 2-3 (accessed 2026-11-17)
  2. SDSL tutorial: rank_support and select_support examples (accessed 2026-11-17)
  3. Zhang et al., SuRF: Practical Range Query Filtering with Fast Succinct Tries, SIGMOD 2018, sections 2.5-2.6 (accessed 2026-11-17)
  4. Hesela: rank/select convention examples and exact scanning reference (CC0) (accessed 2026-11-17)

Further reading

  1. Hesela: exhaustive rank/select identities and invalid-input tests (CC0) (accessed 2026-11-17)
Sources & caveats
  • Primary-source synthesis of indexing conventions and memory accounting, not a replication of throughput experiments.
  • The worked bitvector is constructed. Its downloadable reference scans bits and is not a succinct rank/select implementation.
  • The Broadword PDF identifies itself as the 2023-01-31 author revision; this is not a claim that the underlying work was first published in 2023.

JSON: /data/terms/rank-select.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Rank/select. Hesela. 2026-11-17. https://hesela.dev/terms/rank-select/