  Indexing of static and dynamic sets is fundamental to a large set of
applications such as information retrieval and caching. Denoting the
characteristic vector of the set by B, we consider the problem of encoding sets
and multisets to support approximate versions of the operations rank(i) (i.e.,
computing sum_{j <= i}B[j]) and select(i) (i.e., finding min{p | rank(p) >= i})
queries. We study multiple types of approximations (allowing an error in the
query or the result) and present lower bounds and succinct data structures for
several variants of the problem. We also extend our model to sliding windows,
in which we process a stream of elements and compute suffix sums. This is a
generalization of the window summation problem that allows the user to specify
the window size at query time. Here, we provide an algorithm that supports
updates and queries in constant time while requiring just (1+o(1)) factor more
space than the fixed-window summation algorithms.
