#include "cartesian_tree.hpp"

View this file on GitHub · Last update: 2026-07-25 04:01:54-07:00

Depends on

• reverse_comparator.hpp

Required by

• 🧪 cartesian_tree.test.cpp

Verified with

• verify/cartesian_tree.test.cpp

Code

	Coverage	Exec / Excl / Total
Lines	93.9%	31 / 0 / 33
Functions	50.0%	5 / 0 / 10
Branches	87.8%	43 / 0 / 49
Full report

#pragma once

#include <vector>
#include <array>

#include "reverse_comparator.hpp"

class CartesianTree {
public:
	struct Node {
		int l, m, r; // inclusive ranges
		std::array<int, 2> c;
		int p;
	};
	std::vector<Node> nodes;
	int root = -1;

	CartesianTree() {}

	Node& operator [] (int idx) { return nodes[idx]; }
	const Node& operator [] (int idx) const { return nodes[idx]; }

	int size() const { return int(nodes.size()); }

private:
	CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {}

public:

	// min-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_min_tree(const std::vector<T>& v, Comp comp = Comp()) {
		std::vector<Node> nodes(v.size()*2+1);
		std::vector<int> stk; stk.reserve(v.size());
		int root = -1;
		for (int i = 0; i <= int(v.size()); i++) {
			int cur = 2*i;
			nodes[cur].l = i;
			nodes[cur].r = i-1;
			nodes[cur].m = i-1;
			nodes[cur].c = {-1, -1};
			while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) {
				int nxt = stk.back(); stk.pop_back();
				nodes[cur].p = nxt;
				nodes[nxt].c[1] = cur;
				nodes[nxt].r = nodes[cur].r;
				cur = nxt;
			}
			if (i == int(v.size())) {
				root = cur;
				break;
			}
			nodes[2*i+1].l = nodes[cur].l;
			nodes[2*i+1].m = i;
			nodes[cur].p = 2*i+1;
			nodes[2*i+1].c[0] = cur;
			stk.push_back(2*i+1);
		}
		nodes[root].p = -1;
		return {std::move(nodes), root};
	}

	// max-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) {
		return build_min_tree(v, reverse_comparator(comp));
	}
};

#include <vector>
#include <array>
#include <functional>
#include <utility>
#line 2 "src/cartesian_tree.hpp"

#line 5 "src/cartesian_tree.hpp"

#line 2 "src/reverse_comparator.hpp"

#line 5 "src/reverse_comparator.hpp"

