Data Structures & Algorithms: How to Perform Minimum Queries in Constant Time
This short article describes the sparse table method. It enables to efficiently perform many min-queries (or max-queries) on sub-arrays of a given array, i.e. to find minima (or maxima) of sub-arrays.
If we only have a small number of queries to perform, we can just take a naïve approach and iterate through all the numbers of the sub-arrays we consider. However, if we have many queries to make, this method will end up being very slow.
We’ll start by preprocessing the input array in linearithmic time. This preprocessing step produces an auxiliary array which we’ll use to calculate the minimum of any sub-array in constant time.
Throughout this article, we’ll use letter A to denote the input array and N to denote the number of elements it contains. Indices start at 1.
Preprocessing
The preprocessing step computes the minimum value of every sub-array whose length is a power of two.
We’ll use dynamic programming to calculate the precomputed values in Θ(N log N) time and space.
We’ll store the precomputed results in a two-dimensional array denoted SpTa (for Sparse Table). For all indices i, j where it makes sense, SpTa(i, j) will correspond to the minimum of the sub-array starting at index i and containing exactly 2^j elements: A[i .. i + 2^j - 1]. i can be any index of A (i.e. between 1 and N) and j must satisfy 2^j ≤ N, so j ≤ log₂ N. Therefore, the shape of SpTa is N × (⎣log₂ N⎦+ 1). (“+ 1” because j can take value 0.)
To populate this array, we start by setting SpTa(i, 0) = A[i] for all indices i of A. This is because the sub-array A[i .. i + 2⁰ - 1] only contains A[i], so its minimum element is indeed A[i].
The optimal substructure follows from a simple observation: the minimum between the minima of two sub-arrays is the minimum of their union. Therefore, the minimum of A[i .. i + 2^j - 1] is the minimum between m and m’, where m is the minimum of A[i .. i + 2^{j - 1} - 1] and m’ is the minimum of A[i + 2^{j - 1} .. i + 2^{j} - 1]:
Substituting values previously computed and stored in SpTa, we get:
To implement the above approach, it is important to notice that the computation of SpTa(i, j) relies on computations where i is lower, but j is greater. Therefore, the outer loop of the algorithms corresponds to j and the inner loop corresponds to i.
The following pseudocode defines an algorithm that computes the sparse table of a given array.
The algorithm described above runs in Θ(N log N) time.
Calculating the minimum of a sub-array
We can think of any sub-array A[i .. j] as the union of two sub-arrays U := A[i .. i + 2^k — 1] and V := A[j — 2^k + 1 .. j] whose lengths are powers 2. We choose k such that 2^k is the greatest power of two which does not exceed the length of A[i .. j]:
We need to prove that all the values of A[i .. j] do belong to one of the two sub-arrays U and V. First of all, we observe that both sub-arrays have the same length. Suppose there is a value A[p] (with i ≤ p ≤ j) which not in U or V. Then 2 * 2^k is strictly less than the length of A[i .. j]. Therefore, there exists a power of two which is greater than 2^k and still does not exceed the length of A[i .. j].
Using this method, we can implement a function which takes a sparse table and the lower and upper bounds of a sub-array, and returns the minimum of the sub-array in O(1) time:
Since 2^k is the greatest power of two which does not exceed the length of the sub-array.
Support me
Thanks for reading! I am mathematics and computer science student and write articles covering various areas of computing and programming. If you’d like to receive an email when I publish a new story or to become my referred member, you can follow this link to subscribe: https://medium.com/subscribe/@alouizakarie.
