Cartesian Tree (graph/others/cartesian-tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "graph/others/cartesian-tree.hpp"
• Link: https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/

概要

数列に対応する Cartesian tree を求める.

使い方

• cartesian_tree(v): 数列 v に対応する Cartesian tree を返す. 各要素にはその要素の親の idx が格納される. ただし根は -1.

計算量

• $O(N)$

Verified with

• test/verify/yosupo-cartesian-tree.test.cpp
• test/verify/yosupo-staticrmq-4.test.cpp

Code

#pragma once
/**
 * @brief Cartesian Tree
 *
 * @see https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/
 */
template <typename T>
vector<int> cartesian_tree(const vector<T> &v) {
  int n = (int)v.size();
  vector<int> par(n, -1);
  stack<int> st;
  for (int i = 0; i < n; i++) {
    int last = -1;
    while (!st.empty() && v[st.top()] >= v[i]) {
      last = st.top();
      st.pop();
    }
    if (!st.empty()) par[i] = st.top();
    if (last >= 0) par[last] = i;
    st.emplace(i);
  }
  return par;
}

#line 2 "graph/others/cartesian-tree.hpp"
/**
 * @brief Cartesian Tree
 *
 * @see https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/
 */
template <typename T>
vector<int> cartesian_tree(const vector<T> &v) {
  int n = (int)v.size();
  vector<int> par(n, -1);
  stack<int> st;
  for (int i = 0; i < n; i++) {
    int last = -1;
    while (!st.empty() && v[st.top()] >= v[i]) {
      last = st.top();
      st.pop();
    }
    if (!st.empty()) par[i] = st.top();
    if (last >= 0) par[last] = i;
    st.emplace(i);
  }
  return par;
}

Back to top page