簡潔データ構造
この下界を達成する(静的な)簡潔辞書は存在し、 必要とする領域は B ( m , n ) + o ( B ( m , n ) ) {\displaystyle {\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))} である。そのデータ構造はさらに、 B ( m , n ) + O ( m + n lg  lg  n / lg  n ) {\displaystyle {\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)} の領域量でrankとselectをサポートするように拡張することができる。この下界は、辞書を保持する領域を B ( m , n ) + O ( n t t / lg t  n + n 3 / 4 ) {\displaystyle {\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})} とし、質問に必要な時間を O ( t ) {\displaystyle O(t)} とすることで領域と時間のトレードオフに帰着させることができる。