Home▸Algorithms & AI▸Succinct Rank/Select Bitvector

🧮 Succinct Rank/Select Bitvector

Explore how a bit array can be augmented with a tiny superblock/block index so that rank and select queries run in constant time using barely any extra space beyond the raw bits.

Algorithms & AI3DModerate60 FPS

The simulator builds a bitvector from user input or a random sample, lays out superblock and block boundaries at adjustable sizes, and shows the precomputed running totals stored at each boundary. It then walks through a rank or select query step by step, highlighting exactly which superblock total, which block partial total, and which final popcount lookup combine to produce the answer, alongside a running tally of how many bits the auxiliary index costs compared to the raw bitvector.

🔬 What It Demonstrates

🎮 How to Use

Enter or randomize a bitvector, then adjust the superblock size and block size sliders to see the index boundaries redraw and the stored counts update. Type a position for rank or a rank value for select and press query to watch the three-step lookup animate: superblock total, block partial total, and final leftover popcount. Toggle the overhead panel to compare the index's bit cost against a naive fully-precomputed table at the same input length.

💡 Did You Know?

Modern processors execute a hardware popcount instruction on a 64-bit word in roughly one clock cycle, which is why real succinct bitvector libraries can answer billions of rank queries per second even though, in theory, they are only guaranteed constant time rather than instant time.

⚙ Under the hood

Explore how a bit array can be augmented with a tiny superblock/block index so that rank and select queries run in constant time using barely any extra space beyond the raw bits.

succinct data structuresrank selectbitvectorcompact indexingpopcountwavelet treesalgorithms

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install