簡潔データ構造
この表の各エントリには lg  n {\displaystyle \lg n} ビットが必要で、合計 ( n / l ) lg  n = n / lg  n {\displaystyle (n/l)\lg n=n/\lg n} ビットの領域を使う。大ブロックの中では、もう一つの表 R s [ 0 ... l / s ) {\displaystyle R_{s}[0\dots l/s)} を使って、そのブロックに含まれる l / s = 2 lg  n {\displaystyle l/s=2\lg n} 個の小ブロックのrankを保持する。ここでの違いは、各エントリで、そのエントリが入っている大ブロックの最初のビットのrankからの差分だけを保持すればよいので、 lg  l = lg  lg 2  n = 2 lg  lg  n {\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n} ビットだけが必要になることである。このため、この表は合計 ( n / s ) lg  l = 4 n lg  lg  n / lg  n {\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n} ビットになる。そして、小ブロック内の i ∈ [ 0 , s ) {\displaystyle i\in [0,s)} ビットに対しては、 s {\displaystyle s} ビットの全てのビット列に対するrank質問の答えを保持するルックアップ表 R p {\displaystyle R_{p}} を使うことができる。