dualSegmentTree (区間更新一点取得セグ木)
(src/dataStructure/dualSegmentTree.hpp)

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

概要

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

セグメント木とは？

• TODO

どのようなクエリを処理できますか？

モノイド $(S, \oplus, \text{id})$ と $S$ 上で定義される列 $A$ について

• $A$ の連続する区間 $[l, r)$ に属する値に $\oplus$ を適用する
• $A$ のある値を取得する

が可能

機能

コンストラクタ

以下monoid::value_typeをOと呼ぶ

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

(1)

デフォルトコンストラクタ

(2)

$A$ を $\text{id}$ で初期化する

(3)

$A$ を引数に与える

テンプレート引数monoidについて、以下の要件を満たす構造体を用意してください

• using value_type = Sの型がある
• statc constexpr value_type identity が定義されている $(\text{id})$
• static value_type operation(const value_type& a, const value_type& b) が定義されている $(\oplus)$

制約

$\mid A\mid\ >\ 0$

計算量

(2)、(3)ともに $O(\mid A\mid)$

operator

[]

O operator[] (int i)

$A_i$ を取得する

制約

$0\ \le\ i\ <\ \mid A\mid$

計算量

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

メンバ

set

void set(int i, const O& value)

$A_i$ に valueを代入する

未テスト

制約

$0\ \le\ i\ <\ \mid A\mid$

計算量

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

update

(1) void update(int i, const O& value)
(2) void update(int l, int r, const O& value)

(1) $A_i$ に $A_i\oplus \text{value}$ を代入する

• 未テスト

(2) $l\ \le\ i\ <\ r$ について $A_i$ に $A_i\oplus \text{value}$ を代入する

制約

• $0\ \le\ i, l\ <\ \mid A\mid$
• $l\ \le\ r\ \le\ \mid A\mid$

計算量

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

Verified with

• test/ABC179-F.test.cpp
• test/ABC291-F.test.cpp
• test/dualSegmentTree-AOJRAQ.test.cpp
• test/practice90-037.test.cpp

Code

#pragma once

#include <vector>
#include <cassert>

namespace zawa {

template <class monoid>
class dualSegmentTree {
private:
	using O = typename monoid::valueType;
	int N;
	std::vector<O> dat;

	constexpr int left(int v) const {
		return v << 1;
	}

	constexpr int right(int v) const {
		return v << 1 | 1;
	}

	constexpr int parent(int v) const {
		return v >> 1;
	}

	inline void propagate(int v) {
		if (left(v) < (int)dat.size()) {
			dat[left(v)] = monoid::operation(dat[left(v)], dat[v]);
		}
		if (right(v) < (int)dat.size()) {
			dat[right(v)] = monoid::operation(dat[right(v)], dat[v]);
		}
		dat[v] = monoid::identity;
	}

	void push(int v) {
		int height = 31 - __builtin_clz(v);
		for (int i = height ; i >= 1 ; i--) {
			propagate(v >> i);
		}
	}

public:
	dualSegmentTree() {}
	dualSegmentTree(int _N) : N(_N), dat(_N << 1, monoid::identity) {}
	dualSegmentTree(const std::vector<O>& A) : N((int)A.size()), dat(A.size() << 1, monoid::identity) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			dat[i + N] = A[i];
		}
	}

	O operator[](int i) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		return dat[i];
	}

	void set(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = value;
	}

	void update(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = monoid::operation(dat[i], value);
	}

	void update(int l, int r, const O& value) {
		assert(0 <= l and l < N);
		assert(l <= r and r <= N);
		if (l == r) {
			return;
		}
		l += N; r += N;
		push(l); push(r - 1);
		for ( ; l < r ; l = parent(l), r = parent(r)) {
			if (l & 1) {
				dat[l] = monoid::operation(dat[l], value);
				l++;
			}
			if (r & 1) {
				r--;
				dat[r] = monoid::operation(dat[r], value);
			}
		}
	}

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

} // namespace 

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

#include <vector>
#include <cassert>

namespace zawa {

template <class monoid>
class dualSegmentTree {
private:
	using O = typename monoid::valueType;
	int N;
	std::vector<O> dat;

	constexpr int left(int v) const {
		return v << 1;
	}

	constexpr int right(int v) const {
		return v << 1 | 1;
	}

	constexpr int parent(int v) const {
		return v >> 1;
	}

	inline void propagate(int v) {
		if (left(v) < (int)dat.size()) {
			dat[left(v)] = monoid::operation(dat[left(v)], dat[v]);
		}
		if (right(v) < (int)dat.size()) {
			dat[right(v)] = monoid::operation(dat[right(v)], dat[v]);
		}
		dat[v] = monoid::identity;
	}

	void push(int v) {
		int height = 31 - __builtin_clz(v);
		for (int i = height ; i >= 1 ; i--) {
			propagate(v >> i);
		}
	}

public:
	dualSegmentTree() {}
	dualSegmentTree(int _N) : N(_N), dat(_N << 1, monoid::identity) {}
	dualSegmentTree(const std::vector<O>& A) : N((int)A.size()), dat(A.size() << 1, monoid::identity) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			dat[i + N] = A[i];
		}
	}

	O operator[](int i) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		return dat[i];
	}

	void set(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = value;
	}

	void update(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = monoid::operation(dat[i], value);
	}

	void update(int l, int r, const O& value) {
		assert(0 <= l and l < N);
		assert(l <= r and r <= N);
		if (l == r) {
			return;
		}
		l += N; r += N;
		push(l); push(r - 1);
		for ( ; l < r ; l = parent(l), r = parent(r)) {
			if (l & 1) {
				dat[l] = monoid::operation(dat[l], value);
				l++;
			}
			if (r & 1) {
				r--;
				dat[r] = monoid::operation(dat[r], value);
			}
		}
	}

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

} // namespace 

Back to top page