쉽고 짧고 빠른, 세그먼트 트리 레이지 프로퍼게이션 & 비츠

lazyseg.cpp

/* struct node { ... }; */
int N;
node A[1<<LG_SZ];
void qry(int s=0, int e=N-1, int i=1) {
	if(l<=s && e<=r && A[i].apply(e-s+1)) return;
	int m=s+e>>1;
	A[i*2].down(A[i], m-s+1);
	A[i*2+1].down(A[i], e-m);
	if(l<=m) qry(s, m, i*2);
	if(r>m) qry(m+1, e, i*2+1);
	A[i]=A[i*2]+A[i*2+1];
}

lazyseg_struct.cpp

/* struct node { ... }; */
struct seg {
	int N;
	vector<node> A;
	seg(int n): N(n), A(1<<33-__builtin_clz(N)) { t=-1, l=0, r=N-1; qry(); }
	void qry(int s, int e, int i) {
		if(l<=s && e<=r && A[i].apply(e-s+1)) return;
		int m=s+e>>1;
		A[i*2].down(A[i], m-s+1);
		A[i*2+1].down(A[i], e-m);
		if(l<=m) qry(s, m, i*2);
		if(r>m) qry(m+1, e, i*2+1);
		A[i]=A[i*2]+A[i*2+1];
	}
	void qry() { qry(0, N-1, 1); }
};

node.cpp

/* query variables */;
struct node {
	/* member variables */
	inline node operator+(const node& rhs) const {
		return {/* merge */};
	}
	inline void down(const node& rhs, int sz) {
		/* propagate */
	}
	inline bool apply(int sz) {
		/* apply and build query */
	}
};

seqquery28.cpp

#include <bits/stdc++.h>
using namespace std;

int N, Q, t=-1, l, r=1e9; long x;
struct node {
	long sum, lz, mx, mn;
	inline node operator+(const node& rhs) const {
		return {sum+rhs.sum, 0, max(mx, rhs.mx), min(mn, rhs.mn)};
	}
	inline void down(const node& rhs, int sz) {
		if(rhs.mx==rhs.mn) sum=rhs.mx*sz, mx=rhs.mx, mn=rhs.mn;
		else lz+=rhs.lz, sum+=rhs.lz*sz, mx+=rhs.lz, mn+=rhs.lz;
	}
	inline bool apply(int sz) {
		if(t==-1) {
			if(sz>1) return false;
			cin>>sum; mx=mn=sum;
			return true;
		}
		if(t==3) { x+=sum; return true; }
		if(t==1) { sum+=x*sz, lz+=x, mx+=x, mn+=x; return true; }
		if(mx-mn>1) return false;
		long m=sqrt(mx);
		mn=sqrt(mn);
		if(m==mn) sum=m*sz;
		else sum+=(m-mx)*sz, lz+=m-mx;
		mx=m;
		return true;
	}
} A[1<<17+1];

void qry(int s=0, int e=N-1, int i=1) {
	if(l<=s && e<=r && A[i].apply(e-s+1)) return;
	int m=s+e>>1;
	A[i*2].down(A[i], m-s+1);
	A[i*2+1].down(A[i], e-m);
	if(l<=m) qry(s, m, i*2);
	if(r>m) qry(m+1, e, i*2+1);
	A[i]=A[i*2]+A[i*2+1];
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N;
	qry();
	cin>>Q;
	while(Q--) {
		cin>>t>>l>>r; --l, --r, x=0;
		if(t==1) cin>>x;
		qry();
		if(t==3) cout<<x<<'\n';
	}
}

seqquery28_struct.cpp

#include <bits/stdc++.h>
using namespace std;

int t, l, r; long x;
struct node {
	long sum, lz, mx, mn;
	inline node operator+(const node& rhs) const {
		return {sum+rhs.sum, 0, max(mx, rhs.mx), min(mn, rhs.mn)};
	}
	inline void down(const node& rhs, int sz) {
		if(rhs.mx==rhs.mn) sum=rhs.mx*sz, mx=rhs.mx, mn=rhs.mn;
		else lz+=rhs.lz, sum+=rhs.lz*sz, mx+=rhs.lz, mn+=rhs.lz;
	}
	inline bool apply(int sz) {
		if(t==-1) {
			if(sz>1) return false;
			cin>>sum; mx=mn=sum;
			return true;
		}
		if(t==3) { x+=sum; return true; }
		if(t==1) { sum+=x*sz, lz+=x, mx+=x, mn+=x; return true; }
		if(mx-mn>1) return false;
		long m=sqrt(mx);
		mn=sqrt(mn);
		if(m==mn) sum=m*sz;
		else sum+=(m-mx)*sz, lz+=m-mx;
		mx=m;
		return true;
	}
};

struct seg {
	int N;
	vector<node> A;
	seg(int n): N(n), A(1<<33-__builtin_clz(N)) { t=-1, l=0, r=N-1; qry(); }
	void qry(int s, int e, int i) {
		if(l<=s && e<=r && A[i].apply(e-s+1)) return;
		int m=s+e>>1;
		A[i*2].down(A[i], m-s+1);
		A[i*2+1].down(A[i], e-m);
		if(l<=m) qry(s, m, i*2);
		if(r>m) qry(m+1, e, i*2+1);
		A[i]=A[i*2]+A[i*2+1];
	}
	void qry() { qry(0, N-1, 1); }
};

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, Q;
	cin>>N;
	seg T(N);
	cin>>Q;
	while(Q--) {
		cin>>t>>l>>r; --l, --r, x=0;
		if(t==1) cin>>x;
		T.qry();
		if(t==3) cout<<x<<'\n';
	}
}

설명:

• node.down은 부모 노드에서 현재 노드로 값을 propagate 한다.
  • 인자는 기본적으로 현재 노드가 담당중인 구간의 크기이나, 문제에 따라 바꾸거나 없애도 무방하다.
• node.apply는 쿼리를 실행하며 tag_condition 역할을 한다.
  • 쿼리에는 구간의 값을 구하거나 업데이트하는 모든 행위가 포함되며, 이는 세그먼트 트리를 빌드하는 것도(!) 포함된다.
  • 쿼리의 타입, 정보 및 결과는 코드의 간결함 및 PS계의 전체적인 지향에 따라 모두 전역변수에 저장한다.
  • 반환값이 거짓이면 자식으로 더 깊이 내려가고, 참이면 해당 노드에서 마무리한다.
  • 세그비츠가 아닌 일반적인 레이지 세그는 세그를 빌드할 때를 제외하곤 모두 참을 반환하면 된다.
• 전역변수 l, r을 설정하고 qry를 호출하면 [l, r] 구간(0-indexed)에 포함된 node들이 apply 된다.

장점:

• 쉽고 짧고 빠르다.
• qry 호출하는 부분이랑 node 구조체만 짜면 된다.

단점:

• 표준 입력 외의 방법으로 세그를 빌드하려면 직접 고쳐야 된다.

고민:

• apply에서 전역변수를 여러 개 사용하는 경우 속도가 약간 느려진다. 왜지
• 구조체로 감싼 것보다 안 감싼 게 더 빠르다. 메모리 할당이나 초기화에서 차이가 나는 것 같은데 정확힌 모르겠음