Skip to content

Sparse Table

Definition

Illustration of a sparse table

A sparse table (ST) is a data structure for solving idempotent range query problems.

What is an idempotent range query problem?

A range query problem is idempotent if its operation \(\operatorname{opt}\) satisfies \(x\operatorname{opt} x=x\). For example, \(\max(x,x)=x\) and \(\operatorname{gcd}(x,x)=x\), so RMQ and range GCD are idempotent range query problems. Range sum is not: if the precomputed ranges used to answer a query overlap, the overlap is counted twice, which is not what we want. A sparse table also requires \(\operatorname{opt}\) to be associative.

What is RMQ?

RMQ stands for Range Maximum/Minimum Query: finding the maximum (or minimum) over a range. There are many ways to solve it; see the RMQ topic page.

Introduction

Luogu P3865 [Template] Sparse Table & RMQ Problem

You are given \(n\) (\(1\le n\le 10^5\)) integers and \(m\) (\(1\le m\le 2\times 10^6\)) queries. For each query, find the maximum over the range \([l,r]\).

Consider brute force first: for each query, scan the range \([l,r]\) and take the maximum.

Clearly, this is too slow to pass the time limit.

Sparse table

A sparse table is built on binary lifting. After \(\Theta(n\log n)\) preprocessing it answers each query in \(\Theta(1)\), but it does not support updates.

How can binary lifting give us a range maximum? If we apply it in the usual way, jumping \(2^i\) steps at a time, a query still takes \(\Theta(\log n)\). That is no faster than a segment tree, and the preprocessing is slower.

But \(\max(x,x)=x\): the range maximum is idempotent. So the precomputed ranges we combine are allowed to overlap, and the answer is still correct as long as their union is exactly the queried range.

Trying a few cases by hand shows that two precomputed ranges are always enough to cover a queried range. A query therefore takes only \(\Theta(1)\), which makes a real difference when there are many queries.

Here are the details.

Let \(f(i,j)\) denote the maximum over the range \([i,i+2^j-1]\).

Clearly \(f(i,0)=a_i\).

In binary lifting terms, the second index means "jump \(2^j-1\) steps", which gives the recurrence \(f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))\).

That is all there is to the preprocessing. Queries are just as simple.

We cover each query \([l,r]\) with two ranges, \([l,l+2^s-1]\) and \([r-2^s+1,r]\), where \(s=\left\lfloor\log_2(r-l+1)\right\rfloor\). The answer is the larger of their two maxima.

Query procedure of a sparse table

As argued above, the maximum is idempotent, so the overlap between the two ranges does no harm. And since together they cover exactly \([l,r]\), the answer is correct.

Luogu P3865 [Template] Sparse Table & RMQ Problem reference implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 100000 + 5;
constexpr int logN = 16;  // ⌊ log_2 N ⌋
int f[logN + 1][N], Logn[N];

