11월 20일 - 주식회사 승범이네[BOJ/16404]

트리 구조에서 각 노드와 그 하위 노드들의 손익을 효율적으로 관리하는 문제다. 쿼리의 수가 최대 100,000개까지 가능하기 때문에 효율적인 자료구조와 접근 방식이 필요했다. 이를 위해 세그먼트 트리와 Lazy Propagation을 활용하여 문제를 해결했다.

문제 접근 방법

1. 트리의 오일러 경로(Euler Tour):

• 트리에서 특정 노드와 그 하위 노드에 대해 손익을 업데이트해야 하므로, 트리를 일렬로 나열하는 방식인 오일러 경로를 활용했다.
• 오일러 경로를 통해 각 노드의 시작과 종료 구간을 기록하고, 이 구간에 대해 세그먼트 트리를 적용했다.

2. 세그먼트 트리와 Lazy Propagation:

• 세그먼트 트리를 사용해 특정 구간에 값을 업데이트하거나, 특정 노드의 값을 빠르게 쿼리할 수 있다.
• Lazy Propagation 기법을 통해 구간 업데이트의 효율성을 높였다. 이 방식은 세그먼트 트리를 실제로 갱신하지 않고 필요한 시점에 계산하도록 최적화한다.

3. 쿼리 처리:

• 1 i w: 노드 i와 그 하위 노드들에 대해 w만큼 이익/손해를 반영한다.
• 2 i: 노드 i의 현재 잔고를 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] tree, lazy, start, end;
    static int ett = 0; // Euler Tour Trick에서 사용할 변수
    static List<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st;

        // 입력 처리
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 세그먼트 트리 및 lazy 배열 초기화
        tree = new int[4 * n];
        lazy = new int[4 * n];

        // 그래프 및 오일러 경로 배열 초기화
        start = new int[n + 1];
        end = new int[n + 1];
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        // 트리 구조 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if (parent != -1) graph[parent].add(i);
        }

        // 오일러 경로 구성
        dfs(1);

        // 쿼리 처리
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int node = Integer.parseInt(st.nextToken());
            if (type == 1) {
                int value = Integer.parseInt(st.nextToken());
                update(1, n, 1, start[node], end[node], value);
            } else {
                pw.println(query(1, n, 1, start[node]));
            }
        }

        pw.flush();
        pw.close();
    }

    // 오일러 경로 구성
    static void dfs(int node) {
        start[node] = ++ett;
        for (int child : graph[node]) {
            dfs(child);
        }
        end[node] = ett;
    }

    // Lazy propagation 처리
    static void applyLazy(int s, int e, int node) {
        if (lazy[node] != 0) {
            tree[node] += (e - s + 1) * lazy[node];
            if (s != e) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    // 세그먼트 트리 갱신
    static void update(int s, int e, int node, int l, int r, int value) {
        applyLazy(s, e, node);
        if (s > r || e < l) return; // 범위를 벗어남
        if (l <= s && e <= r) { // 범위에 포함됨
            tree[node] += (e - s + 1) * value;
            if (s != e) {
                lazy[node * 2] += value;
                lazy[node * 2 + 1] += value;
            }
            return;
        }
        int mid = (s + e) / 2;
        update(s, mid, node * 2, l, r, value);
        update(mid + 1, e, node * 2 + 1, l, r, value);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    // 세그먼트 트리 쿼리
    static int query(int s, int e, int node, int index) {
        applyLazy(s, e, node);
        if (s > index || e < index) return 0; // 범위를 벗어남
        if (s == e) return tree[node]; // 단일 범위
        int mid = (s + e) / 2;
        return query(s, mid, node * 2, index) + query(mid + 1, e, node * 2 + 1, index);
    }
}

코드 설명

1. 오일러 경로 구성

static void dfs(int node) {
    start[node] = ++ett;
    for (int child : graph[node]) {
        dfs(child);
    }
    end[node] = ett;
}

• DFS를 통해 각 노드의 시작 구간(start)과 종료 구간(end)을 기록한다.
• 이를 통해 각 노드와 그 하위 노드들의 범위를 구할 수 있다.

2. Lazy Propagation 처리

static void applyLazy(int s, int e, int node) {
    if (lazy[node] != 0) {
        tree[node] += (e - s + 1) * lazy[node];
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

• Lazy Propagation을 사용해 세그먼트 트리의 갱신을 필요할 때만 적용한다.
• 구간 업데이트 시에는 lazy 배열에 갱신 값을 저장하고, 쿼리 시에는 applyLazy를 호출해 값을 반영한다.

3. 세그먼트 트리 갱신

static void update(int s, int e, int node, int l, int r, int value) {
    applyLazy(s, e, node);
    if (s > r || e < l) return; // 범위를 벗어남
    if (l <= s && e <= r) { // 범위에 포함됨
        tree[node] += (e - s + 1) * value;
        if (s != e) {
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
        return;
    }
    int mid = (s + e) / 2;
    update(s, mid, node * 2, l, r, value);
    update(mid + 1, e, node * 2 + 1, l, r, value);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

• 갱신할 범위가 현재 노드 범위에 포함되면 tree 값을 갱신하고 lazy 값을 업데이트한다.

4. 세그먼트 트리 쿼리

static int query(int s, int e, int node, int index) {
    applyLazy(s, e, node);
    if (s > index || e < index) return 0; // 범위를 벗어남
    if (s == e) return tree[node]; // 단일 범위
    int mid = (s + e) / 2;
    return query(s, mid, node * 2, index) + query(mid + 1, e, node * 2 + 1, index);
}

• 쿼리 범위가 노드 범위에 포함될 경우, applyLazy를 호출해 갱신 값을 반영한 후 결과를 반환한다.

So...

오일러 경로와 세그먼트 트리를 결합하여 트리의 서브트리에 대한 구간 연산을 효율적으로 처리한 사례로, Lazy Propagation을 활용해 구간 갱신의 효율성을 극대화했다. 특히 트리 구조를 일렬로 표현하는 방법과 구간 연산의 최적화를 고민하며, 오일러 경로와 Lazy Propagation의 중요성을 다시금 확인할 수 있었다.