알고리즘 템플릿

const int MAX_TREE_NODE_SIZE = 1 << 17;

int node[MAX_TREE_NODE_SIZE];
int lazy[MAX_TREE_NODE_SIZE];

void propagate(int idx, int s, int e) {
	if (lazy[idx] == 0) return;
	
	node[idx] += lazy[idx]; // 필요에따라 업데이트하는 값 변경
	
	if (s < e) {
		int L = idx * 2, R = L + 1;
		lazy[L] += lazy[idx];
		lazy[R] += lazy[idx];
	}
	
	lazy[idx] = 0;
}

segUpdate(int idx, int ns, int ne, int qs, int qe, int val)
{
	propagate(); // 노드를 방문하면 값을 전파해준다.
	
	if (qs <= ns && ne <= qe) { // 탐색 구간이 완전히 포함될 때엔 lazy만 갱신하고 더이상 탐색하지 않는다.
		lazy[idx] += val;
		return;
	}
}

segFind();

인사이트

정의

문제 및 풀이 코드

2820 - 자동차 공장 (https://www.acmicpc.net/problem/2820)

부하직원들의 월급을 일제히 가감하는 점에서 lazy하게 업데이트해야 함을 느꼈다.

그런데 어떻게 a의 부하직원들만 골라서 업데이트 하는가?

→ lazy하게 업데이트 하려면 어쨌든 부하직원들이 다 하나의 구간에 몰려있어야 한다.

→ 주어진 employee 관계는 tree이다.

→ 부하직원들끼리 구간으로 모이도록 tree를 배열로 펼칠 수 있을까?

→ tree를 배열로 펼치려면 traverse를 해야 한다.

→ traverse 중 전위순회를 하면 내가 원했던대로 자식의 자식, 자식의 자식의 자식.. 월급을 일제히 인상해야하는 대상들끼리 같은 구간에 포함된 배열을 만들 수 있다.

이후에는 단순한 lazy segment tree로 풀이 가능했다.