template <typename F> struct reverse_comparator_t {
	F f;
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) & {
		return f(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) const& {
		return f(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) && {
		return std::move(f)(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) const&& {
		return std::move(f)(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
};

template <typename F> constexpr reverse_comparator_t<std::decay_t<F>> reverse_comparator(F&& f) {
	return { std::forward<F>(f) };
}
#line 7 "src/cartesian_tree.hpp"

class CartesianTree {
public:
	struct Node {
		int l, m, r; // inclusive ranges
		std::array<int, 2> c;
		int p;
	};
	std::vector<Node> nodes;
	int root = -1;

	CartesianTree() {}

	Node& operator [] (int idx) { return nodes[idx]; }
	const Node& operator [] (int idx) const { return nodes[idx]; }

	int size() const { return int(nodes.size()); }

private:
	CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {}

public:

	// min-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_min_tree(const std::vector<T>& v, Comp comp = Comp()) {
		std::vector<Node> nodes(v.size()*2+1);
		std::vector<int> stk; stk.reserve(v.size());
		int root = -1;
		for (int i = 0; i <= int(v.size()); i++) {
			int cur = 2*i;
			nodes[cur].l = i;
			nodes[cur].r = i-1;
			nodes[cur].m = i-1;
			nodes[cur].c = {-1, -1};
			while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) {
				int nxt = stk.back(); stk.pop_back();
				nodes[cur].p = nxt;
				nodes[nxt].c[1] = cur;
				nodes[nxt].r = nodes[cur].r;
				cur = nxt;
			}
			if (i == int(v.size())) {
				root = cur;
				break;
			}
			nodes[2*i+1].l = nodes[cur].l;
			nodes[2*i+1].m = i;
			nodes[cur].p = 2*i+1;
			nodes[2*i+1].c[0] = cur;
			stk.push_back(2*i+1);
		}
		nodes[root].p = -1;
		return {std::move(nodes), root};
	}

	// max-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) {
		return build_min_tree(v, reverse_comparator(comp));
	}
};

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/reverse_comparator.hpp
template<typename F>struct reverse_comparator_t{
F f;
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)&{
return f(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)const&{
return f(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)&&{
return std::move(f)(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)const&&{
return std::move(f)(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
};
template<typename F>constexpr reverse_comparator_t<std::decay_t<F>>reverse_comparator(F&&f){
return{std::forward<F>(f)};
}
// src/cartesian_tree.hpp
class CartesianTree{
public:
struct Node{
int l,m,r;
std::array<int,2>c;
int p;
};
std::vector<Node>nodes;
int root=-1;
CartesianTree(){}
Node&operator[](int idx){return nodes[idx];}
const Node&operator[](int idx)const{return nodes[idx];}
int size()const{return int(nodes.size());}
private:
CartesianTree(std::vector<Node>&&nodes_,int root_):nodes(std::move(nodes_)),root(root_){}
public:
template<typename T,typename Comp=std::less<T>>
static CartesianTree build_min_tree(const std::vector<T>&v,Comp comp=Comp()){
std::vector<Node>nodes(v.size()*2+1);
std::vector<int>stk;stk.reserve(v.size());
int root=-1;
for(int i=0;i<=int(v.size());i++){
int cur=2*i;
nodes[cur].l=i;
nodes[cur].r=i-1;
nodes[cur].m=i-1;
nodes[cur].c={-1,-1};
while(!stk.empty()&&(i==int(v.size())||comp(v[i],v[nodes[stk.back()].m]))){
int nxt=stk.back();stk.pop_back();
nodes[cur].p=nxt;
nodes[nxt].c[1]=cur;
nodes[nxt].r=nodes[cur].r;
cur=nxt;
}
if(i==int(v.size())){
root=cur;
break;
}
nodes[2*i+1].l=nodes[cur].l;
nodes[2*i+1].m=i;
nodes[cur].p=2*i+1;
nodes[2*i+1].c[0]=cur;
stk.push_back(2*i+1);
}
nodes[root].p=-1;
return{std::move(nodes),root};
}
template<typename T,typename Comp=std::less<T>>
static CartesianTree build_max_tree(const std::vector<T>&v,Comp comp=Comp()){
return build_min_tree(v,reverse_comparator(comp));
}
};
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

#pragma once

#include <vector>
#include <array>

#include "reverse_comparator.hpp"

class CartesianTree {
public:
	struct Node {
		int l, m, r; // inclusive ranges
		std::array<int, 2> c;
		int p;
	};
	std::vector<Node> nodes;
	int root = -1;

	CartesianTree() {}

	Node& operator [] (int idx) { return nodes[idx]; }
	const Node& operator [] (int idx) const { return nodes[idx]; }

	int size() const { return int(nodes.size()); }

private:
	CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {}

public:

	// min-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_min_tree(const std::vector<T>& v, Comp comp = Comp()) {
		std::vector<Node> nodes(v.size()*2+1);
		std::vector<int> stk; stk.reserve(v.size());
		int root = -1;
		for (int i = 0; i <= int(v.size()); i++) {
			int cur = 2*i;
			nodes[cur].l = i;
			nodes[cur].r = i-1;
			nodes[cur].m = i-1;
			nodes[cur].c = {-1, -1};
			while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) {
				int nxt = stk.back(); stk.pop_back();
				nodes[cur].p = nxt;
				nodes[nxt].c[1] = cur;
				nodes[nxt].r = nodes[cur].r;
				cur = nxt;
			}
			if (i == int(v.size())) {
				root = cur;
				break;
			}
			nodes[2*i+1].l = nodes[cur].l;
			nodes[2*i+1].m = i;
			nodes[cur].p = 2*i+1;
			nodes[2*i+1].c[0] = cur;
			stk.push_back(2*i+1);
		}
		nodes[root].p = -1;
		return {std::move(nodes), root};
	}

	// max-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) {
		return build_min_tree(v, reverse_comparator(comp));
	}
};

Back to top page