Function which describes an optimal data structure for a bounded number of query operations?

Question

Given an ordered sequence of $n$ elements, you have to choose a family $A$ of subsets of consecutive elements, such that each subset of consecutive elements (not necessairly in $A$) can be represented as a disjoint union of at most $k$ elements of $A$. Let $A$ be the minimal set with this property, define the function $f(n, k):=|A|$. Now I am really interested in how this function behaves. Notice that $A$ actually describes a data structure which is capable of answering most kinds of interval queries (the sequence of elements have to be elements of a monoid) in $k$ "operations". I've discussed it with some of my colleagues and we have noticed the following:

Obviously $f(n, 1) = {n \choose2}$.

Now more interestingly, $f(n, 2) = O(n \; log(n))$, and the structure of $|A|$ vaguely resembles the standard implementation of a sparse table.

Some also interesting upper bounds are $f(n, log(log(n))) = O(n \; log(log(n)))$, you can build a tree which resembles the van Emde Boas data structure.

And for $f(n, 2log(n) - 2)$ = $O(n)$ you can use the segment tree data structure. Asymptotically, $f(n, O(log(n))) = O(n)$, this is tight.

Now, I am interested in whether anyone has seen something resembling this function anywhere before? Seems like many data structures can be viewed of as optimal constructions of $A$ for different values of $k$? It would be really helpful if someone could just point me to a reference.

Answer 1

This question is answered by Alon and Schieber [1]. For a constant $k \geq 2$, the asymptotic bound is $f(n,k) = \Theta(n \lambda(k,n))$ where $\lambda(k,\cdot)$ is a certain slowly growing function. Concrete values are:

$ \begin{equation} f(n,2) = \Theta(n \log n) \\ f(n,3) = \Theta(n \log \log n) \\ f(n,4) = \Theta(n \log^\ast n) \end{equation} $

The upper bound is proven by a simple recursive algorithm.

For non-constant $k$, it is proven that $f(n,O(\alpha(n))) = \Theta(n)$ where $\alpha(n)$ is the inverse Ackermann function. This is best possible for the linear number of subsets.

• [1] Alon, Noga, and Baruch Schieber. “Optimal Preprocessing for Answering On-Line Product Queries,” 1987.