// initialize the logarithms
void pre() {
  Logn[2] = 1;
  for (int i = 3; i < N; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  pre();
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> f[0][i];
  for (int j = 1; j <= logN; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);  // the sparse table recurrence
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    int s = Logn[y - x + 1];
    cout << max(f[s][x], f[s][y - (1 << s) + 1]) << '\n';
  }
  return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
#if defined(_MSC_VER) && !defined(__clang__)
#include <immintrin.h>
#define __builtin_clz _lzcnt_u32
#endif
using namespace std;

// compute ⌊ log_2 x ⌋ with a built-in function
int lg2(int x) { return 31 - __builtin_clz(x); }

template <typename T>
class SparseTable {
  using VT = vector<T>;
  using VVT = vector<VT>;
  using func_type = function<T(const T &, const T &)>;

  VVT ST;

  static T default_func(const T &t1, const T &t2) { return max(t1, t2); }

  func_type op;

 public:
  SparseTable(const vector<T> &v, func_type _func = default_func) {
    op = _func;
    int n = v.size(), l = lg2(n);
    ST.assign(l + 1, VT(n, 0));
    for (int i = 0; i < n; ++i) {
      ST[0][i] = v[i];
    }
    for (int j = 1; j <= l; ++j) {
      for (int i = 0; i + (1 << j) <= n; ++i) {
        ST[j][i] = op(ST[j - 1][i], ST[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T query(int l, int r) {
    int q = lg2(r - l + 1);
    return op(ST[q][l], ST[q][r - (1 << q) + 1]);
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int &i : a) cin >> i;
  SparseTable<int> st(a);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    cout << st.query(x - 1, y - 1) << '\n';
  }
  return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys

input = sys.stdin.readline


class SparseTable:
    def __init__(self, arr: list, func=min):
        self.func = func
        self.n = len(arr)
        self.log = [0] * (self.n + 1)

        for i in range(2, self.n + 1):
            self.log[i] = self.log[i // 2] + 1

        self.k = self.log[self.n]
        self.st = [[0] * (self.n) for _ in range(self.k + 1)]
        self.st[0] = arr

        for j in range(1, self.k + 1):
            i = 0
            while i + (1 << j) <= self.n:
                self.st[j][i] = self.func(
                    self.st[j - 1][i], self.st[j - 1][i + (1 << (j - 1))]
                )
                i += 1

    def query(self, left: int, right: int):
        j = self.log[right - left + 1]
        return self.func(self.st[j][left], self.st[j][right - (1 << j) + 1])


n, m = map(int, input().split())
a = list(map(int, input().split()))
st = SparseTable(a, max)
for _ in range(m):
    left, right = map(int, input().split())
    print(st.query(left - 1, right - 1))

Caveats

  1. The input and output are usually large, so use fast I/O.

  2. The table is usually a two-dimensional array, with \(\log n\) entries along one dimension and \(n\) along the other. Put the \(\log n\) dimension first: this improves cache locality.

  3. Calling std::log on every query is wasteful. Use a built-in such as __builtin_clz or __lg instead; if none is available, precompute the logarithms like this:

\[ \begin{cases} \texttt{Logn}[1] \gets 0, \\ \texttt{Logn}\left[i\right] \gets \texttt{Logn}\left[\frac{i}{2}\right] + 1. \end{cases} \]

Sparse tables for other operations

RMQ is not the only idempotent range query problem. Range bitwise AND, range bitwise OR and range GCD are others, and a sparse table handles all of them efficiently.

For range GCD, though, a sparse table query is asymptotically no faster than a segment tree query. (If the values are at most \(w\), a sparse table query takes \(\Theta(\log w)\) and a segment tree query \(\Theta(\log n+\log w)\), and the bound on the values is usually larger than \(n\).) On the other hand, its preprocessing is no slower than a segment tree's, and it is much simpler to code.

Looked at closely, idempotent range query problems tend to have an RMQ hidden inside them. Range bitwise AND is a minimum taken bit by bit, and range GCD is a minimum taken over the exponent of each prime factor.

Summary

A sparse table is a good fit for idempotent range queries (the operation must also be associative): it is fast and takes far less code than the alternatives. But it works for only a narrow class of operations, is hard to extend, and does not support updates.

Practice problems

Appendix: time complexity of range GCD with a sparse table

Preprocessing takes \(\Theta(\log n)\) iterations, and each of them calls the recursive GCD function. If the values are at most \(w\), one GCD call costs up to \(O(\log w)\), so at first sight the total is \(O(n\log n\log w)\).

However, every recursive step of GCD except the last at least halves some number in the sequence, and the numbers in the sequence can be halved at most \(\log_2 (w^n)=\Theta(n\log w)\) times in total. So the recursive steps number at most \(O(n\log w)\) overall. Adding the \(\Theta(n\log n)\) for the loops (and the last step of each recursion) gives \(O(n(\log w+\log n))\). Inputs can be constructed that force \(\Omega(n(\log w+\log n))\), so the bound is tight: \(\Theta(n(\log w+\log n))\).

Queries are easy to analyze: in the worst case every query hits the worst possible pair of numbers and costs \(\Theta(\log w)\). So range GCD on a sparse table takes \(\Theta(n(\log n+\log w))\) to preprocess and \(\Theta(\log w)\) per query.

A segment tree takes \(\Theta(n\log w)\) to preprocess and \(\Theta(\log n+\log w)\) per query.

This argument is not rigorous. A more careful one follows.

A more rigorous proof

This part assumes you know the potential method; see time complexity.

We start with the preprocessing.

Call the sequence at the current level of the preprocessing loop the current sequence, and denote it by \(A\). At level zero it is the original sequence; at level one it is what one iteration makes of that, namely st[1..n][1]; and so on.

Define the potential as the base-two logarithm of the product of all numbers in the current sequence: \(\Phi(A)=\log_2\left(\prod\limits_{i=1}^n A_i\right)\).

The time for one iteration is the time for the loop itself plus the time spent inside GCD. The latter varies: a call may recurse only once or twice, or as many as \(O(\log w)\) times. But every recursive step other than the first and the last at least halves some entry of the current sequence. Each such step lowers \(\Phi(A)\) by at least \(1\), so its cost is amortized against the potential.

Initially \(\Phi(A)\) is at most \(\log_2 (w^n)=\Theta(n\log w)\), and \(\Phi(A)\) never increases. Hence preprocessing the sparse table takes \(O(n(\log w+\log n))\).