sparse tables
I guess I am a fan of tables. Also I thought this will be a quick write up since my last blog had suggestions to convert it into a gitbook. Although I hope you like this one, it won't take much of your time.
Sparse Tables, it's probably a niche data structure with a great time complexity when answering range queries on static arrays.
Motivation
Alright! Let's talk about the type of situation where you might want to use sparse tables. As I said, it's all about doing efficient range queries on static arrays. So, a typical use case is when you're dealing with say an integer array that has immutable data i.e. does not change over the course of time.
Some common types of range queries that you often want to know are things like finding the minimum value in a certain range, may be finding the sum, product, gcd, etc. For a significant amount of queries, you would definitely not want to take a lot of time (i.e. brute force) in processing the solution.
Intuition
I'd like to give you a brief intuition on how a sparse table works at a high level without getting into too many details.
So, if you think about any positive integer, you know that it can easily be represented as the sum of powers of 2, given by it's binary representation. For example:
Similary we can break down an interval [l, r] with a left and a right end point into ranges of lengths that are powers of 2. For example:
Here, [5, 17] is broken down into three ranges of length 8, 4, and 1. Now imagine if we could precompute the range query answer (i.e min, max, sum ...) for all these intervals and combine them.
Prerequisites
The first is that the binary range combination function is associative which means that the order in which operations are performed, does not matter.
More formally:
f(x, y) is associative if:
f(a, f(b, c)) = f(f(a, b), c) for all a, b, cOperations like addition, multiplication are associative, but functions like subtraction and exponentiation are not. Here's a counterexample proving subtraction is not associative:
Let f(a, b) = a - b
f(1, f(2, 3)) = f(1, 2 - 3) = f(1, -1) = 2
f(f(1, 2), 3) = f(1 - 2, 3) = f(-1, 3) = -4
∴ f is not associativeIf your range combination function is associative, then you can do range queries on a sparse table in logarithmic O(log₂(n)) time.
Range Combination Function
When the range query combination function is overlap friendly, then range queries on a sparse table can be answered in O(1). A function is overlap friendly if it yields the same answer regardless of whether it is combining ranges which overlap or those that do not.
We say a binary function f(x, y) is overlap friendly if:
f(f(a, b), f(b, c)) = f(a, f(b, c)) for all valid a, b, cConsider this array and a summation function f(x, y) which just adds x and y. Unfortunately, this is not overlap friendly:
f(f(r1, r2), f(r2, r3)) = f(f(1, 3), f(3, 24)) = f(4, 27) = 31
and
f(r1, f(r2, r3)) = f(7, f(3, 24)) = f(7, 27) = 34
∴ f is not overlap friendlyQ. Which of these are overlap friendly functions?
f(a, b) = 1 * b - YES
f(a, b) = a * b - NO
f(a, b) = min(a, b) - YES
f(a, b) = max(a, b) - YES
f(a, b) = a + b - NO
f(a, b) = a - b - NO
f(a, b) = gcd(a, b) - YESTable Construction
The central idea behind a sparse table is to pre compute the range query answers for all intervals of size 2^x to efficiently answer range queries between [l, r]. The main downside to this approach is that you need O(Nlog(N)) memory.
Let N be size of the input values array, and let 2^P be the largest power of 2 that fits in the length of the values array.
P = floor(log2(N)) = floor(log2(13)) = 3Each cell (i, j) represents the answer for the range [j, j + 2^i) in the original array.
For example, cell (2, 5) represents the answer for the range [5, 9). If we're building a min sparse table then the (2, 5) cell would have a value of 3.
Now that we understand what each cell represents, let's build a sparse table to support minimum range queries. The range combination function:
f(x, y) = min(x, y)The current cell (i, j) represents the range [j, j + 2^i) which always has even length. This range can be broken into two sub intervals which we will have already computed.
To compute the value of cell (3, 2), we split it into two orange cells representing intervals of length 4:
More specifically the range for the cell (i, j) can be split into:
- left interval: [j, j + 2^(i-1))
- right interval: [j + 2^(i-1), j + 2^i)
Finish filling the sparse table by combining values from the previous rows (dynamic programming):
dp[i][j] = f(dp[i-1][j], dp[i-1][j+pow(2, i-1)])
= min(dp[i-1][j], dp[i-1][j+pow(2, i-1)])Range Queries
In the table we have already precomputed the answer for all intervals of length 2^x. Let k be the largest power of two that fits in the length of the range between [l, r].
Knowing k we can do a lookup in the table to find the minimum:
- Left interval: [l, l + k]
- Right interval: [r-k+1, r]
Q: Suppose we want to know the minimum value between [1, 11]?
len = l - r + 1 = 11 - 1 + 1 = 11
P = floor(log2(len)) = floor(3.321) = 3
k = pow(2, P) = pow(2, 3) = 8
= min(dp[P][l], dp[P][r - k + 1])
= min(dp[3][1], dp[3][4])
= min(1, -1)
= -1Associative Function Queries
Some functions such as multiplication and summation are associative, but not overlap friendly. A sparse table can still accommodate such functions via a cascading query. You can do this by breaking the range [l, r] into smaller ranges of size 2^x which do not overlap.
For example range between [2, 15] can be split into:
[2, 10) U [10, 14) U [14, 16)
= dp[2][0] * dp[1][4] * dp[0][6]
= -12 * -4 * 5
= 240
Pseudocode
function BuildMinSparseTable(values):
N = length(values)
P = floor(log(N) / log(2))
log2 = [0, 0, ..., 0, 0]
for (i = 2 ; i <=N ; ++i):
log2[i] = log2[i/2] + 1
for (i = 0 ; i < N ; ++i):
dp[0][i] = values[i]
it[0][i] = i
for (p = 1 ; p <= P ; ++p):
for (i = 0 ; i + (1<<p) <= N ; ++i):
left = dp[p-1][i]
right = dp[p-1][i + (1<<(p-1))]
dp[p][i] = min(left, right)
if left <= right:
it[p][i] = it[p-1][i]
else:
it[p][i] = it[p-1][i + (1 << (p-1))]
function MinQuery(l, r):
len = r - l + 1
p = log2[len]
left = dp[p][l]
right = dp[p][r - (1<<p) + 1]
return min(left, right)
function CascadingMinQuery(l, r):
minVal = inf
for (p = log2[r - l + 1] ; l <= r ; p = log2[r - l + 1]):
minVal = min(minVal, dp[p][l])
l += (1<<p)
return minVal
function MinIndexQuery(l, r):
len = r - l + 1
p = log2[len]
left = dp[p][l]
right = dp[p][r - (1<<p) + 1]
if left <= right:
return it[p][l]
return it[p][r - (1<<p) + 1]C++ Implementation
#include <bits/stdc++.h>
using namespace std;
class MinSparseTable {
int n, P;
vector<int> log2;
vector<vector<int>> dp, it;
int inf = 1e9;
public:
vector<int> values;
MinSparseTable(vector<int> &values) {
n = values.size();
P = (int) (log(n) / log(2));
dp.resize(P+1, vector<int>(n));
it.resize(P+1, vector<int>(n));
for (int i = 0 ; i < n ; ++i) {
dp[0][i] = values[i];
it[0][i] = i;
}
log2.resize(n+1);
for (int i = 2 ; i <= n ; ++i)
log2[i] = log2[i/2] + 1;
for (int p = 1 ; p <= P ; ++p) {
for (int i = 0; i + (1<<p) <= n ; ++i) {
int leftInterval = dp[p-1][i];
int rightInterval = dp[p-1][i + (1 << (p-1))];
dp[p][i] = min(leftInterval, rightInterval);
if (leftInterval <= rightInterval)
it[p][i] = it[p-1][i];
else
it[p][i] = it[p-1][i + (1 << (p-1))];
}
}
}
int MinQuery(int l, int r) {
int len = r - l + 1;
int p = log2[len];
int left = dp[p][l];
int right = dp[p][r - (1<<p) + 1];
return min(left, right);
}
int CascadingMinQuery(int l, int r) {
int minVal = inf;
for (int p = log2[r - l + 1] ; l <= r ; p = log2[r - l + 1]) {
minVal = min(minVal, dp[p][l]);
l += (1<<p);
}
return minVal;
}
int MinIndexQuery(int l, int r) {
int len = r - l + 1;
int p = log2[len];
int left = dp[p][l];
int right = dp[p][r - (1<<p) + 1];
if (left <= right)
return it[p][l];
return it[p][r - (1<<p) + 1];
}
};
int main() {
vector<int> values = {1, 2, -3, 2, 4, -1, 5};
MinSparseTable minSparseTable(values);
cout << minSparseTable.MinQuery(1, 5) << endl; // -3
cout << minSparseTable.MinIndexQuery(1, 5) << endl; // 2
return 0;
}That's about it! Hope you had a good time :). Do subscribe if you're interested to get notified for further posts.