세그먼트 트리 그래프 간선 압축

Segment Tree Graph, 세그먼트 트리 그래프, Segment Tree on Graph Edges

정의

세그먼트 트리 그래프 간선 압축 은 “한 정점 v 에서 구간 [l, r] 의 모든 정점으로 가는 간선” (또는 구간에서 구간으로) 을 단순 V·N 간선 대신 세그먼트 트리의 노드를 가상 정점 으로 두어 O(log N) 개의 간선 으로 표현하는 기법.

원래 O(N²) 또는 O(NQ) 였던 그래프 구성을 O((N + Q) log N) 으로 → BFS / Dijkstra / SCC 적용 가능.

문제 상황과 동기

1-to-range 간선이 많은 문제

“비행기 타고 가요” 같은 문제: 도시 v 에서 모든 도시 [l, r] 로 가는 직항 이 비용 c 로 가능하다. 최단 거리를 구하고 싶다.

직접 간선을 추가하면 한 쿼리 당 r-l+1 개, Q 개 쿼리면 O(NQ) 간선. N=10^5, Q=10^5 면 간선 10^10 개로 메모리도 시간도 터진다.

Naive 접근: 각 1-to-range 쿼리를 r-l+1 개 간선으로 직접 추가 → O(NQ) 간선, O(NQ log N) Dijkstra 불가능.

세그먼트 트리 압축의 돌파구: 세그먼트 트리를 그래프의 가상 정점들 로 두고, 구간 [l, r] 을 덮는 O(log N) 개 세그먼트 트리 노드들과 v 사이 간선을 추가. 전체 간선 O(Q log N), Dijkstra O((N + Q log N) log N) 가능.

전형적 문제

• 1-to-range 간선: v → [l, r] 모든 정점으로 가는 간선
• range-to-1 간선: [l, r] 모든 정점에서 v 로 오는 간선
• range-to-range 간선: [l1, r1] 의 모든 정점에서 [l2, r2] 의 모든 정점으로

공통점: 직접 추가하면 O(N²) 간선, 세그먼트 트리 가상 정점으로 O(log N) 또는 O(log² N) 압축.

시각화

핵심 아이디어

세그먼트 트리 노드를 그래프의 가상 정점 으로 둔다. 두 가지 트리를 만든다.

• In-tree: 자식 → 부모 간선 (비용 0). 노드 v 에서 “구간 [l, r] 의 모든 leaf 들로” 가려면 v → [l,r] 을 덮는 O(log N) 개 In-tree 노드들 로 간선 추가. 각 In-tree 노드는 자식으로 흘러가며 leaf 들에 도달.
• Out-tree: 부모 → 자식 간선 (비용 0). 구간 → 노드 v 갈 때 사용. [l,r] 을 덮는 O(log N) 개 Out-tree 노드들 → v 로 간선 추가.

1-to-range:    v → seg_in_nodes covering [l, r] → leaf들 (자식으로 전파)
range-to-1:    leaf들 → seg_out_nodes covering [l, r] → v (부모로 전파)
range-to-range: Out-tree 루트 → In-tree 루트 간선

각 쿼리 당 추가 간선 O(log N). 세그먼트 트리 노드 총 O(N) 개, 전체 정점 약 5N (원래 N + In-tree 2N + Out-tree 2N).

예제 추적

N=4 정점 (0-3), 쿼리: “정점 4 에서 구간 [1,2] 의 모든 정점으로 비용 10 간선”

In-tree 구조 (자식→부모, 비용 0):
         in_root
        /        \
    in_[0,1]    in_[2,3]
     /  \        /  \
  in_0 in_1  in_2 in_3
    ↓    ↓     ↓    ↓
    0    1     2    3  (원래 정점)

구간 [1,2] 를 덮는 세그먼트: in_1, in_2 (2개 노드)

간선 추가:
  4 → in_1 (비용 10)
  4 → in_2 (비용 10)

in_1, in_2 는 각각 자식 간선 (비용 0) 으로 정점 1, 2 로 전파
결과: 정점 4 에서 1, 2 로 비용 10 경로 생성

총 간선: O(log N) = 2개 (직접 추가 시 r-l+1=2개, 이 경우 같지만 N 커지면 차이)
N=1000, [100,900] 이면 직접 801개 vs 세그먼트 O(log 1000)≈10개

응용

1. “비행기 타고 가요” 류

한 도시에서 모든 도시 [l, r] 로 비행기 가는 비용 c → 다익스트라.

2. 그래프 위 SCC / BCC

구간 단위 간선이 많은 그래프의 SCC.

3. 이분 매칭 / 흐름

이분 매칭에서 한 정점이 구간 매칭 가능한 경우, segment tree 로 압축 후 매칭.

4. Journeys / Desert 류

특정 구간들과 연결된 정점들에 대한 BFS / Dijkstra.

구현

다음은 In-tree, Out-tree 두 세그먼트 트리를 구축하고 1-to-range 간선을 추가해 Dijkstra 를 돌리는 골격.

// O((N + Q log N) log N), O(N log N) 공간. 1-to-range / range-to-range 간선을 O(log N) 압축
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

struct SegTreeGraph {
    int N, in_base, out_base, orig_base;
    vector<vector<pair<int,ll>>> adj; // 인접 리스트
    
