# Data structure for prefix covering

I have a list $$[1, 2, \ldots, T]$$. I want to create a collection of subsets, such that:

1. each element belongs to a small number of subsets
2. each prefix is a union of small number of subsets (these subsets can intersect, but they must exactly cover the prefix)

For a given collection of subsets, let $$F$$ and $$G$$ be the maximums of the values from the first and second properties respectively.

Examples:

• binary tree: each elements belongs to $$\log T$$ subsets (so, $$F = \log T$$) and each prefix can be represented by a union of $$\log T$$ subsets ($$G = \log T$$)
• prefixes themselves, i.e. $$[1]$$, $$[1, 2]$$, $$[1, 2, 3]$$, $$\ldots$$, $$[1, 2, \ldots, T]$$. Here, element 1 belongs to $$T$$ subsets, and each prefix is exactly 1 subset. Therefore, $$F = T$$ and $$G = 1$$.

My question is, which structure minimises $$G \log F$$?

In particular, compared to binary search structure, where $$F = G = \log T$$, I would like to have a smaller value of $$G$$ in the expense of larger $$F$$.

My intuition is that it is possible to have $$G = O(\log^w \log T)$$ while $$F = O(\log^k T)$$, for some constant $$w$$ and $$k$$, which would give $$G \log F = O(\log^{w+1} \log T)$$.

On the other hand, maybe there exist some lowerbounds from coding theory?

I looked at the van Emde Boas tree, but could not improve $$G \log F$$.

Thank you!

• The obvious parameter setting to explore is $G=2$. Then to do better than what you've got so far, you need to have $F < \sqrt{T}$. So I think the first natural question is, is there a way to achieve both $F<\sqrt{T}$ and $G=2$? That seems pretty challenging.
– D.W.
Commented Oct 15, 2023 at 0:47