Lazy Segment Tree

Info

Monoidの区間fold、区間更新が\(O(\log{n})\)でできるデータ構造

Complexity

構築 - \(O(n)\)
区間更新 - \(O(\log{n})\)
区間fold - \(O(\log{n})\)

Interface

LazySegmentTree<M,OM>(int n) モノイド\(M\)、作用素\(OM\)、大きさ\(n\)で初期化する
[i] \(i\)番目の要素への参照を返す(最初のbuild()の前に事前に初期化するときに使う)
build() セグ木を構築する(すべての要素が単位元で初期化の場合も使う)
update(int l,int r,OM a) \([l,r)\)の区間に作用素\(a\)を適用する
fold(int l,int r) 区間\([l,r)\)をfoldした値を返す

Interface(Monoid)

I() 単位元を返す
f(M lhs, M rhs) モノイド間の演算\(f:(M,M)\rightarrow M\)

Interface(Operator Monoid)

I() 単位元を返す
g(M m, OM om) モノイドに作用素を適用するときの演算\(g:(M,OM)\rightarrow M\)
h(OM first, OM second) 作用素間の演算\(h:(OM,OM)\rightarrow OM\)

Code

using lnt=long long;
/* <LazySegmentTree> */

template<typename M, typename OM>
struct LazySegmentTree
{
	int n,h;
	std::vector<M> data; std::vector<OM> lazy;
	LazySegmentTree(int N) : n(1),h(0) { while(n<N) n<<=1,h++; data.assign(n<<1,M::I()); lazy.assign(n,OM::I()); }
	M& operator[](int i) { return data[i+n]; } // unsafe. use only with build()
	void build() { for(int i=n-1;i>0;i--) data[i]=M::f(data[i<<1],data[i<<1|1]); } // build() even when all I
	void apply(int i, const OM& o) { if(i<n) lazy[i]=OM::h(lazy[i],o); data[i]=OM::g(data[i],o); }
	void propagate(int i) { if(lazy[i].alive) { apply(i<<1,lazy[i]); apply(i<<1|1,lazy[i]); lazy[i]=OM::I(); } }
	void thrust(int i) { for(int j=h;j>0;j--) propagate(i>>j); }
	void recalc(int i) { for(;i>1;i>>=1) data[i>>1]=M::f(data[i],data[i^1]); }
	void update(int l, int r, const OM& o) {
		l+=n;r+=n; int l0=l/(l&-l),r0=r/(r&-r); thrust(l0); thrust(r0-1);
		for(;l<r;l>>=1,r>>=1) { if(l&1) apply(l++,o); if(r&1) apply(--r,o); }
		recalc(l0); recalc(r0-1);
	}
	M fold(int l, int r) {
		l+=n;r+=n; int l0=l/(l&-l),r0=r/(r&-r); thrust(l0); thrust(r0-1); recalc(l0); recalc(r0-1);
		M L=M::I(),R=M::I(); for(;l<r;l>>=1,r>>=1) { if(l&1) L=M::f(L,data[l++]); if(r&1) R=M::f(data[--r],R); }
		return M::f(L,R);
	}
	M get(int i) { return fold(i,i+1); }
};

/* <LazySegmentTree> */

/* <LazySegmentTree::RangeAffineRangeSum> */
template<typename T=lnt>
struct RangeAffineRangeSum
{
	struct M
	{
		T v; int n;
		static M I() { return M(0,1); }
		M(T v, int n=1) : v(v),n(n) {}
		static M f(const M& lhs, const M& rhs) { return M(lhs.v+rhs.v,lhs.n+rhs.n); }
		operator T() const { return v; }
	};

	struct OM
	{
		T a, b; bool alive;
		static OM I() { return OM(); }
		OM() : alive(false) {}
		OM(T a, T b) : a(a),b(b),alive(true) {}
		static M g(const M& m, const OM& om) { if(om.alive) return M(m.v*om.a+T(m.n)*om.b,m.n); else return m; }
		static OM h(const OM& first, const OM& second) {
			if(first.alive&&second.alive) return OM(first.a*second.a, first.b*second.a+second.b);
			return (first.alive)?first:second;
		}
	};
};
/* <LazySegmentTree::RangeAffineRangeSum> */

/* <LazySegmentTree::RangeAffineRangeMinMax> */
// untested
template<typename T=lnt>
struct RangeAffineRangeMinMax
{
	struct M
	{
		struct V
		{
			T v; int i;
			operator T() const { return v; } 
			V(T v, int i=-1) : v(v),i(i) {}
		};
		V min, max;
		static M I() { return M(std::numeric_limits<T>::max(),std::numeric_limits<T>::min()); }
		M(T v, int i=-1) : min(v,i),max(v,i) {}
		M(V min,V max) : min(min),max(max) {}
		static M f(const M& lhs, const M& rhs) {
			return M((lhs.min.v<rhs.min.v)?lhs.min:rhs.min, (rhs.max.v<lhs.max.v)?lhs.max:rhs.max);
		}
	};

	struct OM
	{
		T a, b; bool alive;
		static OM I() { return OM(); }
		OM() : alive(false) {}
		OM(T a, T b) : a(a),b(b),alive(true) {}
		static M g(M m, const OM& om) {
			if(om.alive) {
				if(om.a<0) std::swap(m.min,m.max);
				m.min.v*=om.a; m.min.v+=om.b;
				m.max.v*=om.a; m.max.v+=om.b;
				return m;
			} else return m;
		}
		static OM h(const OM& first, const OM& second) {
			if(first.alive&&second.alive) return OM(first.a*second.a, first.b*second.a+second.b);
			return (first.alive)?first:second;
		}
	};
};
/* <LazySegmentTree::RangeAffineRangeMinMax> */

Examples

using T=RangeAffineRangeSum<int>;
LazySegmentTree<T::M,T::OM> seg(10);

for(int i=0;i<10;i++) seg[i]=i;
seg.build();

std::cout << seg.fold(2,5) << '\n'; // 9

seg.update(2,4,T::OM(100,-50)); // x=x*100+(-50)

std::cout << seg.fold(2,5) << '\n'; // 404