세그먼트 트리의 정의
세그먼트 트리는 구간에 대한 질의를 다루는 트리 자료구조인데, 이러한 세그트리를 활용해서 문제를 해결하기 위해서는
- 구간에 항등원이 존재해야함
- 각 구간에서의 결합법칙이 성립해야 함.
이라는 두 가지 조건이 필요합니다.
항등원은 base case로서 아무런 처리가 이루어지지 않았을때 기본적으로 가지게 되는 값이며, 또한 lazy propergation에서의 lazy트리에 대한 기본 값이기도 합니다.
구간에서의 결합법칙이 성립하면 세그먼트 트리에서
- 왼쪽 자식 노드(구간의 좌측 절반)
- 오른쪽 자식 노드(구간의 우측 절반)
이 두 노드를 서로 결합하여 자기 자신의 노드를 갱신할 수 있고, 이는 세그트리를 구성할때 리프 노드에서부터 결합해 올라오는 구현을 위해 필요한 조건입니다.
BOJ 10070 벽
이 문제에서 배열의 원소 $arr_i$ 에 대하여 들어오는 구간 쿼리는 두 가지 종류가 있는데,
첫번째는 $arr_i = MAX(arr_i, K)$ 로 변경하는 연산이며
두번째는 $arr_i = MIN(arr_i, K)$ 으로 변경하는 연산입니다.
이 연산을 결합법칙이 가능한 형태로 어떻게 정의할 수 있을까요?
이 문제에서 까다로워지는 부분은 쿼리가 실제 정답 배열의 값을 갱신할 수도 있고, 갱신하지 않을 수도 있다는 부분에 있습니다. 이를 매끄럽게 처리하기 위해서, 쿼리를 구간의 형태로 바꿔보도록 하겠습니다.
쿼리를 구간으로 다루는 발상
입력 예제에서의 첫 번째 쿼리가 들어왔다고 가정해 봅시다. 만약 기존 배열에서 4보다 높이가 더 높은 원소가 있다면, 해당 원소는 갱신되지 않아야 합니다.
이때, 해당 쿼리가 실행된 이후 시점 을 고민해 보아야 합니다.
해당 쿼리가 실행된 이후, 정답으로써 고려될 수 있는 값들은 모두 [4,inf] 범위에 있다는걸 생각해 볼 수 있습니다.
이제 이 정답으로써 고려될 수 있는 값 그 자체를 쿼리로 정의합니다.
다시 말해 쿼리 l,r,{low,up} 는 [l,r] 구간에서 제한되는 구간을 구간을 [low,up] 범위로 줄이라는 의미가 됩니다.
이렇게 정의한다면, 첫번째 쿼리는 {K,inf} 구간에 대한 쿼리가 되고, 두번째 쿼리는 {0,K} 구간에 대한 쿼리가 됩니다.
쿼리를 세그트리에 결합연산하기
{low,up} 쿼리 B 를 기존의 세그트리에 저장된 값 {low,up} A 와 결합연산 해봅시다. 편의성을 위해 기존 구간 A에 B를 A+B로 결합하는 것으로 방향을 한정짓겠습니다.
둘을 결합하는 것은 앞선 글에서 설명하였듯 덧셈 연산에 대한 연산자 오버로딩을 통해 구현하면 편리합니다.
박성훈
height operator+(height A, height B){
if(A.up < B.low) return {B.low, B.low};
if(B.up < A.low) return {B.up, B.up};
return {max(A.low, B.low), min(A.up, B.up)};
}덧셈 연산 구현의 마지막 줄은 자명합니다. 두 구간 사이의 교집합을 취하고 있습니다. 첫번째 줄과 두번째 줄이 어떤 케이스일까요?
높이를 더하는 연산
기존 A 구간을 {0,4} 정도로 정의해보겠습니다. 다시 말해 쿼리가 진행되기 전 높이는 4보다 높을 수 없습니다.
그런데 B에 쿼리로 {5,inf} 가 들어왔습니다. 다시말해서 높이는 반드시 5보다는 커야 합니다. ( 지문에서의 첫 번째 쿼리 유형입니다 )
이 경우 A에 B를 결합하는 것이기 때문에 B를 존중해야 합니다. 따라서 결합된 구간의 low값은 5가 될 것입니다.
up값이 좀 흥미로운 부분인데, {0,4} 에 {5,inf} 를 결합한다는 것은 기존의 모든 구간이 5보다 작기 때문에, 지문에서 요구하는 바에 의하면 높이가 5로 통일되어야 합니다.
따라서, 이를 같이 고려할때 모든 높이는 5로 통일되어야 하고, 병합된 구간은 {5,5} 가 되어야 합니다.
높이를 빼는 연산
위 역시 높이를 더하는 연산과 동일하게 새로 들어온 쿼리 B를 존중하기 위해서,
병합된 구간은 새로 들어온 쿼리의 최대 높이값 이어야 합니다.
구조체 연산에 대한 부분은 아래와 같습니다.
struct height{
int low, up;
};
height operator+(height A, height B){
if(A.up < B.low) return {B.low, B.low};
if(B.up < A.low) return {B.up, B.up};
return {max(A.low, B.low), min(A.up, B.up)};
}
bool operator!=(height A, height B){
if(A.up == B.up && A.low == B.low) return false;
return true;
}
height tree[8901234];
height base = {0,998244353};레이지 세그먼트 트리
이제 구간에 대한 덧셈 쿼리를 정의했으니, 세그먼트 트리 및 레이지 세그먼트 트리를 작성할 수 있습니다.
이 문제에서 특이한 점은 구간 갱신 - 점 쿼리 구조를 띄고 있다는 점에 있습니다.
모든 출력을 위한 질의문이 점 쿼리로 한정되기 때문에, 세그트리에서 보다 넓은 구간에 대한 노드값을 항상 들고 있을 필요가 없고, 리프 노드의 값만 정확하게 유지해주면 됩니다.
따라서, 이 문제에서는 구현의 편의성을 위해 lazy[] 트리만을 들고 문제를 해결할 수 있습니다.
따라서 lazy[] 트리의 프로파게이션 연산 시에 원래 seg[] 트리에 이를 반영할 필요가 없고, 저는 lazy[] 트리를 그냥 tree[] 라고 이름붙여 구현하였습니다.
주의해야할 점으로는 리프노드에서는 프로파게이션 연산이 일어나지 않아야 추후 점 쿼리 때에 값을 정상적으로 가져올 수 있습니다.
void prop(int s, int e, int node){
int l = node*2;
int r = node*2+1;
if(s != e){
tree[l] = tree[l] + tree[node];
tree[r] = tree[r] + tree[node];
tree[node] = base;
}
return;
}프로파게이션 연산입니다.
부모노드인 node를 자식 노드인 l,r에 결합시켜 구간을 전파합니다.
+= 연산자에 대한 오버로딩이 되어있지 않으므로 반드시 저렇게 작성해야 합니다.
void update(int l, int r, height X, int s=1, int e=M, int node=1){
if(tree[node] != base) prop(s,e,node);
if(r<s || e<l) return;
if(l<=s && e<=r){
tree[node] = tree[node] + X;
return;
}
int mid = (s+e)/2;
update(l,r,X,s,mid,node*2);
update(l,r,X,mid+1,e,node*2+1);
return;
}
height query(int l, int r, int s=1, int e=M, int node=1){
if(tree[node] != base) prop(s,e,node);
if(r<s || e<l) return base;
if(l<=s && e<=r) return tree[node];
int mid = (s+e)/2;
return query(l,r,s,mid,node*2) + query(l,r,mid+1,e,node*2+1);
}구간 업데이트 + 점 쿼리입니다.
tree[node]에 입력으로 들어온 쿼리 X를 결합시킵니다.
첫번째 줄에 propagation 연산을 진행할지 말지를 판단하기 위한 != 연산자가 사용되는데, 이 또한 오버로딩 해주어야 합니다.
쿼리문의 경우 구간 쿼리에도 대응하고 있는데, 그냥 템플릿으로 짜놔서 그렇습니다. 별도로 점 쿼리에 특화된 형태로 작성하셔도 무방합니다.
여담
for(int i=1; i<=N; i++) cout << query(i,i).up << "\n";출력의 경우 위와 같이 처리하고 있는데, tree[] 를 처음 만드는 시점에서 초깃값이 {0,0} 으로 들어가 있기 때문에, 항상 query를 때린 후의 low와 up의 값이 같습니다. 따라서 up으로 출력하든 low로 출력하든 AC를 받을 수 있음을 확인했습니다.
전체 소스코드는 아래와 같습니다.
