Disjoint Sparse Table
(DataStructure/DisjointSparseTable.hpp)

• View this file on GitHub
• Last update: 2021-03-18 11:48:12+09:00
• Include: #include "DataStructure/DisjointSparseTable.hpp"
• Link: https://tkmst201.github.io/Library/DataStructure/DisjointSparseTable.hpp

概要

配列を扱う静的データ構造です。
要素数 $N$ の配列に対し、任意の区間の最小値や総和などの計算を、事前計算 $\Theta(N\log{N})$ クエリ $\Theta(1)$ で行うことができます。
Sparse Table で必要だった可換性や冪等性が要求されません。

• DisjointSparseTable(InputIterator first, InputIterator last, const F & f)
  • 時間/空間 $\Theta(N\log{N})$ $[first, last)$ でテーブルを構築
• size_t size()
  • $\Theta(1)$ 配列の要素数 $N$ を返す
• T fold(size_t l, size_t r)
  • $\Theta(N\log{N})$ $f(A_l, f(A_{l+1}, f(\ldots, f(A_{r-1}, A_{r-1}))\ldots)$ を返す

コンストラクタ

F は二項演算 std::function<T (const T &, const T &)> の略記です。

---

DisjointSparseTable(InputIterator first, InputIterator last, const F & f)

$[first, last)$ でテーブルを構築します。

制約

• $(T, f)$ は半群

計算量

• 時間/空間 $\Theta(N\log{N})$

---

メンバ関数

以下、要素数 $N$ の配列 $A_0, A_1, \ldots, A_{N-1}$ を対象とします。二項演算は $f$ です。

---

size_t size()

配列の要素数 $N$ を返します。

計算量

• $\Theta(1)$

---

T fold(size_t l, size_t r)

$f(A_l, f(A_{l+1}, f(\ldots, f(A_{r-1}, A_{r-1}))\ldots)$ を返します。

制約

• $0 \leq l < r \leq N$

計算量

• $\Theta(N\log{N})$

---

使用例

#include <bits/stdc++.h>
#include "DataStructure/DisjointSparseTable.hpp"
using namespace std;

int main() {
	vector<int> A{1, 10, 100, 1000, 10000};
	
	DisjointSparseTable<int> dst(begin(A), end(A), [](int x, int y) { return x + y; });
	cout << dst.fold(0, 5) << endl; // 11111
	cout << dst.fold(0, 2) << endl; // 11
	cout << dst.fold(1, 3) << endl; // 110
	cout << dst.fold(4, 5) << endl; // 10000
}

解説

build

$level$ は 1 つの累積和のサイズが $2^{level}$ 個であることを表します。
実装の都合上、左側に伸びる累積和は配列の格納順序が逆になっているので fold の l ^ ~(~0 << level) のように index を修正する必要があります。

参考

2020/04/30: https://noshi91.hatenablog.com/entry/2018/05/08/183946#fn-3c2b044b

Depends on

• bit 操作 (Mathematics/bit_operation.hpp)

Verified with

• Test/DisjointSparseTable.test.cpp

Code

#ifndef INCLUDE_GUARD_DISJOINT_SPARSE_TABLE_HPP
#define INCLUDE_GUARD_DISJOINT_SPARSE_TABLE_HPP

#include <vector>
#include <cassert>
#include <functional>
#include <algorithm>
#include <utility>

#include <Mathematics/bit_operation.hpp>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/DisjointSparseTable.hpp
 */
template <typename T>
struct DisjointSparseTable {
public:
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	F f;
	std::vector<std::vector<value_type>> table;
	
public:
	template<class InputIterator>
	DisjointSparseTable(InputIterator first, InputIterator last, const F & f) : f(f) {
		table.emplace_back(first, last);
		build();
	}
	
	size_type size() const noexcept {
		return table.empty() ? 0 : table.front().size();
	}
	
	value_type fold(size_type l, size_type r) const noexcept {
		assert(l < r);
		assert(r <= size());
		--r;
		if (l == r) return table.front()[l];
		size_type level = 31 - tk::count_leading_zeros(l ^ r);
		return f(table[level][l ^ ~(~0 << level)], table[level][r]);
	}
	
private:
	void build() {
		if (size() <= 2) return;
		table.reserve(32 - tk::count_leading_zeros(size() - 1));
		for (size_type level = 1; (1 << level) + 1 <= size(); ++level) {
			std::vector<value_type> dat;
			const size_type cnt = size() & (~0 << (level + 1));
			dat.reserve(cnt + (1 << level) + 1 <= size() ? size() : cnt);
			for (size_type i = 0; i < size(); i += 1 << (level + 1)) {
				size_type k = i + (1 << level);
				if (k >= size()) continue;
				dat.emplace_back(table.front()[k - 1]);
				for (size_type j = k - 1; j != i; --j) {
					dat.emplace_back(f(table.front()[j - 1], dat.back()));
				}
				dat.emplace_back(table.front()[k]);
				for (size_type j = k + 1, ej = std::min(k + (1 << level), size()); j != ej; ++j) {
					dat.emplace_back(f(dat.back(), table.front()[j]));
				}
			}
			table.emplace_back(std::move(dat));
		}
	}
};

#endif // INCLUDE_GUARD_DISJOINT_SPARSE_TABLE_HPP

#line 1 "DataStructure/DisjointSparseTable.hpp"



#include <vector>
#include <cassert>
#include <functional>
#include <algorithm>
#include <utility>

#include <Mathematics/bit_operation.hpp>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/DisjointSparseTable.hpp
 */
template <typename T>
struct DisjointSparseTable {
public:
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	F f;
	std::vector<std::vector<value_type>> table;
	
public:
	template<class InputIterator>
	DisjointSparseTable(InputIterator first, InputIterator last, const F & f) : f(f) {
		table.emplace_back(first, last);
		build();
	}
	
	size_type size() const noexcept {
		return table.empty() ? 0 : table.front().size();
	}
	
	value_type fold(size_type l, size_type r) const noexcept {
		assert(l < r);
		assert(r <= size());
		--r;
		if (l == r) return table.front()[l];
		size_type level = 31 - tk::count_leading_zeros(l ^ r);
		return f(table[level][l ^ ~(~0 << level)], table[level][r]);
	}
	
private:
	void build() {
		if (size() <= 2) return;
		table.reserve(32 - tk::count_leading_zeros(size() - 1));
		for (size_type level = 1; (1 << level) + 1 <= size(); ++level) {
			std::vector<value_type> dat;
			const size_type cnt = size() & (~0 << (level + 1));
			dat.reserve(cnt + (1 << level) + 1 <= size() ? size() : cnt);
			for (size_type i = 0; i < size(); i += 1 << (level + 1)) {
				size_type k = i + (1 << level);
				if (k >= size()) continue;
				dat.emplace_back(table.front()[k - 1]);
				for (size_type j = k - 1; j != i; --j) {
					dat.emplace_back(f(table.front()[j - 1], dat.back()));
				}
				dat.emplace_back(table.front()[k]);
				for (size_type j = k + 1, ej = std::min(k + (1 << level), size()); j != ej; ++j) {
					dat.emplace_back(f(dat.back(), table.front()[j]));
				}
			}
			table.emplace_back(std::move(dat));
		}
	}
};

Back to top page