Sparse Table

The Sparse Table is a data structure that maintains a sequence of $n$ numbers $a_0,a_1,\dots ,a_{n-1}$ by maintaining

$$f(i,j)=\underset{k=j}{\overset{j+2^i-1}{\max }}{a}_k$$

This requires $\mathcal{O}(n\log n)$ space.

Build

Build builds a Sparse Table for $a_0,a_1,\dots ,a_{n-1}$ in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

$$\forall i\in {\mathbb{Z}}_{+},\forall j\in \{0,1,\dots ,n-2^i\},f(i,j)=\max \{f(i-1,j),f(i-1,j+2^{i-1})\}$$

Applying the lemma to find $f$ yields an algorithm that solves the problem in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(1)$ space.

void build(int n, const std::vector<int> &a) {
	f.assign(std::__lg(n) + 1, a);
	for (int i = 1; i <= std::__lg(n); i++) {
		for (int j = 0; j + (1 << i) <= n; j++) {
			f[i][j] = std::max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
		}
	}
}

Range Maximum Query

Range Maximum Query computes ${\max }_{i=l}^{r-1}{a}_i$ in $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

$$\forall l\in \{0,1,\dots ,n-1\},\forall r\in \{l+1,l+2,\dots ,n\},\underset{i=l}{\overset{r-1}{\max }}{a}_i=\max \{f(\lfloor {\log }_2(r-l)\rfloor ,l),f(\lfloor {\log }_2(r-l)\rfloor ,r-2^{\lfloor {\log }_2(r-l)\rfloor })\}$$

Applying the lemma to find ${\max }_{i=l}^{r-1}{a}_i$ yields an algorithm that solves the problem in $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

int range_max_query(int l, int r) {
	int i = std::__lg(r - l);
	return std::max(f[i][l], f[i][r - (1 << i)]);
}