    SegTreeGraph(int n) : N(n) {
        in_base = 0;           // In-tree 노드: [0, 2N)
        out_base = 2*N;        // Out-tree 노드: [2N, 4N)
        orig_base = 4*N;       // 원래 정점: [4N, 4N+N)
        adj.resize(4*N + N);
        
        // In-tree 구축 (자식→부모, 비용 0)
        for (int i = 0; i < N; i++) {
            int in_leaf = in_base + N + i;
            int orig = orig_base + i;
            adj[in_leaf].push_back({orig, 0}); // leaf → 원래 정점
        }
        for (int i = N-1; i >= 1; i--) {
            int lc = 2*i, rc = 2*i+1;
            adj[lc].push_back({i, 0}); // 왼쪽 자식 → 부모
            adj[rc].push_back({i, 0}); // 오른쪽 자식 → 부모
        }
        
        // Out-tree 구축 (부모→자식, 비용 0)
        for (int i = 0; i < N; i++) {
            int out_leaf = out_base + N + i;
            int orig = orig_base + i;
            adj[orig].push_back({out_leaf, 0}); // 원래 정점 → leaf
        }
        for (int i = 1; i < N; i++) {
            int lc = 2*i, rc = 2*i+1;
            adj[i].push_back({out_base + lc, 0}); // 부모 → 왼쪽 자식
            adj[i].push_back({out_base + rc, 0}); // 부모 → 오른쪽 자식
        }
    }
    
    // v → [l, r] 구간 모든 정점으로 비용 cost 간선 추가
    void add_edge_v_to_range(int v, int l, int r, ll cost) {
        int orig_v = orig_base + v;
        // In-tree 에서 [l, r] 덮는 노드들과 orig_v 연결
        function<void(int, int, int)> add = [&](int node, int nl, int nr) {
            if (r < nl || nr < l) return;
            if (l <= nl && nr <= r) {
                adj[orig_v].push_back({in_base + node, cost});
                return;
            }
            int mid = (nl + nr) / 2;
            add(2*node, nl, mid);
            add(2*node+1, mid+1, nr);
        };
        add(1, 0, N-1);
    }
    
    // [l, r] 구간 모든 정점에서 v 로 비용 cost 간선 추가
    void add_edge_range_to_v(int l, int r, int v, ll cost) {
        int orig_v = orig_base + v;
        function<void(int, int, int)> add = [&](int node, int nl, int nr) {
            if (r < nl || nr < l) return;
            if (l <= nl && nr <= r) {
                adj[out_base + node].push_back({orig_v, cost});
                return;
            }
            int mid = (nl + nr) / 2;
            add(2*node, nl, mid);
            add(2*node+1, mid+1, nr);
        };
        add(1, 0, N-1);
    }
    
    // Dijkstra from source (원래 정점 번호)
    vector<ll> dijkstra(int src) {
        int s = orig_base + src;
        vector<ll> dist(adj.size(), INF);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        dist[s] = 0; pq.push({0, s});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, w] : adj[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        // 원래 정점들의 거리만 반환
        vector<ll> res(N);
        for (int i = 0; i < N; i++) res[i] = dist[orig_base + i];
        return res;
    }
};

int main() {
    int N, Q; cin >> N >> Q;
    SegTreeGraph g(N);
    
    for (int i = 0; i < Q; i++) {
        int v, l, r; ll cost;
        cin >> v >> l >> r >> cost;
        g.add_edge_v_to_range(v, l, r, cost);
    }
    
    auto dist = g.dijkstra(0);
    for (int i = 0; i < N; i++) cout << (dist[i] == INF ? -1 : dist[i]) << " ";
}

구현 팁

1. 인덱싱 분리: In-tree, Out-tree, 원래 정점 세 영역을 명확히 분리. 혼동하면 간선이 엉뚱한 곳에 추가.
2. 비용 0 간선: 세그먼트 트리 내부 간선은 모두 비용 0. 쿼리 간선만 실제 비용.
3. range-to-range: Out-tree 루트 → In-tree 루트 간선 O(log² N) 개. 중간 가상 정점 하나 두면 O(log N) 으로 줄일 수 있지만 구현 복잡.

복잡도

작업	비용
세그먼트 트리 두 그루 구축	O(N)
간선 추가 (1-to-range)	O(log N)
간선 추가 (range-to-range)	O(log² N)
BFS / Dijkstra	O((N + M log N) log N)

M = 쿼리 / 간선 수.

함정

1. 두 트리 노드 분리

In-tree 와 Out-tree 의 노드를 별개의 인덱스 로. leaf 들끼리는 간선 비용 0 으로 연결해야 정합.

2. 가상 정점 인덱싱

세그먼트 트리 노드 + 원래 정점 = 약 5N 정도. 메모리 / 인덱스 관리.

3. range-to-range

두 segment tree 의 각 노드끼리 직접 연결 시 O(log² N) 간선. 중간 가상 정점 으로 압축하면 O(log N) 가능 (구현 복잡).

4. 양방향 비용

다익스트라가 비음수 가중치 가정. 음수 / 0 가중치 케이스 처리.

BOJ 연습 문제

번호	제목	링크
BOJ 18193	비행기 타고 가요	kokoa-lab
BOJ 8274	Journeys	kokoa-lab
BOJ 18362	Desert	kokoa-lab

다른 출처 연습 문제

출처	제목	링크
AtCoder	ARC 069 F Flags	https://atcoder.jp/contests/arc069/tasks/arc069_d

참고

• Dynamic Tree
• Offline Incremental SCC / MST
• Push-Relabel / Cost Scaling