###
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 kinds of summary queries on the
labels of *paths* in *f*. For example, we can find either the minimum
label in *f^k(i)* for a given *i* and any *k >= 0* in a given
range *[k1..k2]*, or the minimum label in *f^(-k)(i)* for a given
*i* and *k > 0*, using *n lg n + n lg s + o(n lg n)* bits and
time *O(alpha(n))*, the inverse Ackermann function. Within similar space
we can count, in time *O(lg n / lg lg n)*, the number of labels within a
range, and report each element with such labels in *O(lg n / lg lg n)*
additional time. Several other tradeoffs and possible queries are considered,
such as selection, top-*r* queries and *t*-majorities. Finally, we
consider queries that allow us navigate on the graph of the function, such as
the nearest common successor of two elements, or the nearest successor or
predecessor of an element within a range of labels.