library/data-structure/sparse-table.hpp

• View this file on GitHub
• Last update: 2023-07-11 10:41:16+08:00
• Include: #include "library/data-structure/sparse-table.hpp"

Required by

• library/tree/hld.hpp

Verified with

• test/data-structure/sparse-table/yosupo-Static-RMQ.test.cpp
• test/tree/hld/aoj-grl-Lowest-Common-Ancestor.test.cpp
• test/tree/hld/aoj-grl-Range-Query-on-a-Tree-II.test.cpp
• test/tree/hld/aoj-grl-Range-Query-on-a-Tree.test.cpp
• test/tree/hld/yosupo-Jump-on-Tree.test.cpp
• test/tree/hld/yosupo-Lowest-Common-Ancestor.test.cpp
• test/tree/hld/yosupo-Vertex-Add-Path-Sum.test.cpp
• test/tree/hld/yosupo-Vertex-Add-Subtree-Sum.test.cpp
• test/tree/hld/yosupo-Vertex-Set-Path-Composite.test.cpp

Code

#pragma once
#include <vector>
#include <cassert>

namespace felix {

template<class S, S (*op)(S, S)>
struct sparse_table {
public:
	sparse_table() {}
	explicit sparse_table(const std::vector<S>& a) {
		n = (int) a.size();
		int max_log = std::__lg(n) + 1;
		mat.resize(max_log);
		mat[0] = a;
		for(int j = 1; j < max_log; ++j) {
			mat[j].resize(n - (1 << j) + 1);
			for(int i = 0; i <= n - (1 << j); ++i) {
				mat[j][i] = op(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	S prod(int from, int to) const {
		assert(0 <= from && from <= to && to <= n - 1);
		int lg = std::__lg(to - from + 1);
		return op(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
	}

private:
	int n;
	std::vector<std::vector<S>> mat;
};

} // namespace felix

#line 2 "library/data-structure/sparse-table.hpp"
#include <vector>
#include <cassert>

namespace felix {

template<class S, S (*op)(S, S)>
struct sparse_table {
public:
	sparse_table() {}
	explicit sparse_table(const std::vector<S>& a) {
		n = (int) a.size();
		int max_log = std::__lg(n) + 1;
		mat.resize(max_log);
		mat[0] = a;
		for(int j = 1; j < max_log; ++j) {
			mat[j].resize(n - (1 << j) + 1);
			for(int i = 0; i <= n - (1 << j); ++i) {
				mat[j][i] = op(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	S prod(int from, int to) const {
		assert(0 <= from && from <= to && to <= n - 1);
		int lg = std::__lg(to - from + 1);
		return op(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
	}

private:
	int n;
	std::vector<std::vector<S>> mat;
};

} // namespace felix

Back to top page