Cartesian Tree
(algorithm/cartesian_tree.cpp)

• View this file on GitHub
• Last update: 2022-01-28 02:17:51+09:00

see: https://kmyk.github.io/blog/blog/2020/07/27/recursion-on-cartesian-tree/

Usage

• getCartesianTree(A, cmp): $O(N)$
  • [Input] 数列 $A = (a_1, a_2, \ldots, a_N)$ と比較関数 $\mathrm{cmp}(x, y)$ を与える
    • 比較関数は省略可能。デフォルトでは $\min$ になっている ($x < y$ ならば true)
    • 以降、比較関数が $\min$ に設定されていると仮定して説明する
  • [Output] 以下によって生成される $N$ 頂点の根付き木と、その根を pair にして返す
    • $f(l, r)$ を、「$l \leq m < r, a_m = \min_{j=l}^{r-1} a_j$ を満たすインデックス $m$ を返す関数」と定義する
      • 最小値を取る要素が複数存在する場合は、それらのうち最左の要素に対応するインデックスを返す
    • 頂点 $u = f(l, r)$ から、頂点 $c_l = f(l, m)$ と頂点 $c_r = f(m+1, r)$ の両方に向けて辺を張る
      • 「部分配列から最小値を取り除いて列を分割する」のを再帰的に行うことに対応する木となっている

Depends on

• graph/graph_000_basic.cpp

Verified with

• verifying_test/yosupo/tree/cartesian_tree.test.cpp

Code

#pragma once

/**
 * @brief Cartesian Tree
 * @docs docs/algorithm/cartesian_tree.md
 */

#include <vector>
#include <stack>
#include <utility>
#include <functional>
using namespace std;

#include "../graph/graph_000_basic.cpp"

template <typename Tp = int>
pair< Graph<>, int > getCartesianTree(const vector<Tp> &A,
    function<bool(Tp, Tp)> cmp = [](Tp a, Tp b) {
        return a < b; // min
    }
) {
    int N = A.size();
    vector<int> par(N, -1), st;
    st.reserve(N);
    for(int i=0; i<N; i++) {
        int prev_idx = -1;
        while(st.size() and cmp(A[i], A[st.back()])) {
            prev_idx = st.back(); st.pop_back();
        }
        if(prev_idx >= 0) {
            par[ prev_idx ] = i;
        }
        if(st.size()) {
            par[i] = st.back();
        }
        st.emplace_back(i);
    }

    int root = -1;
    Graph<> G(N);
    for(int i=0; i<N; i++) {
        if(par[i] < 0) {
            root = i;
        }
        else {
            G[ par[i] ].emplace_back(i);
        }
    }
    return make_pair(G, root);
}

#line 2 "algorithm/cartesian_tree.cpp"

/**
 * @brief Cartesian Tree
 * @docs docs/algorithm/cartesian_tree.md
 */

#include <vector>
#include <stack>
#include <utility>
#include <functional>
using namespace std;

#line 1 "graph/graph_000_basic.cpp"
// 移動元と行先と辺のコストを記録する構造体

template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;
#line 15 "algorithm/cartesian_tree.cpp"

template <typename Tp = int>
pair< Graph<>, int > getCartesianTree(const vector<Tp> &A,
    function<bool(Tp, Tp)> cmp = [](Tp a, Tp b) {
        return a < b; // min
    }
) {
    int N = A.size();
    vector<int> par(N, -1), st;
    st.reserve(N);
    for(int i=0; i<N; i++) {
        int prev_idx = -1;
        while(st.size() and cmp(A[i], A[st.back()])) {
            prev_idx = st.back(); st.pop_back();
        }
        if(prev_idx >= 0) {
            par[ prev_idx ] = i;
        }
        if(st.size()) {
            par[i] = st.back();
        }
        st.emplace_back(i);
    }

    int root = -1;
    Graph<> G(N);
    for(int i=0; i<N; i++) {
        if(par[i] < 0) {
            root = i;
        }
        else {
            G[ par[i] ].emplace_back(i);
        }
    }
    return make_pair(G, root);
}

Back to top page