Sparse table(KACTL version)
(DS/Sparse_table.hpp)

• View this file on GitHub
• Last update: 2024-05-22 23:06:51+07:00
• Include: #include "DS/Sparse_table.hpp"

Description:

Range Minimum Queries on an array. Returns min(V[a], V[a + 1], … V[b - 1]) in constant time. Also work for max queries

Usage:

• RMQ rmq(values);
• rmq.query(inclusive, exclusive);

Time:

• $O(V\log(V)+Q)$

Required by

• tree/LCA_kactl.hpp

Verified with

• test/yosupo/Ds/RMQ_yosupo.test.cpp
• test/yosupo/Tree/LCA_yosupo_2.test.cpp

Code

#pragma once

template<class T>
struct sparsetable {
	vector<vector<T>> jmp;
	sparsetable(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= V.size(); pw *= 2, ++k) {
			jmp.emplace_back(V.size() - pw * 2 + 1);
			rep(j,jmp[k].size())
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

#line 2 "DS/Sparse_table.hpp"

template<class T>
struct sparsetable {
	vector<vector<T>> jmp;
	sparsetable(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= V.size(); pw *= 2, ++k) {
			jmp.emplace_back(V.size() - pw * 2 + 1);
			rep(j,jmp[k].size())
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

Back to top page