lazySquareDecomp (区間更新可能平方分割)
(src/dataStructure/lazySquareDecomp.hpp)

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

前置き

lazySegmentTreeで同様の処理がより高速にできます。そちらをお使いください。ドキュメントの更新も止まってます。

概要

平方分割の手法を用いて列上のクエリを高速に処理するデータ構造です。遅延評価可能であるため、src/dataStructure/sqdecomp.hpp と比較して、区間更新が可能となっています

平方分割について

$N$ 要素の列に対して $\sqrt{N}$ の大きさのバケットを $\sqrt{N}$ 個保持し、要素の更新や演算処理に対してバケットを利用する。(詳細: TODO?)

クエリについて

言葉の定義

• $N$ : 非負整数
• $A$ : 長さ $N$ の列、 $A$ 上でクエリを処理する
• $T$ : $A$ の各要素 $A_i (0\ \le\ i\ <\ n)$ が属する集合
• $\oplus$ : $T$ 上の演算
• $\text{id}_T$ : $T$ の要素、 $\oplus$ の単位元
• $S$ : ある集合
• $f_x\ :\ T\ \rightarrow\ T$ : $x\ \in\ S$ で定義される写像
• $\times$ : $S$ 上で定義される演算
• $\text{id}_S$ : $S$ の要素、 $\times$ の単位元

要件

• $(T, \oplus, \text{id}_T)$ はモノイド を成す
• $(S, \times, \text{id}_S)$ はモノイドを成す
• $f_{\text{id}_S} (v)\ =\ v$ $(v\ \in\ T)$
• $f_x(v_1\oplus v_2)\ =\ f_x(v_1)\ \oplus\ f_x(v_2)$ を満たす(自己準同型)
• $f_{x_1}(f_{x_2}(v))\ =\ f_{x_1\times x_2} (v)$ を満たす

処理できるクエリ

• update l r x : $l\ \le\ i\ <\ r$ を満たす整数 $i$ について $A_i\ \leftarrow\ f_x(A_i)$
• prod l r: $\displaystyle \bigoplus_{i = l}^{r - 1} A_i$ を求める

機能

計算量の表記について、 $\oplus$ や $\times$ の計算量が $O(1)$ であることを仮定しています。 (例えば $\oplus$ や $\times$ が $O(\text{hoge})$ なら計算量が $\text{hoge}$ 倍されます)

コンストラクタ

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

• 以下の機能をもたせたstructを用意してください
  • using valueMonoid: $(T, \oplus, \text{id}_T)$ を表現したモノイド構造体(後述)
  • using operatorMonoid: $(S, \times, \text{id}_S)$ を表現したモノイド構造体
  • static valueMonoid::valueType mapping(const value_monoid::valye_type& v, const operator_monoid::value_type& x) : $f_x(v)$ を返す関数、const参照や値渡しなどを用いること(引数の中身を変更しないように)
• モノイド構造体は以下の機能を持たせてください
  • using value_type : $T$ や $S$ の型
  • static constexpr value_type identity : $\text{id}_T$ や $\text{id}_S$ といった単位元
  • static value_type operation(const value_type& a, const value_type& b): $a\oplus b$ や $a\times b$ を返す関数。こちらも引数の中身を変更しないように

zawa::lazy_sqdecomp<structure>(std::size_t n):

• $A$ を長さ $N$ 、 各要素を structure::value_monoid::identityで初期化する
• 計算量 : $O(N)$

zawa::lazy_sqdecomp<structure>(const std::vector<structure::value_monoid::value_type>& A)

• $A$ を A で初期化する
• 計算量 : $O(N)$

メンバ関数

structure::value_monoid::value_typeをT、structure::operator_monoid::value_typeをSと表記します（長いので）

void update(int pos, const S& value)

• $A_{\text{pos}}\ \leftarrow\ f_{\text{value}} (A_{\text{pos}})$ とする
• テストをしていません
• 計算量 : $O(\sqrt{N})$

