NyaaLIB::DS_LazySegmentTree

遅延評価セグメント木 (Lazy Segment Tree)
任意区間のクエリを計算量 $O(\log N)$ で処理する

https://betrue12.hateblo.jp/entry/2020/09/22/194541
https://atcoder.github.io/ac-library/production/document_ja/lazysegtree.html
https://betrue12.hateblo.jp/entry/2020/09/23/005940

範囲更新・範囲合計取得（RUQ・RSUMQ）

// LST定義（範囲更新RUQ、範囲合計取得RSUMQ）
// 半開区間[0, N)の遅延セグメント木
// DS_LST_USUM lst(std::vector<DataUSUM>(N, { 0,1 }));
// apply(l, r, x); 半開区間[l,r)をxに更新
// prod(l, r).value; 半開区間[l,r)の合計を取得
using LazyUSUM = long long;
struct DataUSUM { long long value; long long size; };
const long long ID_USUM = (long long)(2e9);
DataUSUM op_usum(DataUSUM a, DataUSUM b) { return { a.value + b.value, a.size + b.size }; }
DataUSUM el_usum() { return { 0, 0 }; }
DataUSUM mapping_usum(LazyUSUM f, DataUSUM x) { if (f != ID_USUM) x.value = (long long)x.size * f; return x; }
LazyUSUM composition_usum(LazyUSUM f, LazyUSUM g) { return (f == ID_USUM ? g : f); }
LazyUSUM id_usum() { return ID_USUM; }
using DS_LST_USUM = DS_LazySegmentTree<DataUSUM, op_usum, el_usum, LazyUSUM, mapping_usum, composition_usum, id_usum>;

int main()
{
	long long N = 100;
	DS_LST_USUM lst(std::vector<DataUSUM>(N, { 0,1 }));
	lst.apply(10, 31, 1000); // 半開区間[10,31)の値を1000に更新
	std::cout << lst.prod(10, 31).value; // 半開区間[10,31)の合計取得
	return 0;
}

実装例
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6817363

範囲加算・範囲合計取得（RAQ・RSQ）

// LST定義（範囲加算RAQ、範囲合計取得RSQ）
// 半開区間[0, N)の遅延セグメント木（値0、幅1で初期化）
// DS_NyaaLST_AS lst(vec<DataAS>(N, { 0,1 }));
// apply(l, r, x); 半開区間[l,r)にxを加算
// prod(l, r).value; 半開区間[l,r)の合計を取得
using LazyASUM = long long;
struct DataASUM { long long value; long long size; };
DataASUM op_asum(DataASUM a, DataASUM b) { return { a.value + b.value, a.size + b.size }; }
DataASUM el_asum() { return { 0, 0 }; }
DataASUM mapping_asum(LazyASUM f, DataASUM x) { return { x.value + f * x.size, x.size }; }
LazyASUM composition_asum(LazyASUM f, LazyASUM g) { return f + g; }
LazyASUM id_asum() { return 0; }
using DS_LST_ASUM = DS_LazySegmentTree<DataASUM, op_asum, el_asum, LazyASUM, mapping_asum, composition_asum, id_asum>;

int main()
{
	long long N = 100;
	DS_LST_ASUM lst(vec<DataASUM>(N, { 0,1 }));
	lst.apply(10, 31, 1000); // 半開区間[10,31)の値に1000を加算
	cout << lst.prod(10, 31).value; // 半開区間[10,31)の合計取得
	return 0;
}

実装例
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6469556

範囲更新・範囲最大値取得（RUQ・RMQ）

// LST定義（範囲更新RUQ、範囲最大値取得RMQ）
// 半開区間[0, N)の遅延セグメント木（初期値 0）
// DS_NyaaLST_UMAX(std::vector<DataUMAX>(N, 0));
// apply(l, r, x); 半開区間[l,r)をxに更新
// prod(l, r); 半開区間[l,r)の最大値を取得
using DataUMAX = long long;
using TypeUMAX = long long;
const DataUMAX INF_UMAX = DataUMAX(8e18);
const TypeUMAX ID_UMAX = TypeUMAX(8e18);
DataUMAX op_umax(DataUMAX a, DataUMAX b) { return std::max(a, b); }
DataUMAX el_umax() { return -INF_UMAX; }
DataUMAX mapping_umax(TypeUMAX f, DataUMAX x) { return (f == ID_UMAX ? x : f); }
TypeUMAX composition_umax(TypeUMAX f, TypeUMAX g) { return (f == ID_UMAX ? g : f); }
TypeUMAX id_umax() { return ID_UMAX; }
using DS_NyaaLST_UMAX = DS_NyaaLST<DataUMAX, op_umax, el_umax, TypeUMAX, mapping_umax, composition_umax, id_umax>;

