Cartesian Tree (デカルト木)
(lib/graph/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2024-10-31 23:51:11+09:00
• Include: #include "lib/graph/cartesian_tree.hpp"

Cartesian Tree (デカルト木)

概要

数列 $A$ について、Cartesian Tree を求めます。

計算量

数列の長さを $N$ とすると、$\mathrm{O}(N)$

Verified with

• test/library_checker/tree/cartesian_tree.test.cpp

Code

#pragma once

/**
 * @brief Cartesian Tree (デカルト木)
 * @docs docs/graph/cartesian_tree.md
 */

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

template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a){
    int n = a.size();
    vector<vector<int>> G(n);
    vector<int> par(n, -1), st;
    for(int i = 0; i < n; ++i){
        int prev = -1;
        while(!st.empty() && a[i] < a[st.back()]){
            prev = st.back();
            st.pop_back();
        }
        if(prev != -1){
            par[prev] = i;
        }
        if(!st.empty()){
            par[i] = st.back();
        }
        st.emplace_back(i);
    }
    int root = -1;
    for(int i = 0; i < n; ++i){
        if(par[i] != -1){
            G[par[i]].emplace_back(i);
        } else{
            root = i;
        }
    }
    return make_pair(G, root);
}

#line 2 "lib/graph/cartesian_tree.hpp"

/**
 * @brief Cartesian Tree (デカルト木)
 * @docs docs/graph/cartesian_tree.md
 */

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

template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a){
    int n = a.size();
    vector<vector<int>> G(n);
    vector<int> par(n, -1), st;
    for(int i = 0; i < n; ++i){
        int prev = -1;
        while(!st.empty() && a[i] < a[st.back()]){
            prev = st.back();
            st.pop_back();
        }
        if(prev != -1){
            par[prev] = i;
        }
        if(!st.empty()){
            par[i] = st.back();
        }
        st.emplace_back(i);
    }
    int root = -1;
    for(int i = 0; i < n; ++i){
        if(par[i] != -1){
            G[par[i]].emplace_back(i);
        } else{
            root = i;
        }
    }
    return make_pair(G, root);
}

Back to top page