graph/tree/cartesian_tree.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "graph/tree/cartesian_tree.hpp"

Verified with

• verify/yosupo_graph/tree_cartesian.test.cpp

Code

#ifndef KK2_GRAPH_TREE_CARTESIAN_TREE_HPP
#define KK2_GRAPH_TREE_CARTESIAN_TREE_HPP 1

#include <utility>
#include <vector>

namespace kk2 {

template <class T> std::pair<int, std::vector<int>> cartesian_tree(const std::vector<T> &a) {
    int n = a.size();
    std::vector<int> par(n, -1);
    std::vector<int> stk;
    for (int i = 0; i < n; ++i) {
        int last = -1;
        while (!stk.empty() && a[stk.back()] > a[i]) {
            last = stk.back();
            stk.pop_back();
        }
        if (last != -1) par[last] = i;
        if (!stk.empty()) par[i] = stk.back();
        stk.push_back(i);
    }
    return {stk[0], par};
}

} // namespace kk2

#endif // KK2_GRAPH_TREE_CARTESIAN_TREE_HPP

#line 1 "graph/tree/cartesian_tree.hpp"



#include <utility>
#include <vector>

namespace kk2 {

template <class T> std::pair<int, std::vector<int>> cartesian_tree(const std::vector<T> &a) {
    int n = a.size();
    std::vector<int> par(n, -1);
    std::vector<int> stk;
    for (int i = 0; i < n; ++i) {
        int last = -1;
        while (!stk.empty() && a[stk.back()] > a[i]) {
            last = stk.back();
            stk.pop_back();
        }
        if (last != -1) par[last] = i;
        if (!stk.empty()) par[i] = stk.back();
        stk.push_back(i);
    }
    return {stk[0], par};
}

} // namespace kk2

Back to top page