[P2] 백준 3002번 아날로그 다이얼 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

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

Lazy Propagation를 활용한 꽤나 복잡한 문제였다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• Node : 세그먼트 트리의 구간 합, 느리게 갱신할 업데이트 값, 0~9의 개수를 정의할 구조체
• tree : 세그먼트 트리 정보를 저장할 Node타입 배열
• n : 아날로그 다이얼의 개수를 저장할 변수
• m : 질의의 개수를 저장할 변수
• str : 초기 다이얼 정보를 저장할 변수

 

함수

1. update_parent

void update_parent(int node) {
	int temp_sum = 0;
	for (int i = 0; i < 10; ++i) {
		tree[node].cnt[i] = tree[node * 2].cnt[i] + tree[node * 2 + 1].cnt[i];
		temp_sum += tree[node].cnt[i] * i;
	}
	tree[node].sum = temp_sum;
}

 

자식 노드의 cnt와 sum의 합을 계산하여 부모 노드에 할당하기 위한 함수

 

2. build

void build(int node, int s, int e) {
	if (s == e) {
		int d = str[s - 1] - '0';
		tree[node].sum = d;
		tree[node].lazy = 0;
		++tree[node].cnt[d];
		return;
	}
	int mid = (s + e) / 2;
	build(node * 2, s, mid);
	build(node * 2 + 1, mid + 1, e);
	update_parent(node);
}

 

세그먼트 트리 초기화를 위한 함수

 

3. update_range

void update_range(int node, int x) {
	array<int, 10> temp_array{};
	for (int i = 0; i < 10; ++i) temp_array[(i + x) % 10] = tree[node].cnt[i];
	tree[node].cnt = temp_array;

	int temp_sum = 0;
	for (int i = 0; i < 10; ++i) temp_sum += i * temp_array[i];
	tree[node].sum = temp_sum;
}

 

구간 내 다이얼의 개수를 순회 후 변경된 구간 합을 업데이트 하기 위한 함수

 

4. propagate

void propagate(int node, int s, int e) {
	if (tree[node].lazy) {
		update_range(node, tree[node].lazy);

		if (s != e) {
			tree[node * 2].lazy += tree[node].lazy;
			tree[node * 2 + 1].lazy += tree[node].lazy;
		}

		tree[node].lazy = 0;
	}
}

 

현재 노드에 밀린 업데이트를 적용하고, 리프노드가 아닐 경우 전파하기 위한 함수

 

5. update

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

 

세그먼트 트리 업데이트를 위한 함수

 

6. query

int query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node].sum;
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

 

세그먼트 트리 구간합을 구하고 반환하기 위한 함수

 

 

문제풀이

1. n, m, str을 입력 받고, build함수를 통해 세그먼트 트리 초기화를 수행한다.
2. m개의 질의 구간을 변수 L, R에 입력 받는다.
3. query함수를 통해 L~R범위의 누적합을 구하고 출력 후 개행문자를 삽입한다.
4. update함수를 통해 L~R범위에 lazy값을 1만큼 증가시켜 느린 업데이트를 적용시킨다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 세그먼트 트리의 노드 구조체가 여러가지 정보를 담고 있어 업데이트 시 update_parent를 별도로 함수로 빼주었다.
2. propagate시에도 update_range를 통해 현재 노드 정보를 업데이트 하고 자식에겐 lazy값만 전파해 주었다.

 

정답 코드

#include<iostream>
#include<array>
using namespace std;

const int N = 250001;
struct Node {
	int sum;
	int lazy;
	array<int, 10> cnt{};
};
Node tree[N * 4];
int n, m;
string str;

void update_parent(int node) {
	int temp_sum = 0;
	for (int i = 0; i < 10; ++i) {
		tree[node].cnt[i] = tree[node * 2].cnt[i] + tree[node * 2 + 1].cnt[i];
		temp_sum += tree[node].cnt[i] * i;
	}
	tree[node].sum = temp_sum;
}

void build(int node, int s, int e) {
	if (s == e) {
		int d = str[s - 1] - '0';
		tree[node].sum = d;
		tree[node].lazy = 0;
		++tree[node].cnt[d];
		return;
	}
	int mid = (s + e) / 2;
	build(node * 2, s, mid);
	build(node * 2 + 1, mid + 1, e);
	update_parent(node);
}

void update_range(int node, int x) {
	array<int, 10> temp_array{};
	for (int i = 0; i < 10; ++i) temp_array[(i + x) % 10] = tree[node].cnt[i];
	tree[node].cnt = temp_array;

	int temp_sum = 0;
	for (int i = 0; i < 10; ++i) temp_sum += i * temp_array[i];
	tree[node].sum = temp_sum;
}

void propagate(int node, int s, int e) {
	if (tree[node].lazy) {
		update_range(node, tree[node].lazy);

		if (s != e) {
			tree[node * 2].lazy += tree[node].lazy;
			tree[node * 2 + 1].lazy += tree[node].lazy;
		}

		tree[node].lazy = 0;
	}
}

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

int query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node].sum;
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

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

	cin >> n >> m >> str;
	build(1, 1, n);
	while (m--) {
		int L, R; cin >> L >> R;
		cout << query(1, 1, n, L, R) << "\n";
		update(1, 1, n, L, R);
	}
}