Sparse Table is a data structure that answers static Range Minimum Query (RMQ). It is recognized for its relatively fast query and short implementation compared to other data structures.
The main idea of Sparse Table is to precompute for all pairs .
Build a Sparse Table on array
3 1 5 3 4 7 6 1
where cell , and , stores .
To answer , we can select two pre-computed data with one starts from and the other one ends at such that their combined interval covers interval .
There always exist a pair of precomputed interval such that they cover any range
Let be the largest integer such that . Then, let the first and second interval be and respectively. If the two intervals don't overlaps, this gives us and leads to a contradiction to our initial assumption that is the largest integer such that .
The implementation for Sparse Table can be done with simple dynamic programming approach.
The first row is a copy of the initial array. From the second row onward, we can avoid recalculations by optimally picking two green cells from the previous row to get the desired interval. For example, interval can be achieved by combining intervals and .
1 2 3 4 5 6 7 8 9 10 11 12
As proven in the previous section, there always exist a pair of precomputed interval in the same row to achieve our desired interval. The trickier part is to find the value . A clever method is to observe that and look at the binary representation of . is the position of the most significant bit. For example,
10 returns 1,
1011 returns 3,
11111 returns 4 and
1 returns 0. Fortunately, in C++ there's a built-in function
__builtin_clz() that returns the number of leading
0's until the first
1 bit. Since there are a total of 32 bits for a C++
int data type, the desired answer is
1 2 3 4
In a macro level, since there are columns and rows and each cell takes time to compute, the overall complexity is .
Similarly, memory complexity is also .
We only need two cells for any pairs , hence complexity is .