int main()
{
	long long N = 100;
	DS_NyaaLST_UMAX lst(std::vector<DataUMAX>(N, 0));
	lst.apply(10, 31, 1000); // 半開区間[10,31)の値を1000に更新
	cout << lst.prod(10, 31); // 半開区間[10,31)の最大値取得
	return 0;
}

実装例
https://atcoder.jp/contests/typical90/submissions/24723691

範囲加算・範囲最大値取得（RAQ・RMQ）

// LST定義（範囲加算RAQ、範囲最大値取得RMQ）
// 半開区間[0, N)の遅延セグメント木（初期値 0）
// DS_NyaaLST_AMAX(std::vector<DataAMAX>(N, 0));
// apply(l, r, x); 半開区間[l,r)にxを加算
// prod(l, r); 半開区間[l,r)の最大値を取得
using DataAMAX = long long;
using TypeAMAX = long long;
const DataAMAX INF_AMAX = DataAMAX(8e18);
const TypeAMAX ID_AMAX = TypeAMAX(8e18);
DataAMAX op_amax(DataAMAX a, DataAMAX b) { return std::max(a, b); }
DataAMAX el_amax() { return -INF_AMAX; }
DataAMAX mapping_amax(TypeAMAX f, DataAMAX x) { return f + x; }
TypeAMAX composition_amax(TypeAMAX f, TypeAMAX g) { return f + g; }
TypeAMAX id_amax() { return ID_AMAX; }
using DS_NyaaLST_AMAX = DS_NyaaLST<DataAMAX, op_amax, el_amax, TypeAMAX, mapping_amax, composition_amax, id_amax>;

int main()
{
	long long N = 100;
	DS_NyaaLST_AMAX lst(std::vector<DataAMAX>(N, 0));
	lst.apply(10, 31, 1000); // 半開区間[10,31)の値を1000に加算
	cout << lst.prod(10, 31); // 半開区間[10,31)の最大値取得
	return 0;
}

実装例

範囲XOR更新・範囲合計取得（RxorQ・RSQ）

実装例
https://atcoder.jp/contests/abc185/submissions/30338386

#include <bits/stdc++.h>

namespace NyaaLIB
{
	/*
	* 遅延評価セグメント木ライブラリ
	* 色々な区間クエリをO(log N)で処理する
	*/

