Cartesian Tree
(graph/tree/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2026-08-13 01:41:40+09:00
• Include: #include "graph/tree/cartesian_tree.hpp"

Overview

m1une::tree::CartesianTree builds the Cartesian tree of an array. With the default comparator, the minimum element is the root, each parent has value no greater than its children, and an inorder traversal visits indices in increasing order.

Use std::greater<T> to build the maximum Cartesian tree. More generally, comp(x, y) means that value x has higher priority and should be closer to the root than value y. If neither value compares before the other, the smaller index is kept closer to the root.

The structure stores only vertex indices. It can be converted to m1une::graph::Graph<int> when you want to use the other tree helpers.

Public Members

Member	Type	Description
root	int	Root index, or -1 for an empty tree.
parent	std::vector<int>	Parent index, or -1 at the root.
left	std::vector<int>	Left child index, or -1.
right	std::vector<int>	Right child index, or -1.

Methods

Method	Description	Complexity
CartesianTree()	Creates an empty tree.	$O(1)$
CartesianTree(const std::vector<T>& a, Compare comp = Compare())	Builds the Cartesian tree of a.	$O(N)$
void build(const std::vector<T>& a, Compare comp = Compare())	Rebuilds the structure from a.	$O(N)$
int size() const	Returns the number of vertices.	$O(1)$
bool empty() const	Returns whether the tree is empty.	$O(1)$
int parent_or_self(int v) const	Returns parent[v], or v when v is the root.	$O(1)$
std::vector<int> parent_with_root_self() const	Returns the parent array with root as its own parent.	$O(N)$
std::vector<std::pair<int, int>> edges() const	Returns directed (parent, child) pairs.	$O(N)$
m1une::graph::Graph<int> to_graph() const	Returns an undirected graph with one edge per parent-child relation.	$O(N)$

Notes

The implementation is iterative and uses a monotone stack. It does not mutate the input array. The comparator must model a strict weak ordering.

Library Checker’s cartesian_tree problem asks for the root to be printed as its own parent; use parent_with_root_self() for that convention.

Example

#include "graph/tree/cartesian_tree.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {3, 1, 4, 0, 2};

    m1une::tree::CartesianTree tree(a);
    std::vector<int> parent = tree.parent_with_root_self();

    for (int i = 0; i < int(parent.size()); i++) {
        if (i) std::cout << ' ';
        std::cout << parent[i];
    }
    std::cout << "\n";
}

Depends on

• Graph (graph/graph.hpp)

Required by

• Graph All (graph/all.hpp)
• Tree All (graph/tree/all.hpp)

Verified with

• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp
• verify/graph/tree/cartesian_tree.test.cpp
• verify/graph/tree/tree_algorithms.test.cpp

Code

#ifndef M1UNE_TREE_CARTESIAN_TREE_HPP
#define M1UNE_TREE_CARTESIAN_TREE_HPP 1

#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <utility>
#include <vector>

#include "../graph.hpp"

namespace m1une {
namespace tree {

struct CartesianTree {
    int root;
    std::vector<int> parent;
    std::vector<int> left;
    std::vector<int> right;

   private:
    int _n;

    void check_vertex(int v) const {
        assert(0 <= v && v < _n);
    }

   public:
    CartesianTree() : root(-1), _n(0) {}

    template <class T, class Compare = std::less<T>>
    explicit CartesianTree(const std::vector<T>& a, Compare comp = Compare()) : root(-1), _n(0) {
        build(a, comp);
    }

