[백준 14287번] [세그먼트 트리 / 오일러 투어 테크닉] 회사 문화 3

Approach

가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다.

다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초과하게 된다.

 

이때 등장하는 방법이 Euler tour technique이다.

해당 방법을 통해 트리를 Array로 필 수 있게 된다. 기존에 진행하던 DFS 과정을 잘 생각해보면, 일종의 재귀적으로 계속해서 해당 노드를 기준으로 밑으로 내려가게 된다. 즉, DFS에서 방문순서를 기준으로 index를 부여할 수 있게 된다. 이를 바탕으로 다음과 같은 식을 잡을 수 있다.

 

dfs_in[i] : 노드 i를 포함한 i의 subtree를 방문하는 Euler trail의 시작 index

dfs_out[i] : 노드 i를 포함한 i의 subtree를 방문하는 Euler trail의 끝 index

 

이를 통해, subtree에 대한 정보를 query[dfs_in[i], dfs_out[i]]로 치환해서 볼 수 있게 된다.

 

따라서 i번째 점수는 node_left, node_right가 각각 dfs_in[i], dfs_out[i]와 정확히 같은 상황일 때의 seg[node_index] 값이 된다. 자세한 메커니즘은 다음 필기를 보면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

vector<int> edge[100001];
int seg[400004];
int dfs_in[100001];
int dfs_out[100001];

int EulerTour(int node, int count){
    dfs_in[node] = count;
    if(edge[node].size() == 0){
        dfs_out[node] = count;
        return count; // 자식이 없는 경우
    }
    
    for(int i = 0; i < edge[node].size(); i++){
        count = EulerTour(edge[node][i], ++count);
    }
    dfs_out[node] = count;
    return count;
}

void update(int node_index, int node_left, int node_right, int update_index, int value){
    if(update_index < node_left || update_index > node_right) return;

    seg[node_index] += value;
    if(node_left == node_right) return;
    else{
        int mid = (node_left + node_right) / 2;
        update(node_index * 2, node_left, mid, update_index, value);
        update(node_index * 2 + 1, mid + 1, node_right, update_index, value);
        return;
    }
}

int query(int node_index, int node_left, int node_right, int update_index){
    int dfs_in_index = dfs_in[update_index];
    int dfs_out_index = dfs_out[update_index];
    
    if(dfs_out_index < node_left || dfs_in_index > node_right) return 0; // Out of bound
    else if(dfs_in_index <= node_left && node_right <= dfs_out_index) return seg[node_index];
    else{
        int mid = (node_left + node_right) / 2;
        return query(node_index * 2, node_left, mid, update_index) +
               query(node_index * 2 + 1, mid + 1, node_right, update_index);
    }
}

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));
    memset(dfs_in, 0, sizeof(dfs_in));
    memset(dfs_out, 0, sizeof(dfs_out));

    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        int e;
        cin >> e;
        if(e == -1) continue;
        else{
            edge[e].push_back(i);
        }
    }

    EulerTour(1, 1);

    for(int i = 0; i < m; i++){
        int t;
        cin >> t;
        // update
        if(t == 1){
            int index, value;
            cin >> index >> value;
            update(1, 1, n, dfs_in[index], value);
        }
        else{
            int index;
            cin >> index;
            cout << query(1, 1, n, index) << "\n";
        }
    }
    return 0;
}