sparseTable ( $x \oplus x\ =\ x$ の区間クエリ解答 )
(src/dataStructure/sparseTable.hpp)

• View this file on GitHub
• Last update: 2023-03-06 15:21:58+09:00
• Include: #include "src/dataStructure/sparseTable.hpp"

概要

更新の無い列 $A$ に対して以下の条件を満たす演算 $\oplus$ に対するクエリ $\displaystyle \bigoplus_{i = l}^{r - 1}A_i$ を求める

• 結合則 $(a \oplus b) \oplus c\ =\ a \oplus (b \oplus c)$
• 等冪則 $a \oplus a\ =\ a$

例: min、max、gcd

機能

コンストラクタ

以下、structure::valueTypeをTと省略する。

sparseTable<structure>(const std::vector<T>& A)

$A$ を引数のstd::vector<T>で初期化する

テンプレート引数structureは以下を満たす構造体にしてください

• $A$ の型をusing valueType = でエイリアスする
• 演算 $\oplus$ を表現するstatic valueType operation(const valueType& a, const valueType& b) 関数

計算量

$O(\mid A\mid \log \mid A \mid)$

メンバ

query

T query(int l, int r)

$\displaystyle \bigoplus_{i = l}^{r - 1}A_i$ を求める

制約

$0\ \le\ l\ <\ r\ \le\ \mid A\mid$

計算量

$O(1)$

_dat

const std::vector<std::vector<T>>& _dat()

• 内部のコンテナを返します。デバッグにでも

Verified with

• test/ABC125-C.test.cpp
• test/sparseTable.test.cpp

Code

#pragma once

#include <vector>
#include <cassert>

namespace zawa {

template <class structure>
class sparseTable {
private:
	using T = typename structure::valueType;
	std::vector<int> L;
	std::vector<std::vector<T>> dat;

public:

	sparseTable(const std::vector<T>& A) : L(A.size() + 1, 0) {
		for (int i = 1 ; i < (int)L.size() ; i++) {
			L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
		}
		dat = std::vector(L.back() + 1, A);
		for (int i = 1 ; i < (int)dat.size() ; i++) {
			int pt = (1 << i);
			for (int j = 0 ; j + pt - 1 < (int)dat[i].size() ; j++) {
				dat[i][j] = structure::operation(dat[i - 1][j], dat[i - 1][j + (pt >> 1)]);
			}
		}
	}

	T query(int l, int r) {
		assert(0 <= l and l < (int)dat[0].size());
		assert(l <= r and r <= (int)dat[0].size());
		int now = L[r - l];
		return structure::operation(dat[now][l], dat[now][r - (1 << now)]);
	}

	inline std::vector<std::vector<T>> _dat() const {
		return dat;
	}

};

} // namespace zawa

#line 2 "src/dataStructure/sparseTable.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <class structure>
class sparseTable {
private:
	using T = typename structure::valueType;
	std::vector<int> L;
	std::vector<std::vector<T>> dat;

public:

	sparseTable(const std::vector<T>& A) : L(A.size() + 1, 0) {
		for (int i = 1 ; i < (int)L.size() ; i++) {
			L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
		}
		dat = std::vector(L.back() + 1, A);
		for (int i = 1 ; i < (int)dat.size() ; i++) {
			int pt = (1 << i);
			for (int j = 0 ; j + pt - 1 < (int)dat[i].size() ; j++) {
				dat[i][j] = structure::operation(dat[i - 1][j], dat[i - 1][j + (pt >> 1)]);
			}
		}
	}

	T query(int l, int r) {
		assert(0 <= l and l < (int)dat[0].size());
		assert(l <= r and r <= (int)dat[0].size());
		int now = L[r - l];
		return structure::operation(dat[now][l], dat[now][r - (1 << now)]);
	}

	inline std::vector<std::vector<T>> _dat() const {
		return dat;
	}

};

} // namespace zawa

Back to top page