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

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.

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:
$$$$f(n,2) = \Theta(n \log n) \\ f(n,3) = \Theta(n \log \log n) \\ f(n,4) = \Theta(n \log^\ast n)$$$$
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.