[P3] 백준 14268번 회사 문화 2 C++ 세그먼트 트리, 오일러 경로 테크닉, 느리게 갱신되는 세그먼트 트리

리뷰

 

오일러 경로 테크닉에 대한 개념을 이해하게 된 문제

일반적인 Lazy propagation을 통한 풀이는 인덱스를 지정하기가 불가능해 보인다.

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

 

전역 변수

• MAX_N : n값의 최대치를 저장할 정수형 상수 변수, 크기는 10만 1로 초기화 한다.
• tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화
• lazy : 세그먼트 트리의 업데이트 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화
• n, m : 직원의 수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 m
• path : 직원간의 상하 직속 정보를 인접리스트 형태로 저장할 정수형 벡터, 크기는 MAX_N으로 초기화
• it : 서브 트리의 시작시간(세그먼트 트리의 시작 인덱스)를 저장할 정수형 배열, 크기는 MAX_N으로 초기화
• ot : 서브 트리의 종료시간(세그먼트 트리의 종료 인덱스)를 저장할 정수형 배열, 크기는 MAX_N으로 초기화
• timer : 서브 트리 탐색 시 시작과 종료시간을 초기화 할때 사용할 변수

 

함수

1. dfs

void dfs(int boss)

 

서브트리에서 it와 ot를 초기화 하는데 사용할 함수

1. 사장부터 시작하여 각 직속 부하에 대한 it와 ot에 timer값을 저장해 준다.
2. 배개변수로 들어온 boss는 자기 자신이다, timer를 전위증가 시켜준 후에 it배열의 boss인덱스에 저장해 준다.
3. 자신의 인접리스트를 순회하며 자식들에게 dfs를 통해 재귀를 진행해 준다.
4. 자신의 자식에게 모두 재귀를 마친 경우 자신의 ot배열의 boss인덱스에 종료 시잔을 저장해 준다.

 

2. propagate

void propagate(int node, int s, int e)

 

세그먼트 트리의 입력된 구간에 누적된 업데이트 정보를 적용시켜줄 함수

1. 현재 노드에 쌓인 업데이트 정보가 있다면 적용시켜 준다.
2. 현재 트리 노드에 업데이트할 구간 * 증가시킬 수치를 적용시켜 주면 된다.
3. 현재 노드가 리프노드가 아니라면 왼쪽 오른쪽의 자식 노드에게도 업데이트 값을 전달해 준다.
4. 업데이트 및 전파 작업이 완료된 후에는 자신의 업데이트 값을 0으로 변경해 준다.

 

3. update

void update(int node, int s, int e, int L, int R, int val)

 

세그먼트 트리의 구간 업데이트를 적용시킬 함수

1. 우선 propagate 함수를 통해 현재 노드에 남아있는 업데이트를 진행해 준다.
2. 범위 내인 경우 현재 노드의 lazy배열에 업데이트 값을 증가시켜 준다.
3. propagate 함수를 통해 추가로 업데이트를 진행해준 후에 리턴 해준다.
4. 범위가 아닌 경우 이분 탐색을 통한 재귀로 현재 노드의 왼쪽 오른쪽에 업데이트를 추가로 진행해 준다.
5. 재귀가 완료되면 트리 노드의 값을 업데이트 해준다.

 

4. query

int query(int node, int s, int e, int idx)

 

세그먼트 트리의 인덱스에 해당하는 값을 출력해 주는 함수

1. 세그먼트 트리 내에서 idx에 저장된 노드의 값을 출력해 준다.
2. 탐색은 마찬가지로 이분 탐색을 통해 분할해서 재귀를 이어나가주면 된다.

 

문제풀이

1. trash 변수를 초기화 하고 n, m, trash값을 입력 받는다, trash값은 사용할 일이 없다.
2. 2번 노드부터 n번 노드까지 역방향으로 인접리스트를 추가해 준다.
3. dfs 함수를 통해 루트 노드인 1로부터 it, ot배열을 초기화 해준다.
4. m개의 쿼리를 입력 받고 각 쿼리마다 order와 idx를 입력받아준다.
5. odrer가 1일 경우 val을 추가로 입력 받고 it[idx] ~ ot[idx] 범위에 val값을 더해준다.
6. order가 2일 경우 it[idx]에 해당하는 인덱스의 값을 출력해 준다.

 

참고 사항

오일러 경로 테크닉을 통해 세그먼트 트리의 인덱스 범위를 지정해 줄 수 있다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

const int MAX_N = 100001;
int tree[MAX_N * 4];
int lazy[MAX_N * 4];
int n, m;

vector<int> path[MAX_N];
int it[MAX_N];
int ot[MAX_N];
int timer;

void dfs(int boss) {
	it[boss] = ++timer;
	for (int child : path[boss]) dfs(child);
	ot[boss] = timer;
}

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 == idx && e == idx) return tree[node];
	int mid = (s + e) / 2;
	if (s <= idx && idx <= mid) return query(node * 2, s, mid, idx);
	else return query(node * 2 + 1, mid + 1, e, idx);
}

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

	int trash;
	cin >> n >> m >> trash;
	for (int i = 2; i <= n; i++) {
		int boss; cin >> boss;
		path[boss].push_back(i);
	}

	dfs(1);

	while (m--) {
		int order, idx; cin >> order >> idx;
		if (order == 1) {
			int val; cin >> val;
			update(1, 1, n, it[idx], ot[idx], val);
		}
		else cout << query(1, 1, n, it[idx]) << "\n";
	}
}