Cartesian Tree
(tree/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2026-03-17 14:01:27+09:00
• Include: #include "tree/cartesian_tree.hpp"

• Cartesian Tree - OI Wiki

Verified with

• test/tree/cartesian_tree.test.cpp

Code

#ifndef CARTESIAN_TREE_HPP
#define CARTESIAN_TREE_HPP

#include <vector>

std::vector<int> cartesian_tree(const std::vector<int> &a) {
    const auto n = int(a.size());
    std::vector<int> parent(n, -1), st;
    for (auto i = 0; i < n; ++i) {
        auto v = -1;
        while (!st.empty() && a[i] < a[st.back()]) {
            v = st.back();
            st.pop_back();
        }
        if (!st.empty()) {
            parent[i] = st.back();
        }
        if (~v) {
            parent[v] = i;
        }
        st.push_back(i);
    }
    return parent;
}

#endif // CARTESIAN_TREE_HPP

#line 1 "tree/cartesian_tree.hpp"



#include <vector>

std::vector<int> cartesian_tree(const std::vector<int> &a) {
    const auto n = int(a.size());
    std::vector<int> parent(n, -1), st;
    for (auto i = 0; i < n; ++i) {
        auto v = -1;
        while (!st.empty() && a[i] < a[st.back()]) {
            v = st.back();
            st.pop_back();
        }
        if (!st.empty()) {
            parent[i] = st.back();
        }
        if (~v) {
            parent[v] = i;
        }
        st.push_back(i);
    }
    return parent;
}

Back to top page