segmentTree (一点更新・区間演算セグ木)
(src/dataStructure/segmentTree.hpp)

View this file on GitHub
Last update: 2023-03-10 16:33:31+09:00
Include: #include "src/dataStructure/segmentTree.hpp"

概要

セグメント木を用いて列上のクエリを高速を処理します。

セグメント木について

2冪の区間についての区間和を保持することで要素の更新に $\log$ かけるかわりに任意の区間和を $\log$ にする。

詳しくはTODO?

クエリについて

モノイド $(S, \oplus, \text{id})$ と $S$ の要素からなる長さ $N$ の数列 $A$ について

set i p: $A_i\ \leftarrow\ p$
action i p: $A_i\ \leftarrow A_i \oplus p$
prod l r : get $\displaystyle \bigoplus_{i = l}^r A_i$

のクエリを処理することができる

機能

コンストラクタ

(1) zawa::segmentTree<monoid>()
(2) zawa::segmentTree<monoid>(int _N)
(3) zawa::segmentTree<monoid>(const std::vector<monoid::valueType>& A)

テンプレート引数monoidについて

以下の機能をもたせたstructを用意してください
- using value_type: $S$ の型
- static constexpr value_type identity : モノイドの単位元 $\text{id}$
- static value_type operation(const value_type& a, const value_type& b): $a\oplus b$ を返す関数

(1) デフォルトコンストラクタ

(2)

$A$ を長さ $N$ で各要素をmonoid::identityで初期化する

計算量

$O(N)$

(3)

$A$ を引数に与えた std::vectorで初期化する

計算量

$O(\mid A\mid)$

以降、 $\mid A \mid\ =\ N$ とする

メンバ関数

set

void set(std::size_t pos, const monoid::value_type& value)

$A_{\text{pos}}\ \leftarrow\ \text{value}$ とする

制約

$0\ \le\ \text{pos}\ <\ N$

計算量

$O(\log N)$

update

T update(std::size_t pos, const monoid::value_type& value)

$A_{\text{pos}}\ \leftarrow\ A_{\text{pos}} \oplus \text{value}$ とする

制約

$0\ \le\ \text{pos}\ <\ N$

計算量

$O(\log N)$

prod

T prod(std::size_t l, std::size_t r) const

$\displaystyle \bigoplus_{i = l}^r A_i$ を返す

制約

$0\ \le\ l\ <\ N$

$l\ \le\ r\ \le\ N$

計算量

$O(\log N)$

maxRight

int maxRight<functionType>(int l, const function_type& f) const

単調性を持つブール関数 $f$ について、 $\displaystyle f(\bigoplus_{i = l}^r A_i)\ =\ \text{false}$ となる最小の $r$ を返す。

functionTypeはstd::function<bool(monoid::value_type)>

制約

$0\ \le\ l\ <\ N$

計算量

$O(\log N)$

minLeft

int min_left<functionType>(int r, const function_type& f) const

単調性を持つブール関数 $f$ について、 $\displaystyle f(\bigoplus_{i = l}^r A_i)\ =\ \text{false}$ となる最大の $l$ を返す。

functionTypeはstd::function<bool(monoid::value_type)>

制約

$0\ \le\ r\ <\ N$

計算量

$O(\log N)$

参考

Verified with

Code

#pragma once

#include <vector>
#include <functional>

namespace zawa {

template <class monoid>
class segmentTree {
private:
	using V = typename monoid::valueType;
	std::size_t N;
	std::vector<V> dat;

public:
	segmentTree() {}
	segmentTree(int _N) : N(_N), dat(2 * _N, monoid::identity) {}
	segmentTree(const std::vector<V>& A) : N(A.size()), dat(2 * N, monoid::identity) {
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			dat[i + N] = A[i];
		}
		for (std::size_t i = N - 1 ; i > 0 ; i--) {
			dat[i] = monoid::operation(dat[i << 1], dat[i << 1 | 1]);		
		}
	}

	void set(std::size_t pos, const V& value) {
		pos += N;
		dat[pos] = value;
		while (pos >>= 1) {
			dat[pos] = monoid::operation(dat[pos << 1], dat[pos << 1 | 1]);
		}
	}

	V update(std::size_t pos, const V& value) {
		pos += N;
		do {
			dat[pos] = monoid::operation(dat[pos], value);
		} while (pos >>= 1);
		return dat[pos];
	}

	V prod(std::size_t l, std::size_t r) const {
		V left = monoid::identity, right = monoid::identity;
		for (l += N, r += N ; l < r ; l >>= 1, r >>= 1) {
			if (l & 1) {
				left = monoid::operation(left, dat[l++]);	
			}
			if (r & 1) {
				right = monoid::operation(dat[--r], right);
			}
		}
		return monoid::operation(left, right);
	}

