개요

가장자리 트리는 지속 가능한 세그먼트 트리로, 하지타 님이 개발한 데이터 구조이다. 함수형 세그먼트 트리라고도 불린다. 이 구조는 배열의 역사적 상태를 효율적으로 저장하고 조회할 수 있게 해준다.

핵심 아이디어

모든 버전을 복제하는 방식은 메모리 낭비가 심하다. 하지만 각 업데이트에서 영향을 받는 노드는 루트까지의 경로에 국한된다. 따라서 기존 트리와 공유되는 부분은 그대로 유지하고, 변경된 경로만 새롭게 연결하여 저장하면 된다. 이로 인해 공간 복잡도는 O(n log n) 수준으로 유지된다.

예제 1: 순서 기반 중위값 조회 (P3834)

배열의 특정 구간에서 k번째로 작은 값을 찾는 문제. 가중치 기반의 지속 가능한 세그먼트 트리를 사용한다.

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

const int MAXN = 200005;
const int MAXT = 32 * MAXN;

int n, m, arr[MAXN], roots[MAXN];
struct TreeNode {
    int left, right, count;
} tree[MAXT];
int node_cnt = 0;

int insert(int root_id, int l, int r, int pos, int delta) {
    int curr = ++node_cnt;
    tree[curr] = tree[root_id]; // 기존 노드 복사

    if (l == r) {
        tree[curr].count += delta;
        return curr;
    }

    int mid = (l + r) / 2;
    if (pos <= mid) {
        tree[curr].left = insert(tree[root_id].left, l, mid, pos, delta);
    } else {
        tree[curr].right = insert(tree[root_id].right, mid + 1, r, pos, delta);
    }
    tree[curr].count = tree[tree[curr].left].count + tree[tree[curr].right].count;
    return curr;
}

int query(int left_root, int right_root, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) / 2;
    int left_count = tree[tree[left_root].left].count - tree[tree[right_root].left].count;

    if (k <= left_count) {
        return query(tree[left_root].left, tree[right_root].left, l, mid, k);
    } else {
        return query(tree[left_root].right, tree[right_root].right, mid + 1, r, k - left_count);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    vector<int> values;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        values.push_back(arr[i]);
    }

    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    // 좌표 압축
    for (int i = 1; i <= n; ++i) {
        arr[i] = lower_bound(values.begin(), values.end(), arr[i]) - values.begin() + 1;
    }

    // 초기 루트 생성
    roots[0] = 0;
    for (int i = 1; i <= n; ++i) {
        roots[i] = insert(roots[i-1], 1, values.size(), arr[i], 1);
    }

    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        int result_idx = query(roots[r], roots[l-1], 1, values.size(), k);
        cout << values[result_idx - 1] << '\n';
    }

    return 0;
}

예제 2: 지속 가능한 배열 (P3919)

배열의 특정 위치에 값을 설정하거나, 과거 버전의 값을 조회하는 문제. 각 버전이 독립적인 트리로 표현된다.

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

const int MAXN = 1000005;
const int MAXT = 32 * MAXN;

int n, m, base_arr[MAXN], roots[MAXN];
struct Node {
    int left, right, value;
} nodes[MAXT];
int node_idx = 0;

int build_tree(int l, int r) {
    int curr = ++node_idx;
    if (l == r) {
        nodes[curr].value = base_arr[l];
        return curr;
    }
    int mid = (l + r) / 2;
    nodes[curr].left = build_tree(l, mid);
    nodes[curr].right = build_tree(mid + 1, r);
    return curr;
}

int update(int old_root, int l, int r, int pos, int new_val) {
    int curr = ++node_idx;
    nodes[curr] = nodes[old_root];

    if (l == r) {
        nodes[curr].value = new_val;
        return curr;
    }

    int mid = (l + r) / 2;
    if (pos <= mid) {
        nodes[curr].left = update(nodes[old_root].left, l, mid, pos, new_val);
    } else {
        nodes[curr].right = update(nodes[old_root].right, mid + 1, r, pos, new_val);
    }
    return curr;
}

int get_value(int root, int l, int r, int pos) {
    if (l == r) return nodes[root].value;
    int mid = (l + r) / 2;
    if (pos <= mid) {
        return get_value(nodes[root].left, l, mid, pos);
    } else {
        return get_value(nodes[root].right, mid + 1, r, pos);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> base_arr[i];
    }

    roots[0] = build_tree(1, n);
    for (int i = 1; i <= m; ++i) {
        int ver, op, idx;
        cin >> ver >> op >> idx;
        if (op == 1) {
            int val;
            cin >> val;
            roots[i] = update(roots[ver], 1, n, idx, val);
        } else {
            cout << get_value(roots[ver], 1, n, idx) << '\n';
            roots[i] = roots[ver];
        }
    }

    return 0;
}

세그먼트 트리 상의 이분 탐색 기법

여러 버전의 트리에서 특정 조건을 만족하는 값의 위치를 찾는 데 유용하다.

int find_first(int a, int b, int c, int d, int l, int r, int low, int high) {
    if ((tree[a].count ^ tree[b].count ^ tree[c].count ^ tree[d].count) == 0)
        return -1;

    if (l == r) return l;

    int mid = (l + r) / 2;
    if (low <= mid) {
        int res = find_first(tree[a].left, tree[b].left, tree[c].left, tree[d].left, l, mid, low, high);
        if (res != -1) return res;
    }
    if (high > mid) {
        int res = find_first(tree[a].right, tree[b].right, tree[c].right, tree[d].right, mid + 1, r, low, high);
        if (res != -1) return res;
    }
    return -1;
}