Cartesian Tree
(tree/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-07 23:25:49+09:00
• Include: #include "tree/cartesian_tree.hpp"

Description

Cartesian tree は，数列から定まる二分木で，以下の条件を満たすものである．

• 各頂点の重みは，そのどの子の重みよりも小さい
• 木の in-order traversal がもとの数列と一致する

Operations

• vector<int> cartesian_tree(vector<int> a)
  • 数列 $a$ から定まる Cartesian tree を返す．それぞれの頂点の親のラベルを返す．根の親は -1 とする．
  • 時間計算量: $O(n)$

Reference

• 列を最小値で分割して再帰するパターンと Cartesian tree

Verified with

• test/yosupo/cartesian_tree.test.cpp

Code

#pragma once
#include <stack>
#include <vector>

template <typename T>
std::vector<int> cartesian_tree(const std::vector<T>& a) {
    const int n = a.size();
    std::vector<int> par(n, -1);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {
        int j = -1;
        while (!st.empty() && a[st.top()] >= a[i]) {
            j = st.top();
            st.pop();
        }
        if (!st.empty()) par[i] = st.top();
        if (j != -1) par[j] = i;
        st.push(i);
    }
    return par;
}

#line 2 "tree/cartesian_tree.hpp"
#include <stack>
#include <vector>

template <typename T>
std::vector<int> cartesian_tree(const std::vector<T>& a) {
    const int n = a.size();
    std::vector<int> par(n, -1);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {
        int j = -1;
        while (!st.empty() && a[st.top()] >= a[i]) {
            j = st.top();
            st.pop();
        }
        if (!st.empty()) par[i] = st.top();
        if (j != -1) par[j] = i;
        st.push(i);
    }
    return par;
}

Back to top page