###
Path Queries on Functions

####
Travis Gagie, Meng He, and Gonzalo Navarro

Let *f : [1..n] -> [1..n]* be a function, and *l : [1..n] -> [1..s]*
indicate a label assigned to each element of the domain. We design several
compact data structures that answer various queries on the labels of
*paths* in *f*. For example, we can find the minimum label in
*f^k (i)* for a given *i* and any *k >= 0* in a given range
*[k1..k2]*, using *n lg n + O(n)* bits, or the minimum label in
*f^(-k) (i)* for a given *i* and *k > 0*, using *2n lg n +
O(n)* bits, both in time *O(lg n/ lg lg n)*. By using *n lg s +
o(n lg s)* further bits, we can also count, within the same time, the number
of elements within a range of labels, and report each such element in
*O(1 + lg s / lg lg n)** additional time. Several other possible
queries are considered, such as top-t queries and t-majorities.
*