segtree_lazy(遅延評価セグメント木) (tree/segtree_lazy.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-06-08 22:59:42+09:00

なにこれ

区間取得・区間更新可能な要素数 $n$ のセグメント木． 各要素について更新時の作用素を保持しておき，値が必要になるタイミングで要素と作用素をマージする．

コンストラクタ

• segtree_lazy(n, op, f_upd, f_lz, ex, em)：要素数 n のセグメント木を構築する．
• segtree_lazy(v, op, f_upd, f_lz, ex, em)：配列 v の要素を持つセグメント木を構築する．

op(l, r) は要素の二項演算，f_upd(x, m) は要素と作用素をマージする二項演算，f_lz(l, r) は作用素を蓄積するときの二項演算（マージ順は l $\to$ r）． ex は要素の単位元，em は作用素の単位元． $n \leq 10^8$ 程度．

メンバ関数

• update(idx, val)：idx 番目の要素を val との二項演算 f_upd の結果に更新する．
• update(L, R, val)：[L, R) 番目の要素を val との二項演算 f_upd の結果に更新する．
• get(idx)：idx 番目の要素を返す．
• get(L, R)：区間 [L, R) の二項演算 op の結果を返す．

idx, L, R は 0-indexed である．

計算量

各二項演算の計算量を $O(1)$ と仮定したときの計算量を示す．

• コンストラクタ：$O(n)$
• update(idx, val)：$O(\log n)$
• update(L, R, val)：$O(\log n)$
• get(idx)：$O(\log n)$
• get(L, R)：$O(\log n)$

気を付けるべき使用例

Range Matrix Multiplication

ある行列Aに行列Bを掛ける操作をすることは，Bを左から掛けることに相当する．

using mat = matrix<T>;

auto op = /* 任意の範囲取得クエリ */;
mat ex = /* opの単位元 */;

/* ある行列Aに行列Bを掛ける操作をすることは、Bを左から掛けることに相当する */
auto f_upd = [](mat A, mat B) { return B * A; };
mat em = mat::Indentity();

auto seg = segtree_lazy(v /* or N */, op, f_upd, f_upd, ex, em);

Verified with

• test/aoj_DSL_2_F.cpp
• test/aoj_DSL_2_H.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T, typename M> struct segtree_lazy {
	using F = function<T(T, T)>;
	using FU = function<T(T, M)>;
	using FM = function<M(M, M)>;

private:
	int siz = 1, N;
	vector<T> node;
	vector<M> lazy;
	const F op;
	const FU f_upd;
	const FM f_lz;
	const T ex;
	const M em;

public:
	segtree_lazy(int n, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
		N(n), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, ex);
		lazy.resize(2 * siz - 1, em);
	}
	segtree_lazy(vector<T> &v, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
		N(v.size()), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, ex);
		lazy.resize(2 * siz - 1, em);
		for(int i = 0; i < N; i++) node[siz - 1 + i] = v[i];
		for(int i = siz - 2; i >= 0; i--) node[i] = op(node[2 * i + 1], node[2 * i + 2]);
	}

	void update(int idx, M val) {
		assert(0 <= idx && idx < N);
		upd__(idx, idx + 1, 0, val, 0, siz);
	}
	void update(int L, int R, M val) {
		if(L < 0) L = 0;
		if(R > N) R = N;
		assert(L < R);
		upd__(L, R, 0, val, 0, siz);
	}

	T get(int idx) {
		assert(0 <= idx && idx < N);
		return get__(idx, idx + 1, 0, 0, siz);
	}
	T get(int L, int R) {
		if(L < 0) L = 0;
		if(R > N) R = N;
		assert(L < R);
		return get__(L, R, 0, 0, siz);
	}

