Binary Lifting: 2의 지수 doubling

Binary Lifting, 이진 상승, sparse ancestor

정의

트리에서 정점의 2^k 조상 을 O(N log N) 전처리 후 O(log N) 쿼리로 답하는 기법. LCA, k-th ancestor 등에 사용.

전처리

const int LOG = 20;
vector<vector<int>> up(n, vector<int>(LOG));

void dfs(int u, int p) {
    up[u][0] = p;
    for (int k = 1; k < LOG; k++)
        up[u][k] = up[u][k-1] < 0 ? -1 : up[up[u][k-1]][k-1];
    for (int v : adj[u]) if (v != p) {
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

LCA 쿼리

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++)
        if (diff & (1 << k)) u = up[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }
    return up[u][0];
}

O(log N) per query.

응용

• LCA in O(log N)
• Kth ancestor in O(log N)
• Path sum on tree (BIT + LCA)
• Functional graph next state

참고

• LCA
• Euler Tour