Euler tour technique

들어가며..

  이전에 Heavy-Light Decomposition에 대해 다룬 적이 있다. 이는 트리를 몇개의 선형 배열로 바꾸는 것이며, 주로 특정한 두 정점을 잇는 경로에 포함되는 간선의 가중치나 정점에 관한 쿼리를 처리하는 데에 이용된다. 그렇다면, 해당 노드와 그 노드의 모든 자식 노드들에 관한 쿼리는 어떻게 처리할까?

 

Euler tour technique

  오일러 투어 테크닉(Euler tour technique)은 Tarjan과 Vishkin이 제안한 방법이다. 이 방법을 오일러 투어 테크닉이라고 부르는 이유는 검색 트리에서 이 테크닉을 통해 정점에 numbering 한 후, 각 간선의 역방향 간선을 만들어(자식 → 부모) numbering 한 순서대로 나열하면, 오일러 회로로 나타내지기 때문이다. 이를 오일러 투어 표현(Euler Tour Representation) 이라고 한다.

 

  PS에서 오일러 투어 테크닉은 트리의 노드에 번호를 번호를 붙이는 것으로 끝난다. 오일러 투어 표현을 하지 않아도 좋다. 오일러 투어 테크닉은 DFS를 통해 노드에 번호를 붙이며, 방문한 순서대로 번호를 붙인다. 그리고 번호를 각 정점에 대하여 해당 정점의 모든 자식 노드들을 포함하는 subtree에 포함되는 정점의 번호가 몇 번 부터 몇 번 까지 임을 표기한다.

 

구간 쿼리 처리

  Euler tour technique으로 노드의 넘버링이 끝났다면, 특정 노드의 하위 노드를 모두 포함하는 subtree의 정점들에 대하여, (혹은 간선) lazy propgation을 지원하는 segment tree를 만들고 구간 쿼리를 처리할 수 있다.

 

 

아래는 BOJ 2820을 해결한 코드이다.

// haruki291sa
// BOJ 2820
// submission num : 56596912
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll seg[2000003],lazy[2000003],num[500003],A[500003];
pair<int,int>ET[500003];
vector<vector<int> >G;
void g(ll s,ll e,ll pos){
    if(s==e)return;
    lazy[pos<<1]+=lazy[pos];
    lazy[(pos<<1)|1]+=lazy[pos];
    seg[pos<<1]+=(((s+e)>>1)-s+1)*lazy[pos];
    seg[(pos<<1)|1]+=(e-((s+e)>>1))*lazy[pos];
    lazy[pos]=0LL;
}
void lazy_update(ll S,ll E,ll s,ll e,ll pos,ll val){
    g(s,e,pos);
    if(S>e||s>E)return;
    if(S<=s&&e<=E){
        int p=pos;
        lazy[p]+=val;
        while(p){
            seg[p]+=val*(e-s+1);
            p>>=1;
        }
        return;
    }
    g(s,e,pos);
    lazy_update(S,E,s,(s+e)>>1,pos<<1,val);
    lazy_update(S,E,((s+e)>>1)+1,e,(pos<<1)|1,val);
}
int cnt=0;
void DFS(int x){
    cnt++;
    num[x]=cnt;
    int t=cnt;
    ET[t].first=cnt;
    for(int y:G[x])DFS(y);
    ET[t].second=cnt;
}
int Query(ll S,ll E,ll s,ll e,ll pos){
    if(S>e||s>E)return 0;
    if(S<=s&&e<=E)return seg[pos];
    g(s,e,pos);
    return Query(S,E,s,(s+e)>>1,pos<<1)+Query(S,E,((s+e)>>1)+1,e,(pos<<1)|1);
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int N,M;cin>>N>>M;
    G.resize(N+1);
    int st=1;while(st<N)st<<=1;
    int a,b;cin>>A[1];
    for(int i=2;i<=N;i++){
        cin>>A[i]>>b;
        G[b].push_back(i);
    }
    DFS(1);
    for(int i=1;i<=N;i++){
        int x=num[i];
        lazy_update(x,x,1,st,1,A[i]);
    }
    while(M--){
        char c;cin>>c;
        if(c=='p'){
            cin>>a>>b;
            a=num[a];
            lazy_update(ET[a].first+1,ET[a].second,1,st,1,b);
        }else{
            cin>>a;
            a=num[a];
            cout<<Query(a,a,1,st,1)<<"\n";
        }
    }
    return 0;
}