2.4.14 Cartesian Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/*

Builds the min Cartesian tree of an array in linear time. A Cartesian tree is a binary tree whose
inorder traversal is the original array order and whose heap property is determined by array values.
For a min Cartesian tree, each parent has value less than or equal to its children.

Cartesian trees connect arrays, stacks, range minimum queries, treaps, and largest rectangle style
problems. Equal values are broken by position, so earlier equal values become ancestors of later
equal values.

- `CartesianTree(a)` constructs the tree for array `a`.
- `root[]` stores the root index.
- `parent[]`, `left[]`, and `right[]` store neighboring node indices, or $-1$ if absent.

Time Complexity:
- O(n) construction time, where $n$ is the array size.

Space Complexity:
- O(n) for tree arrays and the monotone stack.

*/

#include <vector>

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

  explicit CartesianTree(const std::vector<int> &a)
      : root(-1), parent(a.size(), -1), left(a.size(), -1), right(a.size(), -1) {
    std::vector<int> st;
    for (int i = 0, n = static_cast<int>(a.size()); i < n; i++) {
      int last = -1;
      while (!st.empty() && a[i] < a[st.back()]) {
        last = st.back();
        st.pop_back();
      }
      if (!st.empty()) {
        right[st.back()] = i;
        parent[i] = st.back();
      }
      if (last != -1) {
        left[i] = last;
        parent[last] = i;
      }
      st.push_back(i);
    }
    root = st.empty() ? -1 : st[0];
  }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

void inorder(const CartesianTree &t, int u, vector<int> *order) {
  if (u == -1) {
    return;
  }
  inorder(t, t.left[u], order);
  order->push_back(u);
  inorder(t, t.right[u], order);
}

int main() {
  vector<int> a{3, 2, 6, 1, 9};
  CartesianTree t(a);
  assert(t.root == 3);
  assert(t.parent[1] == 3);
  assert(t.parent[4] == 3);

  vector<int> order;
  inorder(t, t.root, &order);
  for (int i = 0; i < 5; i++) {
    assert(order[i] == i);
  }
  return 0;
}