Cartesian Tree
(graph/tree/CartesianTree.hpp)

• View this file on GitHub
• Last update: 2026-03-11 19:33:55+09:00
• Include: #include "graph/tree/CartesianTree.hpp"

概要

todo

計算量

todo

Verified with

• verify/LibraryChecker/tree/CartesianTree.test.cpp

Code

template <class T, auto compare = std::less()>
class CartesianTree {
 public:
  int root;
  vector<int> parent, left, right;

  CartesianTree() : root(0) {}
  CartesianTree(const vector<T>& v) : root(0), parent(int(v.size()), -1), left(int(v.size()), -1), right(int(v.size()), -1) {
    stack<pair<lint, int>> st;
    int n = int(v.size());
    for (int i = 0; i < n; i++) {
      if (!st.empty()) {
        int pop_idx = -1;
        while (!st.empty() and compare(v[i], st.top().first)) {
          pop_idx = st.top().second;
          st.pop();
        }
        if (pop_idx != -1) {
          left[i] = pop_idx;
          parent[pop_idx] = i;
        }
        if (!st.empty()) {
          int idx = st.top().second;
          parent[i] = idx;
          right[idx] = i;
        }
      }
      st.emplace(v[i], i);
    }

    for (int i = 0; i < n; i++) {
      if (parent[i] == -1) {
        root = i;
        parent[i] = i;
        break;
      }
    }
  }
};

#line 1 "graph/tree/CartesianTree.hpp"
template <class T, auto compare = std::less()>
class CartesianTree {
 public:
  int root;
  vector<int> parent, left, right;

  CartesianTree() : root(0) {}
  CartesianTree(const vector<T>& v) : root(0), parent(int(v.size()), -1), left(int(v.size()), -1), right(int(v.size()), -1) {
    stack<pair<lint, int>> st;
    int n = int(v.size());
    for (int i = 0; i < n; i++) {
      if (!st.empty()) {
        int pop_idx = -1;
        while (!st.empty() and compare(v[i], st.top().first)) {
          pop_idx = st.top().second;
          st.pop();
        }
        if (pop_idx != -1) {
          left[i] = pop_idx;
          parent[pop_idx] = i;
        }
        if (!st.empty()) {
          int idx = st.top().second;
          parent[i] = idx;
          right[idx] = i;
        }
      }
      st.emplace(v[i], i);
    }

    for (int i = 0; i < n; i++) {
      if (parent[i] == -1) {
        root = i;
        parent[i] = i;
        break;
      }
    }
  }
};

Back to top page