	template <class functionType>
	int maxRight(int l, const functionType& f) const {
		int L = l + N, w = 1;
		V v = monoid::identity;
		for ( ; l + w <= (int)N ; L >>= 1, w <<= 1) {
			if (L & 1) {
			   	if (f(monoid::operation(v, dat[L]))) {
					v = monoid::operation(v, dat[L++]);
					l += w;
				}
				else {
					break;
				}
			}
		}
		while (L <<= 1, w >>= 1) {
			if (l + w <= (int)N and f(monoid::operation(v, dat[L]))) {
				v = monoid::operation(v, dat[L++]);
				l += w;
			}
		}
		return l;
	}

	template <class functionType>
	int minLeft(int r, const functionType& f) const {	
		int R = r + N, w = 1;
		V v = monoid::identity;
		for ( ; r - w >= 0 ; R >>= 1, w <<= 1) {
			if (R & 1) {
				if (f(monoid::operation(dat[R - 1], v))) {
					v = monoid::operation(dat[--R], v);
					r -= w;
				}
				else {
					break;
				}
			}
		}
		while (R <<= 1, w >>= 1) {
			if (r - w >= 0 and f(monoid::operation(dat[R - 1], v))) {
				v = monoid::operation(dat[--R], v);
				r -= w;
			}
		}
		return r;
	}	
};

} // namespace zawa

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

#include <vector>
#include <functional>

namespace zawa {

template <class monoid>
class segmentTree {
private:
	using V = typename monoid::valueType;
	std::size_t N;
	std::vector<V> dat;

public:
	segmentTree() {}
	segmentTree(int _N) : N(_N), dat(2 * _N, monoid::identity) {}
	segmentTree(const std::vector<V>& A) : N(A.size()), dat(2 * N, monoid::identity) {
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			dat[i + N] = A[i];
		}
		for (std::size_t i = N - 1 ; i > 0 ; i--) {
			dat[i] = monoid::operation(dat[i << 1], dat[i << 1 | 1]);		
		}
	}

	void set(std::size_t pos, const V& value) {
		pos += N;
		dat[pos] = value;
		while (pos >>= 1) {
			dat[pos] = monoid::operation(dat[pos << 1], dat[pos << 1 | 1]);
		}
	}

	V update(std::size_t pos, const V& value) {
		pos += N;
		do {
			dat[pos] = monoid::operation(dat[pos], value);
		} while (pos >>= 1);
		return dat[pos];
	}

	V prod(std::size_t l, std::size_t r) const {
		V left = monoid::identity, right = monoid::identity;
		for (l += N, r += N ; l < r ; l >>= 1, r >>= 1) {
			if (l & 1) {
				left = monoid::operation(left, dat[l++]);	
			}
			if (r & 1) {
				right = monoid::operation(dat[--r], right);
			}
		}
		return monoid::operation(left, right);
	}

	template <class functionType>
	int maxRight(int l, const functionType& f) const {
		int L = l + N, w = 1;
		V v = monoid::identity;
		for ( ; l + w <= (int)N ; L >>= 1, w <<= 1) {
			if (L & 1) {
			   	if (f(monoid::operation(v, dat[L]))) {
					v = monoid::operation(v, dat[L++]);
					l += w;
				}
				else {
					break;
				}
			}
		}
		while (L <<= 1, w >>= 1) {
			if (l + w <= (int)N and f(monoid::operation(v, dat[L]))) {
				v = monoid::operation(v, dat[L++]);
				l += w;
			}
		}
		return l;
	}

	template <class functionType>
	int minLeft(int r, const functionType& f) const {	
		int R = r + N, w = 1;
		V v = monoid::identity;
		for ( ; r - w >= 0 ; R >>= 1, w <<= 1) {
			if (R & 1) {
				if (f(monoid::operation(dat[R - 1], v))) {
					v = monoid::operation(dat[--R], v);
					r -= w;
				}
				else {
					break;
				}
			}
		}
		while (R <<= 1, w >>= 1) {
			if (r - w >= 0 and f(monoid::operation(dat[R - 1], v))) {
				v = monoid::operation(dat[--R], v);
				r -= w;
			}
		}
		return r;
	}	
};

} // namespace zawa

segmentTree (一点更新・区間演算セグ木) (src/dataStructure/segmentTree.hpp)

概要

セグメント木について

クエリについて

機能

コンストラクタ

メンバ関数

参考

Verified with

Code

segmentTree (一点更新・区間演算セグ木)
(src/dataStructure/segmentTree.hpp)