Cartesian Tree
(tree/cartesian_tree.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

数列から Cartesian tree を $O(N)$ で構築する。 各区間の最小値の位置を根にした木で、同じ値があるときは左にある添字を優先する。

できること

• auto [g, root] = CartesianTree(a) 配列 a から木の子リスト g と根 root を返す

使い方

g[v] には頂点 v の子が入る。 親配列が欲しいときは g をなめて復元する。

vector<int> a = {3, 1, 4, 1, 5};
auto [g, root] = CartesianTree(a);

vector<int> parent(a.size(), -1);
parent[root] = root;
for (int v = 0; v < (int)a.size(); ++v) {
    for (auto &&u : g[v]) parent[u] = v;
}

実装上の補足

スタックを使って最小 Cartesian tree を構築する。 a[i] < a[j] のときだけ pop するので、a[i] == a[j] なら小さい添字が祖先側に残る。

Verified with

• test/yosupo_cartesian_tree.test.cpp

Code

template<class T>
pair<vector<vector<int>>, int> CartesianTree(const vector<T> &a) {
    int n = a.size();
    vector<vector<int>> g(n);
    vector<int> parent(n, -1), st;
    st.reserve(n);
    for (int i = 0; i < n; ++i) {
        int last = -1;
        while (!st.empty() && a[i] < a[st.back()]) {
            last = st.back();
            st.pop_back();
        }
        if (last != -1) parent[last] = i;
        if (!st.empty()) parent[i] = st.back();
        st.push_back(i);
    }
    int root = -1;
    for (int i = 0; i < n; ++i) {
        if (parent[i] == -1) root = i;
        else g[parent[i]].push_back(i);
    }
    return {g, root};
}

/**
 * @brief Cartesian Tree
 */

#line 1 "tree/cartesian_tree.cpp"
template<class T>
pair<vector<vector<int>>, int> CartesianTree(const vector<T> &a) {
    int n = a.size();
    vector<vector<int>> g(n);
    vector<int> parent(n, -1), st;
    st.reserve(n);
    for (int i = 0; i < n; ++i) {
        int last = -1;
        while (!st.empty() && a[i] < a[st.back()]) {
            last = st.back();
            st.pop_back();
        }
        if (last != -1) parent[last] = i;
        if (!st.empty()) parent[i] = st.back();
        st.push_back(i);
    }
    int root = -1;
    for (int i = 0; i < n; ++i) {
        if (parent[i] == -1) root = i;
        else g[parent[i]].push_back(i);
    }
    return {g, root};
}

/**
 * @brief Cartesian Tree
 */

Back to top page