    template <class T, class Compare = std::less<T>>
    void build(const std::vector<T>& a, Compare comp = Compare()) {
        assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
        _n = int(a.size());
        root = -1;
        parent.assign(_n, -1);
        left.assign(_n, -1);
        right.assign(_n, -1);

        std::vector<int> stack;
        stack.reserve(_n);
        for (int i = 0; i < _n; i++) {
            int last = -1;
            while (!stack.empty() && comp(a[i], a[stack.back()])) {
                last = stack.back();
                stack.pop_back();
            }
            if (last != -1) {
                left[i] = last;
                parent[last] = i;
            }
            if (!stack.empty()) {
                right[stack.back()] = i;
                parent[i] = stack.back();
            }
            stack.push_back(i);
        }

        if (!stack.empty()) root = stack.front();
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int parent_or_self(int v) const {
        check_vertex(v);
        return parent[v] == -1 ? v : parent[v];
    }

    std::vector<int> parent_with_root_self() const {
        std::vector<int> result = parent;
        if (root != -1) result[root] = root;
        return result;
    }

    std::vector<std::pair<int, int>> edges() const {
        std::vector<std::pair<int, int>> result;
        if (_n == 0) return result;
        result.reserve(_n - 1);
        for (int v = 0; v < _n; v++) {
            if (parent[v] != -1) result.emplace_back(parent[v], v);
        }
        return result;
    }

    m1une::graph::Graph<int> to_graph() const {
        m1une::graph::Graph<int> g(_n);
        for (int v = 0; v < _n; v++) {
            if (parent[v] != -1) g.add_edge(parent[v], v);
        }
        return g;
    }
};

template <class T, class Compare = std::less<T>>
CartesianTree cartesian_tree(const std::vector<T>& a, Compare comp = Compare()) {
    CartesianTree result;
    result.build(a, comp);
    return result;
}

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_CARTESIAN_TREE_HPP

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



#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


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

namespace m1une {
namespace tree {

struct CartesianTree {
    int root;
    std::vector<int> parent;
    std::vector<int> left;
    std::vector<int> right;

   private:
    int _n;

    void check_vertex(int v) const {
        assert(0 <= v && v < _n);
    }

   public:
    CartesianTree() : root(-1), _n(0) {}

    template <class T, class Compare = std::less<T>>
    explicit CartesianTree(const std::vector<T>& a, Compare comp = Compare()) : root(-1), _n(0) {
        build(a, comp);
    }

    template <class T, class Compare = std::less<T>>
    void build(const std::vector<T>& a, Compare comp = Compare()) {
        assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
        _n = int(a.size());
        root = -1;
        parent.assign(_n, -1);
        left.assign(_n, -1);
        right.assign(_n, -1);

        std::vector<int> stack;
        stack.reserve(_n);
        for (int i = 0; i < _n; i++) {
            int last = -1;
            while (!stack.empty() && comp(a[i], a[stack.back()])) {
                last = stack.back();
                stack.pop_back();
            }
            if (last != -1) {
                left[i] = last;
                parent[last] = i;
            }
            if (!stack.empty()) {
                right[stack.back()] = i;
                parent[i] = stack.back();
            }
            stack.push_back(i);
        }

        if (!stack.empty()) root = stack.front();
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int parent_or_self(int v) const {
        check_vertex(v);
        return parent[v] == -1 ? v : parent[v];
    }

    std::vector<int> parent_with_root_self() const {
        std::vector<int> result = parent;
        if (root != -1) result[root] = root;
        return result;
    }

    std::vector<std::pair<int, int>> edges() const {
        std::vector<std::pair<int, int>> result;
        if (_n == 0) return result;
        result.reserve(_n - 1);
        for (int v = 0; v < _n; v++) {
            if (parent[v] != -1) result.emplace_back(parent[v], v);
        }
        return result;
    }

    m1une::graph::Graph<int> to_graph() const {
        m1une::graph::Graph<int> g(_n);
        for (int v = 0; v < _n; v++) {
            if (parent[v] != -1) g.add_edge(parent[v], v);
        }
        return g;
    }
};

template <class T, class Compare = std::less<T>>
CartesianTree cartesian_tree(const std::vector<T>& a, Compare comp = Compare()) {
    CartesianTree result;
    result.build(a, comp);
    return result;
}

}  // namespace tree
}  // namespace m1une

Back to top page