A sparse table is a data structure that allows for range queries on a static array. It is most powerful when doing range minimum queries, as it can achieve O(1) time complexity with O(logN) processing.
WLOG we are doing range minimum queries on an array a.
The intuition of a sparse table is to store an array st[i][j] which stores min(a[i], a[i+1], a[i+2] … a[i+2^j – 1]). Then when we want to answer a query [l, r] we can simply retrieve the minimum of
st[l][f] and st[r-2^f+1][f] where f = log2(r-l+1). It is clear that we will cover the entire interval [l, r] with this query.
Now to precompute st[i][j], we can iterate in increasing order of j. Note that st[i][0] = a[i] for all i since 2^0 = 1. Then when computing st[i][j] it is just equal to min(st[i][j-1], st[i+(2^(j-1))][j-1]). We are simply splitting the range of length 2^j into 2 ranges of length 2^(j-1).
Note that we set j = log2(N) + 1
| int j = log2(N)+1; int st[N+1][j]; int a[N+1]; void precompute(){ for(int i = 1; i <= N; i++){ st[i][0] = a[i]; } for(int i = 1; i < j; i++){ for(int k = 1; k + (1<<i) <= N; k++){ st[k][i] = min(st[k][i-1], st[k+(1<<(i-1))][i-1]); } } } int query(int L, int R){ int f = base2log(R-L+1); //any log2 function will do return min(st[L][f], st[R-(1<<f)+1][f]); } |
Note that his works for max as well.
Challenge: 2D Sparse Table