Cartesian Tree
Hi!
Today, I decided to upsolve Codeforces Round 1070 (Div. 2) and work through the problem E. Remove at the Lowest Cost.
While solving it, I learned about a powerful and elegant data structure known as the Cartesian Tree.
This blog summarises what I learned, along with two related data structures that helped me better understand it: Treap and Implicit Treap.
What is a Cartesian Tree?
A Cartesian Tree is a binary tree built from an array that simultaneously satisfies:
- Heap property: Either a max-heap or a min-heap on values
- In-order traversal property: In-order traversal of the tree gives the original array
This combination makes it extremely useful for problems involving:
- Range maximum/minimum relationships
- Dependency between neighbours
- Stack-based construction in linear time
In the Codeforces problem mentioned above, the Cartesian Tree captures which elements can remove which other elements, making the problem tractable.
Learning Resources
These were particularly helpful while learning the concept:
- Wikipedia (concept overview)
https://en.wikipedia.org/wiki/Cartesian_tree - YouTube explanation (excellent intuition)
https://www.youtube.com/watch?v=2R1vV00SQ6g - cp-algorithms (implementation + practice)
https://cp-algorithms.com/data_structures/treap.html
The YouTube video is especially effective as a first exposure — it provides a clear mental model before diving into the code.
Relation to Treaps
A Treap (Tree + Heap) is a randomised balanced BST that shares the same core idea:
- BST property on keys
- Heap property on priorities
If we fix the priorities instead of randomising them, a Treap becomes a Cartesian Tree.
Get Raja Babu’s stories in your inbox
Join Medium for free to get updates from this writer.
Understanding Treaps made Cartesian Trees much easier to grasp.
Here are the two C++ implementations for the same
1. Regular Treap (BST by key, heap by priority)
Below is a standard Treap implementation supporting:
- Insert
- Erase
- Search
Implementation
#include <bits/stdc++.h>
using namespace std;
struct Treap {
struct Node {
int key, prior, cnt;
Node *l, *r;
Node(int k, int p) : key(k), prior(p), cnt(1), l(nullptr), r(nullptr) {}
};
using pNode = Node*;
pNode root = nullptr;
static int cnt(pNode t) {
return t ? t->cnt : 0;
}
static void upd_cnt(pNode t) {
if (t) t->cnt = 1 + cnt(t->l) + cnt(t->r);
}
// Split by key: l contains keys <= key, r contains keys > key
static void split(pNode t, int key, pNode &l, pNode &r) {
if (!t) {
l = r = nullptr;
} else if (t->key <= key) {
split(t->r, key, t->r, r);
l = t;
upd_cnt(l);
} else {
split(t->l, key, l, t->l);
r = t;
upd_cnt(r);
}
}
// Merge two treaps, assuming all keys in l < keys in r
static void merge(pNode &t, pNode l, pNode r) {
if (!l || !r) {
t = l ? l : r;
} else if (l->prior > r->prior) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
upd_cnt(t);
}
void insert(int key, int prior = rand()) {
pNode it = new Node(key, prior);
insert(root, it);
}
static void insert(pNode &t, pNode it) {
if (!t) {
t = it;
} else if (it->prior > t->prior) {
split(t, it->key, it->l, it->r);
t = it;
} else {
insert(it->key < t->key ? t->l : t->r, it);
}
upd_cnt(t);
}
void erase(int key) {
erase(root, key);
}
static void erase(pNode &t, int key) {
if (!t) return;
if (t->key == key) {
pNode old = t;
merge(t, t->l, t->r);
delete old;
} else {
erase(key < t->key ? t->l : t->r, key);
}
upd_cnt(t);
}
bool find(int key) const {
pNode t = root;
while (t) {
if (t->key == key) return true;
t = key < t->key ? t->l : t->r;
}
return false;
}
};Usage Example
#include <bits/stdc++.h>
using namespace std;
int main() {
Treap t;
// Insert keys (priority is random by default)
t.insert(10);
t.insert(5);
t.insert(20);
t.insert(15);
t.insert(3);
/*
Treap now contains:
{3, 5, 10, 15, 20}
Stored in BST order by key,
heap-ordered by priority internally.
*/
// Search for elements
cout << t.find(10) << "\n"; // 1 (true)
cout << t.find(7) << "\n"; // 0 (false)
// Remove a key
t.erase(10);
/*
Now treap contains:
{3, 5, 15, 20}
*/
cout << t.find(10) << "\n"; // 0 (deleted)
// Insert with explicit priority (useful for testing)
t.insert(7, 1000000000);
/*
Key = 7 has very large priority,
so it becomes close to the root.
*/
return 0;
}2. Implicit Treap (Array-like behaviour)
An Implicit Treap removes the explicit key and instead uses the position in the tree as the index.
This allows:
- Insert at position
- Reverse subarrays
- Range operations
All in O(log n).
Implementation
struct ImplicitTreap {
struct Node {
int prior, value, cnt;
bool rev;
Node *l, *r;
Node(int v) : prior(rand()), value(v), cnt(1), rev(false), l(nullptr), r(nullptr) {}
};
using pNode = Node*;
pNode root = nullptr;
static int cnt(pNode t) {
return t ? t->cnt : 0;
}
static void upd_cnt(pNode t) {
if (t) t->cnt = 1 + cnt(t->l) + cnt(t->r);
}
static void push(pNode t) {
if (t && t->rev) {
t->rev = false;
swap(t->l, t->r);
if (t->l) t->l->rev ^= 1;
if (t->r) t->r->rev ^= 1;
}
}
static void merge(pNode &t, pNode l, pNode r) {
push(l);
push(r);
if (!l || !r) {
t = l ? l : r;
} else if (l->prior > r->prior) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
upd_cnt(t);
}
// split by implicit index
static void split(pNode t, pNode &l, pNode &r, int key, int add = 0) {
if (!t) {
l = r = nullptr;
return;
}
push(t);
int cur = add + cnt(t->l);
if (key <= cur) {
split(t->l, l, t->l, key, add);
r = t;
} else {
split(t->r, t->r, r, key, add + 1 + cnt(t->l));
l = t;
}
upd_cnt(t);
}
void insert(int pos, int value) {
pNode t1, t2;
split(root, t1, t2, pos);
pNode it = new Node(value);
merge(t1, t1, it);
merge(root, t1, t2);
}
void reverse(int l, int r) {
pNode t1, t2, t3;
split(root, t1, t2, l);
split(t2, t2, t3, r - l + 1);
if (t2) t2->rev ^= 1;
merge(root, t1, t2);
merge(root, root, t3);
}
static void output(pNode t) {
if (!t) return;
push(t);
output(t->l);
cout << t->value << ' ';
output(t->r);
}
};Usage Example
#include <bits/stdc++.h>
using namespace std;
int main() {
ImplicitTreap t;
/*
Build array: [10, 20, 30, 40, 50]
Insert at the end using position = current size
*/
t.insert(0, 10); // [10]
t.insert(1, 20); // [10, 20]
t.insert(2, 30); // [10, 20, 30]
t.insert(3, 40); // [10, 20, 30, 40]
t.insert(4, 50); // [10, 20, 30, 40, 50]
// Print array
ImplicitTreap::output(t.root);
cout << "\n";
/*
Output:
10 20 30 40 50
*/
// Insert value 99 at position 2
// Before index 2: [10, 20]
// After index 2: [30, 40, 50]
t.insert(2, 99);
/*
Array becomes:
[10, 20, 99, 30, 40, 50]
*/
ImplicitTreap::output(t.root);
cout << "\n";
// Reverse subarray [1, 4]
// 0-based indices
// Subarray: [20, 99, 30, 40]
t.reverse(1, 4);
/*
After reverse:
[10, 40, 30, 99, 20, 50]
*/
ImplicitTreap::output(t.root);
cout << "\n";
return 0;
}Learning about Cartesian Trees was a turning point for me in understanding:
- Advanced stack techniques
- Tree representations of arrays
- Why do some problems suddenly become easy once the proper structure is used
This problem served as a great reminder that data structures are not just theory — they are practical problem-solving tools.
Thanks for reading. This is my first Medium blog, and I’m excited to write more as I continue learning.
Happy coding!
