Interesting Upper Bounds [Dodis, P, Thorup '10] Store a vector A[1..n] from alphabet Σ – Space ⌈ n log 2 Σ ⌉ – Constant time to read or write A[i] [P, FOCS' 08] Store a vector A[1..n] of bits – Query time O(t) for RANK (k) := A[1] + … + A[k] – Space n + n / (w/t) t
{}