Cartesian Tree
(tree/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2024-12-19 02:29:08+09:00
• Include: #include "tree/cartesian_tree.hpp"

説明

数列 $a$ を与え、最も小さい要素が根であるCartesian Treeを構築する。返り値の配列 $p$ について、 $p_i$ には親のインデックスが格納されている。根には $-1$ が入っている。Compare に std::greater を与えることで最も大きい要素が根であるCartesian Treeを構築できる。 $O(N)$

Verified with

• test/tree/Cartesian_Tree.test.cpp

Code

#pragma once

#include <ranges>
#include <vector>

namespace ebi {

template <class T, class Compare = std::less<T>>
std::vector<int> cartesian_tree(const std::vector<T> &a) {
    int n = a.size();
    std::vector<int> par(n, -1);
    std::vector<int> stack;
    stack.reserve(n);
    for (int i : std::views::iota(0, n)) {
        int prev = -1;
        while (!stack.empty() && Compare()(a[i], a[stack.back()])) {
            prev = stack.back();
            stack.pop_back();
        }
        if (prev != -1) {
            par[prev] = i;
        }
        if (!stack.empty()) {
            par[i] = stack.back();
        }
        stack.push_back(i);
    }
    return par;
}

}  // namespace ebi

#line 2 "tree/cartesian_tree.hpp"

#include <ranges>
#include <vector>

namespace ebi {

template <class T, class Compare = std::less<T>>
std::vector<int> cartesian_tree(const std::vector<T> &a) {
    int n = a.size();
    std::vector<int> par(n, -1);
    std::vector<int> stack;
    stack.reserve(n);
    for (int i : std::views::iota(0, n)) {
        int prev = -1;
        while (!stack.empty() && Compare()(a[i], a[stack.back()])) {
            prev = stack.back();
            stack.pop_back();
        }
        if (prev != -1) {
            par[prev] = i;
        }
        if (!stack.empty()) {
            par[i] = stack.back();
        }
        stack.push_back(i);
    }
    return par;
}

}  // namespace ebi

Back to top page