簡潔データ構造
このテーブルには 2 s lg  s = O ( n lg  lg  n ) {\displaystyle 2^{s}\lg s=O({\sqrt {n}}\lg \lg n)} ビットの領域を必要とする。 これらの補助表は o ( n ) {\displaystyle o(n)} の領域だけを使うため、このデータ構造はrank質問を O ( 1 ) {\displaystyle O(1)} 時間と n + o ( n ) {\displaystyle n+o(n)} ビットの領域でサポートする。
次の定数時間アルゴリズムを用いると、 r a n k 1 ( x ) {\displaystyle \mathbf {rank} _{1}(x)} の質問に定数時間で答えることができる。
r a n k 1 ( x ) = R l [ ⌊ x / l ⌋ ] + R s [ ⌊ x / s ⌋ ] + R p [ x ⌊ x / s ⌋ , x mod s ] {\displaystyle \mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]}