[ Query ] 오일러 경로 테크닉 (Euler Tour Technique)

Euler Tour Technique

 

 

Segment Tree를 이용한 쿼리 처리는 일반적으로 Array에서 이루어졌다. Array에서 구간 쿼리를 효율적으로 처리할 수 있었던 이유는, 처리하고자 하는 구간의 원소들이 인접하게, 연속하게 존재했기 때문이다. 이러한 연속성을 이용하여 특정 구간에 대한 쿼리를 Segment Tree로 $O(logN)$에 처리할 수 있었던 것이다. 그렇다면 Graph에서의 쿼리 처리에 대해 고민해보자. Update Query는 아마도 간선 가중치 업데이트가 될 것이고, 구간합 쿼리는 경로의 길이를 구하는 쿼리가 될 것이라고 예상할 수 있다. 하지만 Array와 달리 Graph는 연속성이 정해져 있지 않다. 즉, 그래프의 형태에 따라 업데이트 하고자 하는 구간이 연속적일수도 있고, 아닐 수도 있다. 따라서 우리는 일반 그래프의 형태가 아닌 Tree에서의 쿼리 처리를 먼저 고민해보아야 한다.

 

하지만 트리에서 구간 쿼리를 적용하는 것은 매우 어렵다. 그 이유는 트리의 정점들에게서 구간과 같은 연속성을 찾기 어렵기 때문이다. 추후에 다룰 Heavy-Light Decomposition은 트리를 연속된 부분(분기)들로 잘라 저장하여 세그먼트 트리를 사용할 수 있도록 하는 방법을 제공하지만, 특정 형태의 쿼리에 대해 간단한 테크닉이 존재한다. (HLD와 ETT가 처리하는 쿼리는 그 형태가 매우 다르다)

 

 

 

오일러 투어 테크닉의 핵심은 다음과 같다. 먼저 dfs를 통해 정점의 번호를 지정해준다. 이는 한 분기 내의 정점들이 연속된 번호를 부여받을 수 있도록 하는 작업이다. 이제 핵심은 각 정점들이 "자식 노드의 번호의 범위(구간)"을 저장한다는 것이다. 즉, 정점 u에 대해 [u의 번호, max(v의 번호)] (v는 u의 자손 정점)와 같은 형태의 구간을 저장하도록 하는 것이다.

 

 

그렇다면 이 정보는 쿼리를 처리하는데 어떻게 작용할 수 있을까? 아래 문제를 보자.

 

 

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

16404번: 주식회사 승범이네

 

 

이 문제는 정점의 값이 갱신되면 그 정점의 모든 자식 정점들의 값도 갱신되는 형태의 문제이다. 자식 정점을 업데이트 하기 위해 단순히 그래프 탐색을 해서 업데이트를 해주면 매우 비효율적일 것이다. 따라서 세그먼트 트리 같은 구간을 관리하는 자료구조를 이용해서 업데이트와 쿼리를 $O(logN)$으로 해결해야 할 것이다. 위에서 언급했던 구간을 생각해보자. dfs를 통해 정점에 부여해준 번호를 n(v)라 하자. 정점 u의 자손은 [n(u), max(n(v))](v는 u의 자손)의 구간에 존재하고, 그 구간 내에서 연속적으로 존재할 것이다. 그렇다면 세그먼트 트리에서 특정 정점 u의 가중치를 n(u)번 칸에서 저장하고 있다고 하면, 정점 u의 값을 업데이트 하는 것은, [n(u), max(n(v))](v는 u의 자손)의 구간을 업데이트 하는 것과 같다.

 

 

따라서 Lazy Propagation을 적용한 세그먼트 트리를 통해 O(QlogN)으로 해결 가능하다.

 

 

 

구현

 

먼저 위 문제의 예제를 트리로 나타내면 다음과 같다.

 

 

다음과 같은 구조를 이루게 되는데 dfs로 탐색을 하고 순서대로 번호를 매겨보면

 

 

 

 

다음과 같이 된다. 이 때 우리는 $i$번 노드를 업데이트 하면 $i$번 노드부터 그 아래 자식 노드까지 모두 업데이트가 되도록 해야 한다.

 

예를 들어 4번 노드를 업데이트하면 4번 노드의 자식인 2번 노드도 업데이트 되는 것이다.

 

