[P3] 백준 16404번 주식회사 승범이네 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 오일러 경로 테크닉

리뷰

 

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

dfs로 부사수를 인덱스로 구간합 세그먼트 트리를 구현하고, 구간 업데이트를 통해 특정 노드의 값을 구하는 문제

 

 

전역 변수

• N : 배열 크기의 최대값을 저장할 상수 변수
• n : 직원의 수를 저장할 변수
• m : 쿼리의 수를 저장할 변수
• it : 오일러 경로의 inTime을 기록할 배열
• ot : 오일러 경로의 outTime을 기록할 배열
• t : 오일러 경로를 구할 때 시간으로 사용할 변수
• tree : 세그먼트 트리 정보를 저장할 배열
• lazy : 구간 업데이트 값을 저장할 배열
• child : 자식의 인덱스 값을 저장할 벡터 배열

 

함수

1. dfs

void dfs(int cur)

 

깊이 우선 탐색을 통해 각 사원의 it와 ot를 구하기 위한 함수

1. 매개 변수로 현재 사원의 인덱스 cur을 전달받는다.
2. it배열에 cur인덱스의 값을 t를 전위증가 시킨 값으로 저장한다.
3. for문을 통해 자신의 부사수들을 탐색하며 각 부사수들을 dfs의 매개변수로 전달하여 재귀를 진행한다.
4. 모든 탐색이 종료된 후엔 ot배열에 cur인덱스 값을 현재 t값으로 저장한다.

 

2. propagate

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

 

갱신할 업데이트가 존재한다면 구간에 적용시켜주기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e를 전달받는다.
2. 현재 노드에 lazy값이 존재하는 경우 lazy의 값 만큼 노드에 더해준다.
3. 만약 리프 노드가 아니라면 좌, 우 자식 노드에 lazy값 만큼 전파해 준다.
4. 위 작업을 마친 후엔 현재 노드의 lazy값을 0으로 만들어준다.

 

3. update

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

 

구간 업데이트를 진행하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 업데이트 구간 L, R, 업데이트 값 val을 전달받는다.
2. 함수 실행 시 propagate함수에 node, s, e를 매개 변수로 전달하여 업데이트 할 값이 있다면 적용해 준다.
3. 첫 번째 기저 조건으로 구간을 벗어난 경우 리턴해 준다.
4. 두 번째 기저 조건으로 탐색 범위가 업데이트 구간과 겹칠 경우 lazy에 val만큼 값을 더해주고, propagate함수에 node, s, e를 매개 변수로 전달하여 업데이트 후 리턴을 진행해 준다.
5. 두 기저 조건에 해당하지 않는 경우 좌, 우 자식 노드에 재귀를 진행해 준다.
6. 재귀를 빠져나오면 세그먼트 트리에 구간합 정보를 갱신해 준다,

 

4. query

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

 

특정 인덱스에 저장된 값을 출력해 주는 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 값을 출력한 idx를 전달받는다.
2. 함수 실행 시 propagate함수에 node, s, e를 매개 변수로 전달하여 업데이트 할 값이 있다면 적용해 준다.
3. 기저 조건으로 리프 노드에 도달할 경우 노드에 기록된 값을 리턴해 준다.
4. 이후 재귀를 통해 idx가 위치한 곳으로 재귀를 진행해 준다.

 

문제풀이

1. n, m에 값을 입력해 주고, 루트 노드의 상사 정보를 변수 temp에 입력 받아준다. 해당 값은 쓸 일이 없다.
2. 2번째 직원 부터 상사의 인덱스를 입력 받아 child배열의 해당 인덱스에 현재 사원의 인덱스를 push해준다.
3. dfs함수에 루트 상사의 인덱스 1을 전달하여 오일러 경로 st, et배열의 값을 초기화 해준다.
4. m개의 쿼리 정보를 입력 받아준다, 첫 번째 인자 op의 값에 따라 처리를 다르게 진행해준다.
5. op가 1일 경우 i, w를 입력 받고, update함수를 통해 it[i], ot[i]의 범위까지 w만큼의 값을 증가시켜 준다.
6. op가 2일 경우 i를 입력 받고, query함수를 통해 인덱스가 i인 사원의 값을 출력해 준 뒤 줄 바꿈을 실행해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• propagate함수는 update 및 query 함수를 실행 시 마다 진행해 주어야 한다.
• update, query함수를 진행할 땐 it, ot배열을 활용하여 세그먼트 트리의 탐색 범위를 지정해 주어야 한다.

 

정답 코드

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

const int N = 100001;
int n, m;
int it[N];
int ot[N];
int t;
int tree[N * 4];
int lazy[N * 4];
vector<int> child[N];

void dfs(int cur) {
	it[cur] = ++t;
	for (int next : child[cur]) {
		dfs(next);
	}
	ot[cur] = t;
}

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

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

	cin >> n >> m;
	int temp; cin >> temp;
	for (int i = 2; i <= n; ++i) {
		int node; cin >> node;
		child[node].push_back(i);
	}
	dfs(1);
	while (m--) {
		int op; cin >> op;
		if (op == 1) {
			int i, w; cin >> i >> w;
			update(1, 1, n, it[i], ot[i], w);
		}
		else {
			int i; cin >> i;
			cout << query(1, 1, n, it[i]) << "\n";;
		}
	}
}