On the minimum total length of interval systems expressing all intervals, and range-restricted queries

In this paper, we study the classical one-dimensional range-searching problem, i.e., expressing any interval {i,…,j}⊆{1,…,n} as a disjoint union of at most k intervals in a system of intervals, though with a different lens: we are interested in the minimum total length of the intervals in such a system (and not their number, as is the concern traditionally).We show that the minimum total length of a system of intervals in {1,…,n} that allows to express any interval as a disjoint union of at most k intervals of the system is for any fixed k. We also prove that the minimum number of intervals k=k(n,c), for which there exists a system of intervals of total length cn with that property, satisfies for any integer c⩾1. We also discuss the situation when k=Θ(logn).