이를 구현하기 위해 우리는 이 정점의 시작 번호(dfs로 해당 정점을 방문한 시점)와 끝 번호(dfs로 해당 정점이 포함된 분기에 대한 탐색이 종료된 시점)를 저장해놔야한다. 따라서 변수 하나를 만들고 정점을 방문할 때마다 그 값을 1씩 증가시킬 것이다. $i$번 정점을 방문했을 때의 변수의 값을 시작 값으로, $i$번 정점이 포함된 분기의 탐색이 끝났을 때의 변수의 값을 끝 값으로 하면 된다.

 

$1$번 정점: 시작: $1$ ,  끝: $5$

$2$번 정점: 시작: $4$ ,  끝: $4$

$3$번 정점: 시작: $2$ ,  끝: $2$

$4$번 정점: 시작: $3$ ,  끝: $4$

$5$번 정점: 시작: $5$ ,  끝: $5$

 

 

 

 

//s[i]: i번 정점에 방문한 시점 기록
//e[i]: i번 정점을 빠져나온 시점 기록
int s[500001], e[500001], cnt=0;
vector<int> adj[500001];

void dfs(int x, int par)
{
    S[x]=++cnt;
    for(int nxt : adj[x]) {
        if(nxt==par){ continue; }
        dfs(nxt, x);
    }
    E[x]=cnt;
}

 

 

연습 문제

 

BOJ 16404 주식회사 승범이네: 오일러 투어 테크닉으로 정점들의 번호를 매겨준 후, $i$번 노드를 업데이트를 하면 $i$번 노드의 시작~끝의 구간을 Segment Tree Lazy Propagation으로 업데이트 하면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, m;
long long tree[2000001], lazy[2000001];
int S[500001], E[500001], cnt=0;
vector<int> adj[500001];

void propagation(int node, int s, int e)
{
    if(lazy[node]==0){ return; }
    tree[node]+=(e-s+1)*lazy[node];
    if(s!=e){
        for(int i=node*2; i<=node*2+1; i++){
            lazy[i]+=lazy[node];
        }
    }
    lazy[node]=0;
}

void update(int node, int s, int e, int l, int r, long long val)
{
    propagation(node, s, e);
    if(e<l || r<s){ return; }
    if(l<=s && e<=r){
        lazy[node]=val;
        propagation(node, s, e);
        return;
    }
    int mid=s + e >> 1;
    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];
}

long long sum(int node, int s, int e, int l, int r)
{
    propagation(node, s, e);
    if(e<l || r<s){ return 0; }
    if(l<=s && e<=r){ return tree[node]; }
    int mid=s + e >> 1;
    return sum(node*2, s, mid, l, r)+sum(node*2+1, mid+1, e, l, r);
}


void dfs(int x, int par)
{
    S[x]=++cnt;
    for(int nxt : adj[x]) {
        if(nxt==par){ continue; }
        dfs(nxt, x);
    }
    E[x]=cnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        int a; cin >> a;
        if(a==-1){ continue; }
        adj[a].push_back(i);
    }
    dfs(1, -1);
    int mx=0;
    for(int i=1; i<=n; i++){
        mx=max(mx, E[i]);
    }
    while(m--){
        int op; cin >> op;
        if(op==1){
            int a; long long x;
            cin >> a >> x;
            update(1, 1, mx, S[a], E[a], x);
        }
        else{
            int a; cin >> a; cout << sum(1, 1, mx, S[a], S[a]) << "\n";
        }
    }
	return 0;
}

 

문제 해결

 

위 문제의 경우, 특정 정점이 갱신되면 그 자손들이 모두 갱신되는 형태의 쿼리를 lazy propagation을 통해 직접 시행했지만, 직접 시행하지 않는 경우도 존재한다. 예를 들어 위 문제를 변형해서, u가 갱신되면 그 조상들이 모두 갱신되는 쿼리를 시행해보자. 조상 정점들에 대해 연속성을 가지는 번호을 부여할 수 있을까? 이는 매우 어려울 것이고, 특정 정점에 대해 이가 가능하다면, 다른 분기의 정점에 대해서는 불가능할 것이다. 따라서 다른 방법으로, 업데이트 쿼리가 아닌 sum 쿼리를 이용해보자.

 

 

1. u의 가중치가 갱신되면, 세그먼트 트리에서 n(u)만 갱신한다.

2. u의 가중치를 구하는 쿼리가 주어지면, sum([n(u), max(n(v))]를 구한다.

 

 

자손 정점들의 가중치 합은 결국 u의 가중치에 반영되므로, 오일러 투어 테크닉을 활용할 수 있게 된다.