	template <class S, S(*op)(S, S), S(*e)(), class F, S(*mapping)(F, S), F(*composition)(F, F), F(*id)()> struct DS_LazySegmentTree
	{
		using ll = long long;
		using ull = unsigned long long;
		DS_LazySegmentTree() : DS_LazySegmentTree(0) {}
		DS_LazySegmentTree(ll n) : DS_LazySegmentTree(std::vector<S>(n, e())) {}
		DS_LazySegmentTree(ll n, S init) : DS_LazySegmentTree(std::vector<S>(n, init)) {}
		DS_LazySegmentTree(const std::vector<S>& v) : _n((ll)v.size())
		{
			log = ceil_pow2(_n);
			size = 1LL << log;
			d = std::vector<S>((ll)2 * size, e());
			lz = std::vector<F>(size, id());
			for (auto i = 0LL; i < _n; i++) d[size + i] = v[i];
			for (auto i = size - 1; i >= 1; i--) update(i);
		}

		void set(ll p, S x)
		{
			assert(0 <= p && p < _n);
			p += size;
			for (ll i = log; i >= 1; i--) push(p >> i);
			d[p] = x;
			for (ll i = 1; i <= log; i++) update(p >> i);
		}

		S get(ll p)
		{
			assert(0 <= p && p < _n);
			p += size;
			for (ll i = log; i >= 1; i--) push(p >> i);
			return d[p];
		}

		S prod(ll l, ll r)
		{
			assert(0 <= l && l <= r && r <= _n);
			if (l == r) return e();
			l += size;
			r += size;
			for (ll i = log; i >= 1; i--)
			{
				if (((l >> i) << i) != l) push(l >> i);
				if (((r >> i) << i) != r) push(r >> i);
			}
			S sml = e(), smr = e();
			while (l < r)
			{
				if (l & 1) sml = op(sml, d[l++]);
				if (r & 1) smr = op(d[--r], smr);
				l >>= 1;
				r >>= 1;
			}
			return op(sml, smr);
		}

		S all_prod() { return d[1]; }

		void apply(ll p, F f)
		{
			assert(0 <= p && p < _n);
			p += size;
			for (ll i = log; i >= 1; i--) push(p >> i);
			d[p] = mapping(f, d[p]);
			for (ll i = 1; i <= log; i++) update(p >> i);
		}

		void apply(ll l, ll r, F f)
		{
			assert(0 <= l && l <= r && r <= _n);
			if (l == r) return;
			l += size;
			r += size;
			for (ll i = log; i >= 1; i--)
			{
				if (((l >> i) << i) != l) push(l >> i);
				if (((r >> i) << i) != r) push((r - 1) >> i);
			}
			{
				ll l2 = l, r2 = r;
				while (l < r)
				{
					if (l & 1) all_apply(l++, f);
					if (r & 1) all_apply(--r, f);
					l >>= 1;
					r >>= 1;
				}
				l = l2;
				r = r2;
			}
			for (ll i = 1; i <= log; i++)
			{
				if (((l >> i) << i) != l) update(l >> i);
				if (((r >> i) << i) != r) update((r - 1) >> i);
			}
		}

		template <bool (*g)(S)> ll max_right(ll l) { return max_right(l, [](S x) { return g(x); }); }

		template <class G> ll max_right(ll l, G g)
		{
			assert(0 <= l && l <= _n);
			assert(g(e()));
			if (l == _n) return _n;
			l += size;
			for (ll i = log; i >= 1; i--) push(l >> i);
			S sm = e();
			do {
				while (l % 2 == 0) l >>= 1;
				if (!g(op(sm, d[l])))
				{
					while (l < size)
					{
						push(l);
						l = (2 * l);
						if (g(op(sm, d[l]))) sm = op(sm, d[l]), l++;
					}
					return l - size;
				}
				sm = op(sm, d[l]), l++;
			} while ((l & -l) != l);
			return _n;
		}

		template <bool (*g)(S)> ll min_left(ll r) { return min_left(r, [](S x) { return g(x); }); }

		template <class G> ll min_left(ll r, G g) {
			assert(0 <= r && r <= _n);
			assert(g(e()));
			if (r == 0) return 0;
			r += size;
			for (ll i = log; i >= 1; i--) push((r - 1) >> i);
			S sm = e();
			do {
				r--;
				while (r > 1 && (r % 2)) r >>= 1;
				if (!g(op(d[r], sm)))
				{
					while (r < size)
					{
						push(r);
						r = (2 * r + 1);
						if (g(op(d[r], sm))) sm = op(d[r], sm), r--;
					}
					return r + 1 - size;
				}
				sm = op(d[r], sm);
			} while ((r & -r) != r);
			return 0;
		}
	private:
		ll _n, size, log;
		std::vector<S> d;
		std::vector<F> lz;
		void update(ll k) { d[k] = op(d[2LL * k], d[2LL * k + 1]); }
		void all_apply(ll k, F f)
		{
			d[k] = mapping(f, d[k]);
			if (k < size) lz[k] = composition(f, lz[k]);
		}
		void push(ll k)
		{
			all_apply(2 * k, lz[k]);
			all_apply(2 * k + 1, lz[k]);
			lz[k] = id();
		}
		// @param n `0 <= n`
		// @return minimum non-negative `x` s.t. `n <= 2**x`
		ll ceil_pow2(ll n)
		{
			ll x = 0;
			while ((1LLU << x) < ull(n)) x++;
			return x;
		}
	};
}

7K12 blog

猫でも分かる何か

NyaaLIB::DS_LazySegmentTree