private:
	void eval(int idx) {
		if(lazy[idx] == em) return;
		if(idx < siz - 1) {
			lazy[2 * idx + 1] = f_lz(lazy[2 * idx + 1], lazy[idx]);
			lazy[2 * idx + 2] = f_lz(lazy[2 * idx + 2], lazy[idx]);
		}
		node[idx] = f_upd(node[idx], lazy[idx]);
		lazy[idx] = em;
	}

	void upd__(int L, int R, int idx, M val, int l, int r) {
		eval(idx);
		if(r <= L || R <= l) return;
		if(L <= l && r <= R) {
			lazy[idx] = f_lz(lazy[idx], val);
			eval(idx);
		}
		else {
			upd__(L, R, 2 * idx + 1, val, l, (l + r) / 2);
			upd__(L, R, 2 * idx + 2, val, (l + r) / 2, r);
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}

	T get__(int L, int R, int idx, int l, int r) {
		if(r <= L || R <= l) return ex;
		eval(idx);
		if(L <= l && r <= R) return node[idx];
		T vl = get__(L, R, 2 * idx + 1, l, (l + r) / 2);
		T vr = get__(L, R, 2 * idx + 2, (l + r) / 2, r);
		return op(vl, vr);
	}
};

#line 2 "tree/segtree_lazy.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T, typename M> struct segtree_lazy {
	using F = function<T(T, T)>;
	using FU = function<T(T, M)>;
	using FM = function<M(M, M)>;

private:
	int siz = 1, N;
	vector<T> node;
	vector<M> lazy;
	const F op;
	const FU f_upd;
	const FM f_lz;
	const T ex;
	const M em;

public:
	segtree_lazy(int n, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
		N(n), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, ex);
		lazy.resize(2 * siz - 1, em);
	}
	segtree_lazy(vector<T> &v, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
		N(v.size()), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
		while(siz < N) siz <<= 1;
		node.resize(2 * siz - 1, ex);
		lazy.resize(2 * siz - 1, em);
		for(int i = 0; i < N; i++) node[siz - 1 + i] = v[i];
		for(int i = siz - 2; i >= 0; i--) node[i] = op(node[2 * i + 1], node[2 * i + 2]);
	}

	void update(int idx, M val) {
		assert(0 <= idx && idx < N);
		upd__(idx, idx + 1, 0, val, 0, siz);
	}
	void update(int L, int R, M val) {
		if(L < 0) L = 0;
		if(R > N) R = N;
		assert(L < R);
		upd__(L, R, 0, val, 0, siz);
	}

	T get(int idx) {
		assert(0 <= idx && idx < N);
		return get__(idx, idx + 1, 0, 0, siz);
	}
	T get(int L, int R) {
		if(L < 0) L = 0;
		if(R > N) R = N;
		assert(L < R);
		return get__(L, R, 0, 0, siz);
	}

private:
	void eval(int idx) {
		if(lazy[idx] == em) return;
		if(idx < siz - 1) {
			lazy[2 * idx + 1] = f_lz(lazy[2 * idx + 1], lazy[idx]);
			lazy[2 * idx + 2] = f_lz(lazy[2 * idx + 2], lazy[idx]);
		}
		node[idx] = f_upd(node[idx], lazy[idx]);
		lazy[idx] = em;
	}

	void upd__(int L, int R, int idx, M val, int l, int r) {
		eval(idx);
		if(r <= L || R <= l) return;
		if(L <= l && r <= R) {
			lazy[idx] = f_lz(lazy[idx], val);
			eval(idx);
		}
		else {
			upd__(L, R, 2 * idx + 1, val, l, (l + r) / 2);
			upd__(L, R, 2 * idx + 2, val, (l + r) / 2, r);
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}

	T get__(int L, int R, int idx, int l, int r) {
		if(r <= L || R <= l) return ex;
		eval(idx);
		if(L <= l && r <= R) return node[idx];
		T vl = get__(L, R, 2 * idx + 1, l, (l + r) / 2);
		T vr = get__(L, R, 2 * idx + 2, (l + r) / 2, r);
		return op(vl, vr);
	}
};

Back to top page