void update(int l, int r, const S value)

• $l\ \le\ i\ <\ r$ を満たす整数 $i$ について $A_i\ \leftarrow\ f_{\text{value}}(A_i)$ とする
• 計算量 : $O(\sqrt{N})$

T prod(int l, int r)

• $\displaystyle \bigoplus_{i = l}^{r - 1} A_i$ を求める
• 計算量 : $O(\sqrt{N})$

参考

SegmentTreeに載る代数的構造について

セグメント木をあきらめた人のための平方分割

Verified with

• test/lazySquareDecomp-AOJ-RAQRSQ.test.cpp
• test/lazySquareDecomp-AOJ-RAQRmQ.test.cpp
• test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp
• test/lazySquareDecomp-AOJ-RUQRmQ.test.cpp

Code

#pragma once

#include <vector>
#include <cmath>
#include <algorithm>

namespace zawa {

template <class structure>
class lazySquareDecomp {
	using V = typename structure::valueMonoid::valueType;
	using O = typename structure::operatorMonoid::valueType;

private:
	static constexpr V vId = structure::valueMonoid::identity;
	static constexpr O oId = structure::operatorMonoid::identity;
	struct node {
		V value;
		O lazy;
		node() : value(vId), lazy(oId) {}
	};
	int square;
	std::vector<V> dat;
	std::vector<node> bucket;

	void propagate(int pos) {
		int l = square * pos;
		for (int i = 0 ; i < square ; i++) {
			dat[l + i] = structure::mapping(dat[l + i], bucket[pos].lazy);	
		}
		bucket[pos].lazy = oId;
	}

	void update(int pos) {
		bucket[pos].value = vId;
		int l = square * pos;
		for (int i = 0 ; i < square and l + i < (int)dat.size() ; i++) {
			bucket[pos].value = structure::valueMonoid::operation(bucket[pos].value, dat[l + i]);
		}
	}
	
public:
	lazySquareDecomp(int n) : square(std::sqrt(n + 1)), dat(n, vId), bucket((n + square - 1) / square) {
		for (std::size_t i = 0 ; i < dat.size() ; i++) {
			bucket[i / square].value = structure::valueMonoid::operation(bucket[i / square].value, dat[i]);
		}
	}
	lazySquareDecomp(const std::vector<V>& A) : square(std::sqrt(A.size() + 1)), dat(A), bucket((A.size() + square - 1) / square) {
		for (std::size_t i = 0 ; i < dat.size() ; i++) {
			bucket[i / square].value = structure::valueMonoid::operation(bucket[i / square].value, dat[i]);
		}
	}

	void update(int pos, const O& value) {
		if (bucket[pos / square].lazy != oId) {
			propagate(pos / square);
		}
		dat[pos] = structure::mapping(dat[pos], value);
		update(pos / square);
	}	

	void update(int l, int r, const O& value) {	
		for (int i = 0 ; i < (int)bucket.size() ; i++) {
			int p = i * square, q = (i + 1) * square;
			if (r <= p or q <= l) {
				continue;
			}
			if (l <= p and q <= r) {
				bucket[i].lazy = structure::operatorMonoid::operation(bucket[i].lazy, value);
			}
			else {
				if (bucket[i].lazy != oId) {
					propagate(i);
				}
				for (int j = std::max(l, p) ; j < std::min({ q, r, (int)dat.size() }) ; j++) {
					dat[j] = structure::mapping(dat[j], value);
				}
				update(i);
			}
		}
	}

	V prod(int l, int r) {
		V res = vId;
		for (int i = 0 ; i < (int)bucket.size() ; i++) {
			int p = i * square, q = (i + 1) * square;
			if (r <= p or q <= l) {
				continue;
			}
			if (l <= p and q <= r) {
				if (bucket[i].lazy != oId) {
					res = structure::valueMonoid::operation(res, structure::mapping(bucket[i].value, bucket[i].lazy));
				}
				else {
					res = structure::valueMonoid::operation(res, bucket[i].value);
				}
			}
			else {
				if (bucket[i].lazy != oId) {
					propagate(i);
					update(i);
				}
				for (int j = std::max(l, p) ; j < std::min({ q, r, (int)dat.size() }) ; j++) {
					res = structure::valueMonoid::operation(res, dat[j]);
				}
			}
		}
		return res;
	}
};

} // namespace zawa

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

