Sparse Table
(library/data-structures/1d-range-queries/sparse-table.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/data-structures/1d-range-queries/sparse-table.hpp"

Sparse Table

Unfortunately, I’m not sure how to template this to do $\max$ also since you have to access v. This can’t be modified for “destrutive combinations” like $\gcd$.

Assumptions

• $0$-indexed.

Functions

• comb(a, b): You can modify this for different combinations, right now it’s set to get the $min$ of elements at indices $a, b$ with tie broken by the minimum index.
• index(l, r): Gets index of $\text{min}$ element in range $[l, r]$ in $\mathcal O(1)$.
• query(l, r): Gets minimum element in range $[l, r]$ in $\mathcal O(1)$.
• init(v): Initializes for array $v$ in $\mathcal O(n \log(n))$.

Resources

• Benq

Required by

• LCA RMQ (library/graphs/lca-rmq.hpp)
• Suffix Array with Longest Common Prefix (library/string/suffix-array-lcp.hpp)

Verified with

• verify/codeforces/codeforces-1074F.test.cpp
• verify/yosupo/yosupo-frequency_table_of_tree_distance.test.cpp
• verify/yosupo/yosupo-lca-lca-rmq.test.cpp
• verify/yosupo/yosupo-suffixarray-lcp.test.cpp

Code

#pragma once

template <class T> struct SparseTable {
	std::vector<T> v;
	std::vector<std::vector<int>> jump;

	int level(int x) { return 31 - __builtin_clz(x); }

	int comb(int a, int b) {
		return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
	}

	void init(const std::vector<T>& _v) {
		v = _v;
		jump = {std::vector<int>((int)v.size())};
		iota(jump[0].begin(), jump[0].end(), 0);
		for (int j = 1; (1 << j) <= (int)v.size(); j++) {
			jump.push_back(std::vector<int>((int)v.size() - (1 << j) + 1));
			for (int i = 0; i < (int)jump[j].size(); i++) {
				jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int index(int l, int r) {
		assert(l <= r);
		int d = level(r - l + 1);
		return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
	}

	T query(int l, int r) {
		return v[index(l, r)];
	}
};

template <class T> struct SparseTable {
	std::vector<T> v;
	std::vector<std::vector<int>> jump;

	int level(int x) { return 31 - __builtin_clz(x); }

	int comb(int a, int b) {
		return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
	}

	void init(const std::vector<T>& _v) {
		v = _v;
		jump = {std::vector<int>((int)v.size())};
		iota(jump[0].begin(), jump[0].end(), 0);
		for (int j = 1; (1 << j) <= (int)v.size(); j++) {
			jump.push_back(std::vector<int>((int)v.size() - (1 << j) + 1));
			for (int i = 0; i < (int)jump[j].size(); i++) {
				jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int index(int l, int r) {
		assert(l <= r);
		int d = level(r - l + 1);
		return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
	}

	T query(int l, int r) {
		return v[index(l, r)];
	}
};

Back to top page