segment tree의 lazy propagation : 스위치(BOJ 1395)

lazy propagation을 쉽게 말하자면, 구간 업데이트 쿼리를 빠른 시간 내에 처리하기 위해 lazy한 업데이트를 사용하는 것이다. 이게 뭔 소린가 하면, 업데이트를 안하고 존버까고 있다가, lazy배열의 값을 해당 노드를 필요로 하는 시점에서 update처리해주는 기법이다. 이러면 구간쿼리를 NlogN이 아닌, 다른 쿼리에 낑겨서 들어가기 때문에 logN으로 처리할 수 있다(물론 빅 오)

스위치 문제는 이러한 lazy propagation의 대표적인 예시 중 하나이다. 본인은 쿼리 문제 중 세그트리 관련 문제를 풀 때, 이 문제가 세그트리를 어떻게 써야 하는지부터 생각하는 법이다.

https://www.acmicpc.net/problem/1395

 

 

아래는 이 문제를 풀 때 생각한 순서이다.

1.세그트리는 구간 합 트리이다.

2.노드는 0 or 1로 처리한다.

3. 업데이트를 제외한 다른 쿼리는 구간 합 쿼리를 사용한다.

4. lazy propagation을 할 때, bool꼴로 자손에게 반전 여부를 전파한다.

5.끗

아래는 본인의 소스코드이다.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll N, M, tree[400001], lazy[400001];
void update_lazy(ll start, ll end, ll node){
	if(lazy[node]==1){
		tree[node]=(end-start+1)-tree[node];
		if(start!=end){
			lazy[node*2]=1-lazy[node*2];
			lazy[node*2+1]=1-lazy[node*2+1];
		}
		lazy[node]=0; // 반전시켰으니 반전 해제 
		// lazy에 따른 반전 전파 
	}
	return;
}
void reverse(ll start, ll end, ll node, ll first, ll second){
	update_lazy(start, end, node);
	if(second<start or first>end) return;
	if(start>=first and end<=second){
		tree[node]=(end-start+1)-tree[node];
		if(start!=end){
			lazy[node*2]=1-lazy[node*2];
			lazy[node*2+1]=1-lazy[node*2+1];
		} // lazy : reverse에 대한 boolian 정보를 저장한다. 
		return;
	}
	ll mid=(start+end)/2;
	reverse(start, mid, node*2, first, second);
	reverse(mid+1, end, node*2+1, first, second);
	tree[node]=tree[node*2]+tree[node*2+1];
	return;
}
ll sum(ll start, ll end, ll node, ll first, ll second){
	update_lazy(start, end, node);
	if(second<start or first>end) return 0;
	if(start>=first and end<=second) return tree[node];
	ll mid=(start+end)/2;
	return sum(start, mid, node*2, first, second)+sum(mid+1, end, node*2+1, first, second);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for(ll i=0;i<M;i++){
		ll O, S, T;
		cin >> O >> S >> T;
		if(O==0){
			reverse(1, N, 1, S, T);	
		}// 구간 업데이트 쿼리 Query
		else{
			cout << sum(1, N, 1, S, T) << '\n';
		}// 구간 합 쿼리 Query  
	}
}

매우 간단하다! 짜피 처음에는 모두 꺼져있으므로 세그트리의 init또한 필요없다.

sum 연산은 여타 다른 lazy propagation마냥 처리하면 된다.

처음에 boolian으로 lazy를 선언했다가, 그냥 long long int형으로 두었다. 저거 아마 boolian으로 해도 맞을거다. 이렇게 바꾼 이유? "맞왜틀? 맞왜틀?..."의 결과물이다.

Dev C++컴파일러는 놀랍게도 세그먼트 에러를 못잡아주는 약한 친구이므로, 이렇게 세그먼트 에러가 난다는 의심이 갈때에는 온라인 컴파일러를 사용하자. 본인은 인터페이스가 깔끔한 이 사이트를 사용한다.

https://www.programiz.com/cpp-programming/online-compiler/

Online C++ Compiler

이상으로 포스트를 마치겠다. 본인은 참고로 포인터랑 클래스를 못쓴다. 더 낫고 쾌적한 PS를 위해 본인은 이 두개를 배우러 간다. 그럼 안녕~