Heavy-Light 分解 (HLD) (Tree/heavy_light_decomposition.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-05-21 15:06:13+09:00
Include: #include "Tree/heavy_light_decomposition.hpp"

Heavy-Light 分解

木（無向連結グラフ）に対し、以下の操作を行います。

任意のパス上の区間クエリ（非可換クエリ対応）
任意の根付き部分木の区間クエリ
最小共通祖先（LCA）計算

コンストラクタ

HeavyLightDecomposition hld(int n);

頂点数 $n$ の木を扱うためのオブジェクトを生成します。

計算量

$O(n)$

add_edge

void hld.add_edge(int u, int v);

頂点 $u, v$ 間に無向辺を追加します。

制約

$0 \leq u, v < n$

計算量

$O(1)$

build

void hld.build(int root = 0);

番号が $root$ の頂点を根として Heavy-Light 分解を構築します。 build 前提のメソッド呼び出し時は自動的に実行されます。

制約

$0 \leq root < n$

計算量

$O(n)$

get_path_ranges

std::vector<std::tuple<int, int, bool>> hld.get_path_ranges(int u, int v);

頂点 $u$ から $v$ へのパスをセグメントのリストに変換します。

各タプルは (l, r, is_reverse) の形式で、基底配列上の区間 [l, r) と、クエリ方向を示すフラグ is_reverse（false: 左から右へ適用、true: 右から左へ適用）を表します。

非可換クエリに対応する場合、is_reverse に応じてクエリや更新の適用方向を変更してください。

制約

$0 \leq u, v < n$

計算量

$O(\log^2 n)$

get_subtree_range

std::array<int, 2> hld.get_subtree_range(int u);

頂点 $u$ を根とする部分木を、基底配列上の区間 [l, r) で返します。

制約

$0 \leq u < n$

計算量

$O(1)$

lca

int hld.lca(int u, int v);

頂点 $u, v$ の最小共通祖先を返します。

制約

$0 \leq u, v < n$

計算量

$O(\log n)$

get_pos

int hld.get_pos(int v);

点 $v$ の HLD 基底配列上のインデックスを返します。

制約

$0 \leq v < n$

計算量

$O(1)$

get_parent

int hld.get_parent(int v);

頂点 $v$ の親ノードを返します。

制約

$0 \leq v < n$

計算量

$O(1)$

get_subtree_size

int hld.get_subtree_size(int u);

頂点 $u$ を根とする部分木の頂点数を返します。

制約

$0 \leq u < n$

計算量

$O(1)$

Verified with

Code

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

class HeavyLightDecomposition
{
public:
    HeavyLightDecomposition(int n)
        : n(n), edges(n), parent(n, -1), depth(n, 0), heavy(n, -1), head(n), pos(n), sz(n), built(false)
    {
    }

    void add_edge(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    void build(int root = 0)
    {
        assert(0 <= root && root < n);
        if (built)
        {
            return;
        }

        parent[root] = -1;
        depth[root] = 0;
        dfs_size(root);

        int time = 0;
        decompose(root, root, time);
        built = true;
    }

    vector<tuple<int, int, bool>> get_path_ranges(int from, int to)
    {
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        ensure_built();

        list<tuple<int, int, bool>> from_ranges, to_ranges;

        while (head[from] != head[to])
        {
            if (depth[head[to]] < depth[head[from]])
            {
                from_ranges.push_back({pos[head[from]], pos[from] + 1, true});
                from = parent[head[from]];
            }
            else
            {
                to_ranges.push_front({pos[head[to]], pos[to] + 1, false});
                to = parent[head[to]];
            }
        }

        if (depth[to] < depth[from])
        {
            to_ranges.push_front({pos[to], pos[from] + 1, true});
        }
        else
        {
            from_ranges.push_back({pos[from], pos[to] + 1, false});
        }

        vector<tuple<int, int, bool>> result;
        result.insert(result.end(), from_ranges.begin(), from_ranges.end());
        result.insert(result.end(), to_ranges.begin(), to_ranges.end());

        return result;
    }

    array<int, 2> get_subtree_range(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return {pos[u], pos[u] + sz[u]};
    }

    int lca(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);

        ensure_built();
        while (head[u] != head[v])
        {
            if (depth[head[u]] > depth[head[v]])
            {
                swap(u, v);
            }
            v = parent[head[v]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int get_pos(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return pos[v];
    }

    int get_parent(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return parent[v];
    }

    int get_subtree_size(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return sz[u];
    }

private:
    int n;
    vector<vector<int>> edges;
    vector<int> parent, depth, heavy, head, pos, sz;
    bool built;

    void ensure_built()
    {
        if (!built)
        {
            build();
        }
    }

    int dfs_size(int v)
    {
        sz[v] = 1;
        int max_size = 0;
        for (int u : edges[v])
        {
            if (u == parent[v])
            {
                continue;
            }

            parent[u] = v;
            depth[u] = depth[v] + 1;
            int sub = dfs_size(u);
            sz[v] += sub;
            if (max_size < sub)
            {
                max_size = sub;
                heavy[v] = u;
            }
        }

        return sz[v];
    }

    void decompose(int v, int h, int &time)
    {
        head[v] = h;
        pos[v] = time++;
        if (heavy[v] != -1)
        {
            decompose(heavy[v], h, time);
        }

        for (int u : edges[v])
        {
            if (u == parent[v] || u == heavy[v])
            {
                continue;
            }

            decompose(u, u, time);
        }
    }
};

#line 1 "Tree/heavy_light_decomposition.hpp"
#include <bits/stdc++.h>
using namespace std;

class HeavyLightDecomposition
{
public:
    HeavyLightDecomposition(int n)
        : n(n), edges(n), parent(n, -1), depth(n, 0), heavy(n, -1), head(n), pos(n), sz(n), built(false)
    {
    }

    void add_edge(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    void build(int root = 0)
    {
        assert(0 <= root && root < n);
        if (built)
        {
            return;
        }

        parent[root] = -1;
        depth[root] = 0;
        dfs_size(root);

        int time = 0;
        decompose(root, root, time);
        built = true;
    }

    vector<tuple<int, int, bool>> get_path_ranges(int from, int to)
    {
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        ensure_built();

        list<tuple<int, int, bool>> from_ranges, to_ranges;

        while (head[from] != head[to])
        {
            if (depth[head[to]] < depth[head[from]])
            {
                from_ranges.push_back({pos[head[from]], pos[from] + 1, true});
                from = parent[head[from]];
            }
            else
            {
                to_ranges.push_front({pos[head[to]], pos[to] + 1, false});
                to = parent[head[to]];
            }
        }

        if (depth[to] < depth[from])
        {
            to_ranges.push_front({pos[to], pos[from] + 1, true});
        }
        else
        {
            from_ranges.push_back({pos[from], pos[to] + 1, false});
        }

        vector<tuple<int, int, bool>> result;
        result.insert(result.end(), from_ranges.begin(), from_ranges.end());
        result.insert(result.end(), to_ranges.begin(), to_ranges.end());

        return result;
    }

    array<int, 2> get_subtree_range(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return {pos[u], pos[u] + sz[u]};
    }

    int lca(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);

        ensure_built();
        while (head[u] != head[v])
        {
            if (depth[head[u]] > depth[head[v]])
            {
                swap(u, v);
            }
            v = parent[head[v]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int get_pos(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return pos[v];
    }

    int get_parent(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return parent[v];
    }

    int get_subtree_size(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return sz[u];
    }

private:
    int n;
    vector<vector<int>> edges;
    vector<int> parent, depth, heavy, head, pos, sz;
    bool built;

    void ensure_built()
    {
        if (!built)
        {
            build();
        }
    }

    int dfs_size(int v)
    {
        sz[v] = 1;
        int max_size = 0;
        for (int u : edges[v])
        {
            if (u == parent[v])
            {
                continue;
            }

            parent[u] = v;
            depth[u] = depth[v] + 1;
            int sub = dfs_size(u);
            sz[v] += sub;
            if (max_size < sub)
            {
                max_size = sub;
                heavy[v] = u;
            }
        }

        return sz[v];
    }

    void decompose(int v, int h, int &time)
    {
        head[v] = h;
        pos[v] = time++;
        if (heavy[v] != -1)
        {
            decompose(heavy[v], h, time);
        }

        for (int u : edges[v])
        {
            if (u == parent[v] || u == heavy[v])
            {
                continue;
            }

            decompose(u, u, time);
        }
    }
};