[P4] 백준 2934번 LRH 식물 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

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

문제를 봤을 때 이해가 잘 되지 않았는데 예시 그래프를 보고 이해 된 내용으로 시도했다.

 

 

전역 변수

• N : 좌표의 최대 범위를 저장할 상수 변수
• n : 식물을 심은 날의 수를 저장할 변수
• tree : 세그먼트 트리 정보를 저장할 배열
• lazy : 업데이트 정보를 저장할 배열

 

함수

1. propagate

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] += (e - s + 1) * lazy[node];
		if (s != e) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

 

lazy에 업데이트해야 할 값이 있다면 세그먼트 트리 업데이트를 진행하고 자식 노드로 전파하기 위한 함수

 

2. update

void update(int node, int s, int e, int L, int R, int val) {
	propagate(node, s, e);
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] += val;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, val);
	update(node * 2 + 1, mid + 1, e, L, R, val);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

 

실제로 세그먼트 트리 업데이트를 진행하기 위한 함수

 

3. query

int query(int node, int s, int e, int idx) {
	propagate(node, s, e);
	if (s == e) return tree[node];
	int mid = (s + e) / 2;
	if (idx <= mid) return query(node * 2, s, mid, idx);
	return query(node * 2 + 1, mid + 1, e, idx);
}

 

세그먼트 트리의 특정 노드에 저장된 값을 구하기 위한 함수

 

문제풀이

1. n값을 입력 받고, n개의 식물 정보를 입력 받아준다, 매 루프마다 변수 L, R에 좌표를 가져와 준다.
2. 변수 left, right에 query함수를 통해 세그먼트 트리의 L, R번 인덱스에 저장된 노드 값을 받아온다.
3. left + right를 한 값을 출력해 주고 줄 바꿈을 수행해 준다.
4. 세그먼트 트리의 L, R번 인덱스에 저장된 노드 값을 0으로 변경해 준다.
5. L과 R번 인덱스 사이의 노드값들을 순회하며 모두 1만큼 값을 증가시켜 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• n은 식물을 심은 날의 수 즉 쿼리의 개수이므로 세그먼트 트리의 크기와는 무관하다.

 

정답 코드

#include<iostream>
using namespace std;
const int N = 1e5;
int n;
int tree[N * 4];
int lazy[N * 4];

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] += (e - s + 1) * lazy[node];
		if (s != e) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node, int s, int e, int L, int R, int val) {
	propagate(node, s, e);
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] += val;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, val);
	update(node * 2 + 1, mid + 1, e, L, R, val);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int s, int e, int idx) {
	propagate(node, s, e);
	if (s == e) return tree[node];
	int mid = (s + e) / 2;
	if (idx <= mid) return query(node * 2, s, mid, idx);
	return query(node * 2 + 1, mid + 1, e, idx);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	while (n--) {
		int L, R; cin >> L >> R;
		int left = query(1, 1, N, L);
		int right = query(1, 1, N, R);
		cout << left + right << "\n";
		update(1, 1, N, L, L, -left);
		update(1, 1, N, R, R, -right);
		update(1, 1, N, L + 1, R - 1, 1);
	}
}