Cartesian Tree

Introduction

A Cartesian tree is a binary tree where each node consists of a key-value pair \((k,w)\). It requires that \(k\) satisfies the properties of a Binary Search Tree (BST), while \(w\) satisfies the properties of a heap. If the key-values \((k,w)\) of the Cartesian tree are determined, and all \(k\) are distinct and all \(w\) are distinct, then the structure of this Cartesian tree is unique. As shown in the figure below:

(Image source: Wikipedia)

The Cartesian tree above treats the array element values as the key \(w\), and the array indices as the key \(k\). It can be observed that the key \(k\) of this tree satisfies BST properties, while the key \(w\) satisfies the properties of a min-heap. Moreover, due to the properties of a binary search tree, it can be seen that for this special Cartesian tree, the indices within a subtree form a contiguous interval.

In competitive programming, when using Cartesian trees, array indices are often used as the key \(k\) of the pair, and the array index \(k\) satisfies BST properties.

In the following, when using \(k,w\), it is assumed by default that \(k\) satisfies BST properties and \(w\) satisfies heap properties.

Building a Cartesian Tree with a Monotonic Stack

Process

We consider inserting elements into the current Cartesian tree in ascending order of \(k\).

For a Cartesian tree, define the "right chain" as the chain formed by starting from the root node and continuously moving to the right child until reaching a leaf node. Then, after inserting a node, this node must be on the right chain. Because we are inserting in ascending order of \(k\) which satisfies BST properties, this newly inserted node must be at the rightmost end of the tree. This node cannot be a left child and has no right child.

Thus, we perform the following process: compare the \(w\) values of nodes on the right chain with the current node \(u\) from bottom to top. If we find a node \(x\) on the right chain satisfying \(w_x<w_u\), we attach \(u\) as the right child of \(x\), and the original right subtree of \(x\) becomes the left subtree of \(u\).

The red box in the figure shows the right chain we maintain:

build

Clearly, each number enters and exits the right chain at most once (or each point exists on the right chain for a contiguous period of time). This process can be maintained using a monotonic stack, where the stack stores the nodes currently on the right chain of the Cartesian tree. A point is popped from the stack when it is no longer on the right chain. Thus, each point enters and exits at most once, resulting in a complexity of \(O(n)\).

Cartesian Tree and Treap

In fact, a Treap is a type of Cartesian tree, except that in a Treap, the value \(w\) is completely random. Treaps have a linear construction algorithm. If the keys \(k\) are sorted in advance, the above monotonic stack algorithm can be used for construction, though it is rarely used this way.

C++ Implementation

// stk maintains the indices corresponding to nodes in the Cartesian tree in the sequence
for (int i = 1; i <= n; i++) {
  int k = top;  // top represents the stack top before the operation, k represents the current stack top
  while (k > 0 && w[stk[k]] > w[i]) k--;  // Maintain nodes on the right chain
  if (k) rs[stk[k]] = i;  // Right child of stack top element := current element
  if (k < top) ls[i] = stk[k + 1];  // Left child of current element := last popped element
  stk[++k] = i;                     // Push current element onto stack
  top = k;
}

Example Problems

HDU 1506. Largest Rectangle in a Histogram

There are \(n\) positions, each with a height \(h_i\). Find the largest sub-rectangle. As shown in the figure:

The shaded part is the largest sub-rectangle in the figure.

Solution Idea

Specifically, we treat the index as the key \(k\), and \(h_i\) as the key \(w\) satisfying min-heap properties, constructing a Cartesian tree of \((i,h_i)\).

Then we enumerate each node \(u\), taking \(w_u\) (i.e., the height \(h\) of node \(u\)) as the height of the largest sub-rectangle. Since the Cartesian tree we built satisfies min-heap properties, the heights of nodes in the subtree of \(u\) are all greater than or equal to \(u\). Moreover, we know that the indices within the subtree of \(u\) form a contiguous interval. Thus, we only need to know the size of the subtree to calculate the area of the largest sub-rectangle for this interval. Update the answer with the value computed for each point. Clearly, this can be done with a single DFS, so the complexity is \(O(n)\).

Reference Implementation

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node {
  int idx, val, par, ch[2];

  friend bool operator<(node a, node b) { return a.idx < b.idx; }

  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
} tree[N];

int root, top, stk[N];
ll ans;

int cartesian_build(int n) {  // Build the tree, satisfying the min-heap property
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}

int dfs(int x) {  // One DFS is enough to update the answer
  if (!x) return 0;
  int sz = dfs(tree[x].ch[0]);
  sz += dfs(tree[x].ch[1]);
  ans = max(ans, (ll)(sz + 1) * tree[x].val);
  return sz + 1;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, hi;
  while (cin >> n, n) {
    tree[0].init(0, 0, 0);
    for (int i = 1; i <= n; i++) {
      cin >> hi;
      tree[i].init(i, hi, 0);
    }
    root = cartesian_build(n);
    ans = 0;
    dfs(root);
    cout << ans << '\n';
  }
  return 0;
}

References

Cartesian tree - Wikipedia

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用