#include <vector>
#include <cmath>
#include <algorithm>

namespace zawa {

template <class structure>
class lazySquareDecomp {
	using V = typename structure::valueMonoid::valueType;
	using O = typename structure::operatorMonoid::valueType;

private:
	static constexpr V vId = structure::valueMonoid::identity;
	static constexpr O oId = structure::operatorMonoid::identity;
	struct node {
		V value;
		O lazy;
		node() : value(vId), lazy(oId) {}
	};
	int square;
	std::vector<V> dat;
	std::vector<node> bucket;

	void propagate(int pos) {
		int l = square * pos;
		for (int i = 0 ; i < square ; i++) {
			dat[l + i] = structure::mapping(dat[l + i], bucket[pos].lazy);	
		}
		bucket[pos].lazy = oId;
	}

	void update(int pos) {
		bucket[pos].value = vId;
		int l = square * pos;
		for (int i = 0 ; i < square and l + i < (int)dat.size() ; i++) {
			bucket[pos].value = structure::valueMonoid::operation(bucket[pos].value, dat[l + i]);
		}
	}
	
public:
	lazySquareDecomp(int n) : square(std::sqrt(n + 1)), dat(n, vId), bucket((n + square - 1) / square) {
		for (std::size_t i = 0 ; i < dat.size() ; i++) {
			bucket[i / square].value = structure::valueMonoid::operation(bucket[i / square].value, dat[i]);
		}
	}
	lazySquareDecomp(const std::vector<V>& A) : square(std::sqrt(A.size() + 1)), dat(A), bucket((A.size() + square - 1) / square) {
		for (std::size_t i = 0 ; i < dat.size() ; i++) {
			bucket[i / square].value = structure::valueMonoid::operation(bucket[i / square].value, dat[i]);
		}
	}

	void update(int pos, const O& value) {
		if (bucket[pos / square].lazy != oId) {
			propagate(pos / square);
		}
		dat[pos] = structure::mapping(dat[pos], value);
		update(pos / square);
	}	

	void update(int l, int r, const O& value) {	
		for (int i = 0 ; i < (int)bucket.size() ; i++) {
			int p = i * square, q = (i + 1) * square;
			if (r <= p or q <= l) {
				continue;
			}
			if (l <= p and q <= r) {
				bucket[i].lazy = structure::operatorMonoid::operation(bucket[i].lazy, value);
			}
			else {
				if (bucket[i].lazy != oId) {
					propagate(i);
				}
				for (int j = std::max(l, p) ; j < std::min({ q, r, (int)dat.size() }) ; j++) {
					dat[j] = structure::mapping(dat[j], value);
				}
				update(i);
			}
		}
	}

	V prod(int l, int r) {
		V res = vId;
		for (int i = 0 ; i < (int)bucket.size() ; i++) {
			int p = i * square, q = (i + 1) * square;
			if (r <= p or q <= l) {
				continue;
			}
			if (l <= p and q <= r) {
				if (bucket[i].lazy != oId) {
					res = structure::valueMonoid::operation(res, structure::mapping(bucket[i].value, bucket[i].lazy));
				}
				else {
					res = structure::valueMonoid::operation(res, bucket[i].value);
				}
			}
			else {
				if (bucket[i].lazy != oId) {
					propagate(i);
					update(i);
				}
				for (int j = std::max(l, p) ; j < std::min({ q, r, (int)dat.size() }) ; j++) {
					res = structure::valueMonoid::operation(res, dat[j]);
				}
			}
		}
		return res;
	}
};

} // namespace zawa

Back to top page