Sparse Table

data_structure/sparse_table.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/sparse_table.hpp"

int op(int a, int b) { return std::min(a, b); }

SparseTable<int, op> table(std::vector<int>{4, 2, 7});
auto value = table.prod(0, 2); // 2

操作	内容・返り値	計算量
SparseTable() / SparseTable(a)	空／配列から構築	空: \(O(1)\)、配列: \(O(n\log n)\)
build(a) / build(n,value)	配列／各要素を value(i) とする列で再構築	\(O(n\log n)\)
prod(l,r) / all_prod()	\([l,r)\)／全体の集約。空区間には e の指定が必要	\(O(1)\)
prod_unchecked(l,r)	境界検査なしで非空区間を集約	\(O(1)\)
operator[](i)	元の配列の要素を取得	\(O(1)\)
size() / empty()	要素数／空判定	\(O(1)\)
clear()	空に戻す	自明に破棄できる型: \(O(\log n)\)、その他: \(O(n\log n)\)

op は結合則と冪等性を満たす演算です。prod(l, r) は \([l,r)\)、all_prod() は全体の集約です。

空区間も使う場合は単位元を返す関数 e() を定義し、SparseTable<S, op, e> とします。build(a) または build(n, value) で再構築でき、後者は value(i) を各要素とします。

冪等性は op(x,x)==x という条件です。最小値・最大値・gcd などに使えます。総和のようにこの条件を満たさない演算には Disjoint Sparse Table を使います。構築後の要素は固定です。別の配列に変える場合は build を呼び直します。

prod_unchecked(l, r) は境界検査を省略します。非空の区間を指定してください。

再構築では各段の確保済み領域を再利用します。小さい配列へ作り直しても容量を保持することがあります。各段の要素領域を解放したい場合は clear() を使います。op が const S& を受け取れる場合、演算の引数用のコピーを省きます。

要素数を \(n\) として、構築時間と格納する要素数は \(O(n\log n)\)、集約・要素取得は \(O(1)\) です。保持する容量は過去の構築サイズにも依存します。演算とコピーは \(O(1)\) とします。

依存ライブラリ

• Default Init Allocator

検証コード

• test/auxiliary_tree.test.cpp
• test/basic_substring_structure_substrings.test.cpp
• test/dynamic_pattern_matching_array.test.cpp
• test/lca_path_sum.test.cpp
• test/lowest_common_ancestor.test.cpp
• test/permutation_tree.test.cpp
• test/sparse_table_min.test.cpp
• test/static_range_min.test.cpp
• test/static_threshold_search.test.cpp
• test/suffix_tree_array.test.cpp
• test/suffix_tree_substrings.test.cpp

コード

#ifndef SPARSE_TABLE_HPP
#define SPARSE_TABLE_HPP

#include "../components/default_init_allocator.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class S, auto op, auto e = nullptr>
class SparseTable {
	using Value = std::conditional_t<std::is_same_v<S, bool>, std::uint8_t, S>;
	using Reference = std::conditional_t<std::is_same_v<S, bool>, bool, const S &>;
	int n = 0;
	std::vector<std::vector<Value, DefaultInitAllocator<Value>>> data;
	static decltype(auto) combine(const Value &a, const Value &b) {
		if constexpr (std::is_same_v<S, bool> || !std::is_invocable_v<decltype(op), const S &, const S &>) return S(op(S(a), S(b)));
		else return op(a, b);
	}

  public:
	SparseTable() = default;
	SparseTable(const SparseTable &) = default;
	SparseTable &operator=(const SparseTable &) = default;
	SparseTable(SparseTable &&other) noexcept : n(std::exchange(other.n, 0)), data(std::move(other.data)) {}
	SparseTable &operator=(SparseTable &&other) noexcept {
		if (this != &other) {
			n = std::exchange(other.n, 0);
			data = std::move(other.data);
		}
		return *this;
	}
	explicit SparseTable(const std::vector<S> &a) { build(a); }
	void clear() {
		data.clear();
		n = 0;
	}
	void build(const std::vector<S> &a) {
		assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
		build(static_cast<int>(a.size()), [&](int i) -> S { return a[i]; });
	}
	template <class F>
	void build(int size, F value) {
		assert(size >= 0);
		n = size;
		data.resize(std::bit_width(unsigned(n)));
		if (!n) return;
		if constexpr (std::is_default_constructible_v<Value>) {
			data[0].resize(n);
			for (int i = 0; i < n; ++i) data[0][i] = value(i);
		} else {
			data[0].clear();
			data[0].reserve(n);
			for (int i = 0; i < n; ++i) data[0].push_back(value(i));
		}
		for (int k = 1; k < std::bit_width(unsigned(n)); ++k) {
			int length = n - (1U << k) + 1, half = 1U << (k - 1);
			if constexpr (std::is_default_constructible_v<Value>) {
				data[k].resize(length);
				for (int i = 0; i < length; ++i) data[k][i] = combine(data[k - 1][i], data[k - 1][i + half]);
			} else {
				data[k].clear();
				data[k].reserve(length);
				for (int i = 0; i < length; ++i) data[k].push_back(combine(data[k - 1][i], data[k - 1][i + half]));
			}
		}
	}
	int size() const { return n; }
	bool empty() const { return n == 0; }
	Reference operator[](int i) const {
		assert(0 <= i && i < n);
		return data[0][i];
	}
	[[gnu::always_inline]] S prod(int l, int r) const {
		assert(0 <= l && l <= r && r <= n);
		if constexpr (std::is_same_v<decltype(e), std::nullptr_t>) assert(l < r);
		else if (l == r) return e();
		return prod_unchecked(l, r);
	}
	[[gnu::always_inline]] S prod_unchecked(int l, int r) const {
		int k = std::bit_width(unsigned(r - l)) - 1;
		return combine(data[k][l], data[k][r - (1U << k)]);
	}
	S all_prod() const { return prod(0, n); }
};

#endif

Back to top page