Heavy-Light Decomposition (HLD)

RMQ와 같이, 수열에서 풀 수 있는 문제들을 트리에서 풀어보자. segment tree를 이용하여 풀 수 있는 문제를 주로 다룬다. 트리를 체인 여러개로 쪼개고, 각 체인에서는 수열에서와 같이 segment tree를 이용해 답을 구한다. 그 후 여러 체인을 합쳐줄 것이다. 그러면 (원하는 구간이 걸쳐져있는 체인의 수) * (체인 1개에 대해서 구간 쿼리를 할 때 필요한 연산 수) 만큼의 연산이 필요하다. 따라서 트리에서의 구간이 적은 체인에 걸쳐지도록 하자. 이렇게 체인을 쪼개어 문제를 푸는 것이 HLD이다.

HLD에서는 간선이 두 가지가 있다: Heavy edge, Light edge. Heavy edge들만 남겨놓고 Light edge를 지우면 체인들만 남게 되고, 이 체인들은 모두 조상-자식을 잇는 형태이다. 한 정점과 그 자식들을 잇는 간선 중에는 Heavy edge가 최대 1개만 있게 된다.

Heavy edge에 대한 정의는 조금씩 다를 수 있는데, 자식들과 연결된 간선 중 크기가 가장 큰 서브트리 쪽으로 가는 간선을 Heavy edge로 지정한다. 자식 서브트리의 크기가 현재 서브트리의 크기의 절반보다 큰 경우에만 Heavy edge로 지정하기도 한다. 나는 주로 전자의 방식을 이용해 구현한다. 

이렇게 Heavy edge를 정의하고 나면, Light edge 간선을 타고 내려가면 서브트리의 크기가 절반 이하로 줄어들게 된다. 따라서 어떤 정점에서 루트까지 올라가는 경로에는 Light edge가 $logN$개 밖에 없게 된다. 

구현을 할 때는 각 체인에 대한 segment tree를 따로 만들어도 되고, 아니면 체인들을 차례대로 이어붙였다고 생각하여 하나의 segment tree를 만들어도 된다. 나는 주로 후자의 방식을 이용한다. 왜냐하면 굉장히 깔끔하게 구현할 수 있다. 어차피 체인들을 이어붙일 것이기 때문에, dfs를 돌며 dfs ordering을 하되, 한 체인을 모두 지나간 후 다른 체인에 진입하도록 하면 된다. 이는 자식들 중 가장 서브트리의 크기가 큰 쪽으로 먼저 내려가며 dfs를 돌면 된다. https://codeforces.com/blog/entry/53170 참고.

 

아래는 RMQ에 대한 HLD 코드의 일부이다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;
const int MX = 1 << 16;
const int INF = 1 << 30;

int N, M;
vector<int> ed[MAXN];
int par[MAXN], sz[MAXN], mx[MAXN], dep[MAXN], dfn[MAXN], hln[MAXN], dn;
int seg[2 * MX];

int gseg(int idx, int l, int r, int x, int y) {	// segment tree를 이용해서  [x, y] 최솟값 구하기
	if(x <= l && r <= y) return seg[idx];
	if(r < x || y < l) return 0;
	int m = (l + r) / 2;
	return min(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y));
}
int gseg(int x, int y) { return gseg(1, 1, N, x, y); }

void gsz(int x, int p) {			// 모든 정점을 순회하며 크기가 가장 큰 자식을 찾는다
	sz[x] = 1;
	for(auto a : ed[x]) if(a != p) {
		gsz(a, x);
		sz[x] += sz[a];
		if(sz[x] > sz[mx[x]]) mx[x] = a;
	}
}

void dfs(int x, int d, int h, int p) {		// Heavy edge를 먼저 가며 dfs ordering을 해준다
	dep[x] = d;
	hln[x] = h;
	par[x] = p;
	dfn[x] = ++dn;
	if(mx[x]) dfs(mx[x], d + 1, h, x);
	for(auto a : ed[x]) if(a != p && a != mx[x]) 
		dfs(a, d + 1, a, x);
}

int ghld(int x, int y) {			// 정점 x와 그 조상 y에 대해 경로상의 최솟값을 구한다
	int ans = INF;
	while(dep[hln[x]] > dep[y]) {
		ans = min(ans, gseg(dfn[hln[x]], dfn[x]));
		x = par[hln[x]];
	}
	return min(ans, gseg(dfn[y], dfn[x]));
}