Skip to content

Permutation Tree

A problem about segments

We begin with a neat little problem:

For a permutation of \(1-n\), call a range whose values are consecutive a segment. Count the segments of a permutation. For example, the segments of \(\{5 ,3 ,4, 1 ,2\}\) are \([1,1],[2,2],[3,3],[4,4],[5,5],[2,3],[4,5],[1,3],[2,5],[1,5]\).

At first sight this seems to call for maintaining the set of values of a range, and the complexity looks rather unfriendly. A segment tree can tell whether a given range is a segment, but it is not much help in counting the segments.

This is where a magical data structure comes in: the permutation tree!

Contiguous segments

Before introducing the permutation tree, we fix some preliminaries. The definitions given in LCA's slides are hard to follow, so to help the reader we give definitions here that are less rigorous (but easier to understand).

Permutations and contiguous segments

Permutation: a permutation \(P\) of length \(n\) is a sequence of \(n\) elements in which \(P_i\) takes each of the values \(1,2,\cdots,n\). More formally, a permutation \(P\) of length \(n\) is an ordered set such that:

  1. \(|P|=n\).
  2. \(\forall i,P_i\in[1,n]\).
  3. \(\nexists i,j\in[1,n],P_i=P_j\).

    Contiguous segment: for a permutation \(P\), a contiguous segment \((P,[l,r])\) is a range \([l,r]\) such that the values of \(P_{l\sim r}\) are consecutive. More formally, a contiguous segment of a permutation \(P\) is a range \([l,r]\) that satisfies:

\[ (\nexists\ x,z\in[l,r],y\notin[l,r],\ P_x<P_y<P_z) \]

In particular, when \(l>r\) we regard this as an empty contiguous segment, written \((P,\varnothing)\).

We write \(I_P\) for the set of all contiguous segments of the permutation \(P\), and we take \((P,\varnothing)\in I_P\).

Operations on contiguous segments

Contiguous segments are defined in terms of ranges and values, so we can define the intersection, union and difference of contiguous segments.

Let \(A=(P,[a,b])\) and \(B=(P,[x,y])\), with \(A,B\in I_P\). The relations and operations on contiguous segments can then be written as:

  1. \(A\subseteq B\iff x\le a\wedge b\le y\).
  2. \(A=B\iff a=x\wedge b=y\).
  3. \(A\cap B=(P,[\max(a,x),\min(b,y)])\).
  4. \(A\cup B=(P,[\min(a,x),\max(b,y)])\).
  5. \(A\setminus B=(P,\{i|i\in[a,b]\wedge i\notin[x,y]\})\).

These are just the ordinary set intersection, union and difference, applied to ranges.

Properties of contiguous segments

Contiguous segments have some evident properties. Let \(A,B\in I_P,A \cap B \neq \varnothing,A \notin B,B \notin A\); then \(A\cup B,A\cap B,A\setminus B,B\setminus A\in I_P\).

The proof? At bottom it is nothing but the set operations of intersection, union and difference.

The permutation tree

Now we come to the main topic. As you may have guessed, the permutation tree is a tree made of contiguous segments. But a permutation can have as many as \(O(n^2)\) contiguous segments, so we have to pick out the more basic ones among them to build the permutation tree.

Primitive segments

The full name of this notion is primitive contiguous segment, but the author finds "primitive segment" more concise.

For a permutation \(P\), a primitive segment \(M\) is a contiguous segment that no contiguous segment in the set \(I_P\) intersects without one of the two containing the other. Formally, it is an \(X\in I_P\) that satisfies \(\forall A\in I_P,\ X\cap A= (P,\varnothing)\vee X\subseteq A\vee A\subseteq X\).

The set of all primitive segments is \(M_P\). Evidently \((P,\varnothing)\in M_P\).

Clearly, two primitive segments are either disjoint or nested. Notice, moreover, that a contiguous segment can be made up of several pairwise disjoint primitive segments. The largest primitive segment is the whole permutation, which contains all the other primitive segments, so the primitive segments form a tree structure. We call this structure the permutation tree. More precisely, the permutation tree of a permutation \(P\) consists of all the primitive segments of \(P\).

After so many dry definitions, a picture is overdue. Consider the permutation \(P=\{9,1,10,3,2,5,7,6,8,4\}\). The permutation tree formed by its primitive segments looks like this:

p1

The figure does not mark the primitive segments themselves, but every node in it represents one primitive segment; we show only the value range of each primitive segment. For example, the node \([5,8]\) represents the primitive segment \((P,[6,9])=\{5,7,6,8\}\). This raises a question: what are cut nodes and join nodes?

Cut nodes and join nodes

We state the definitions directly and discuss why they are sound afterwards.

  1. Value range: for a node \(u\), we write \([u_l,u_r]\) for its value range.
  2. Child sequence: for a node \(u\) of the permutation tree, regard its children as an ordered sequence whose elements are value ranges (a single number \(x\) is understood as the range \([x,x]\)). We call this sequence the child sequence and write it \(S_u\).
  3. Child permutation: the permutation obtained from a child sequence \(S_u\) by coordinate compression of its elements to positive integers. For example, the node \([5,8]\) has the child sequence \(\{[5,5],[6,7],[8,8]\}\); sorting these ranges and numbering them gives the child permutation \(\{1,2,3\}\). Similarly, the child permutation of the node \([4,8]\) is \(\{2,1\}\). The child permutation of a node \(u\) is written \(P_u\).
  4. Join node: a node whose child permutation is increasing or decreasing. Formally, a node with \(P_u=\{1,2,\cdots,|S_u|\}\) or \(P_u=\{|S_u|,|S_u|-1,\cdots,1\}\) is called a join node. A leaf has no child permutation; we count it as a join node too.
  5. Cut node: any node that is not a join node.

The figure shows that \([1,10]\) is the only node that is not a join node: its child permutation is \(\{3,1,4,2\}\).

Properties of cut nodes and join nodes

Cut nodes and join nodes are named after their properties. First, one property is entirely obvious: for every node \(u\) of the permutation tree, the union of the ranges in its child sequence is the value range of \(u\), that is, \(\bigcup_{i=1}^{|S_u|}S_u[i]=[u_l,u_r]\).

For a join node \(u\): every subrange of its child sequence forms a contiguous segment. Formally: \(\forall S_u[l\sim r]\), \(\bigcup_{i=l}^rS_u[i]\in I_P\).

For a cut node \(u\): no subrange of its child sequence of length greater than 1 (length here means the number of elements of the child sequence, not the length of the index range) forms a contiguous segment. Formally: \(\forall S_u[l\sim r],l<r\), \(\bigcup_{i=l}^rS_u[i]\notin I_P\).

The property of join nodes is easy to prove. The child permutation of a join node is either increasing or decreasing, and the value ranges follow one another end to end, so any contiguous subsequence (a subrange) is a contiguous segment.

The property of cut nodes may puzzle many readers: why does no subrange of length greater than \(1\) form a contiguous segment?

Here is a proof by contradiction. Suppose that for some node \(u\) there is a longest range \(S_u[l\sim r]\) of its child sequence that forms a contiguous segment. Then \(A=\bigcup_{i=l}^rS_u[i]\in I_P\), which means that \(A\) is a primitive segment! (Since \(A\) is the longest in the child sequence, there is no contiguous segment that intersects it without one containing the other.) So the permutation tree was not built from all the primitive segments, a contradiction.

Constructing the permutation tree

As for actually constructing the permutation tree, LCA gives a linear-time construction algorithm1. Below we present an \(O(n\log n)\) algorithm that is easier to understand.

Incremental method

We use the incremental method. A stack maintains the permutation forest formed by the first \(i-1\) elements. It must be stressed here that "permutation forest" means that at every moment each node on the stack is either a cut node or a join node. Now consider the current node \(P_i\).

  1. First check whether it can become a child of the node on top of the stack. If it can, make it a child of the top node, then pop the top node and take it as the current node. Repeat until the stack is empty or the current node cannot become a child of the top node.
  2. If it cannot become a child of the top node, see whether several consecutive nodes at the top of the stack can all be merged into one node (how to decide this is described later), and take the merged node as the current node.
  3. Repeat the steps above until neither applies. This ends the increment: push the current node onto the stack.

We now explain this in detail.

The strategy in detail

If the current node can become a child of the top node, then the top node is a join node. If it were a cut node, then after the merge this cut node would contain a contiguous sub-segment, which violates the property of cut nodes. So it must be a join node.

If the current node cannot become a child of the top node, we check whether several consecutive nodes at the top of the stack can be merged together with it. Let \(l\) be the left endpoint of the range of the current node. We compute \(L_i\), the largest left endpoint \(< l\) among the contiguous segments whose right endpoint has index \(i\). The current node is \(P_i\), and we call the top node \(t\).

  1. If \(L_i\) does not exist, the current node clearly cannot be merged.
  2. If \(t_l=L_i\), two nodes are merged, and the result is a join node.
  3. Otherwise the stack must contain a node \(t'\) whose left endpoint is \({t'}_l=L_i\), and everything from the current node to \(t'\) can be merged into a cut node.

Deciding whether a merge is possible

Finally, how do we compute \(L_i\)? A range is a contiguous segment \((P,[l,r])\) exactly when the difference between its maximum and its minimum equals its length minus 1, that is,

\[ \max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i=r-l \]

Moreover, because \(P\) is a permutation, every range \([l,r]\) satisfies

\[ \max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i\ge r-l \]

So we maintain \(\max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i-(r-l)\), and finding a contiguous segment amounts to querying a minimum!

This idea leads naturally to the following algorithm. For the current \(i\) of the incremental process, we maintain an array \(Q\) that holds, for the range \([j,i]\), the difference between its maximum and its minimum, minus its length, plus one. That is,

\[ Q_j=\max_{j\le k\le i}P_k-\min_{j\le k\le i}P_k-(i-j),\ \ 0<j<i \]

Now we want to know whether there is a smallest \(j\) in \(1\sim i-1\) with \(Q_j=0\). This is equivalent to finding the minimum of \(Q_{1\sim i-1}\). The smallest \(j\) found is \(L_i\). If there is none, then \(L_i=i\).

When the \(i\)-th increment ends, however, we must quickly bring the array \(Q\) up to date for \(i+1\). The range \([j,i]\) becomes \([j,i+1]\), and \(Q_j\) changes if \(P_{i+1}>\max\) or \(P_{i+1}<\min\). How does it change? If \(P_{i+1}>\max\), we subtract \(\max\) from \(Q_j\) and then add \(P_{i+1}\), and \(Q_j\) is up to date. The case \(P_{i+1}<\min\) is similar and amounts to \(Q_j=Q_j+\min-P_{i+1}\).

What if, for a range \([x,y]\), the ranges \(P_{x\sim i},P_{x+1\sim i},P_{x+2\sim i},\cdots,P_{y\sim i}\) all have the same \(\max\)? As you have noticed, we are then doing a range addition. Likewise, when \(P_{x\sim i},P_{x+1\sim i},\cdots,P_{y\sim i}\) all have the same \(\min\), it is again a range addition. The updates of \(\max\) and of \(\min\) are independent of each other, so each can be done on its own.

The maintenance of \(Q\) can therefore be described as follows:

  1. Find the largest \(j\) such that \(P_{j}>P_{i+1}\). Clearly all the numbers of \(P_{j+1\sim i}\) are less than \(P_{i+1}\), so the maximum has to be updated in \(Q_{j+1\sim i}\). Since \(P_{i},\max(P_i,P_{i-1}),\max(P_i,P_{i-1},P_{i-2}),\cdots,\max(P_i,P_{i-1},\cdots,P_{j+1})\) is (non-strictly) increasing, each stretch with the same \(\max\) gets the same update, which is a range addition.
  2. Update \(\min\) in the same way.
  3. Subtract \(1\) from every \(Q_j\), because the length of the range grows by \(1\).
  4. Query \(L_i\), that is, the index at which the minimum of \(Q\) is attained.

That's right, a segment tree can maintain \(Q\)! One question remains: how do we find the stretches over which \(\max/\min\) stays the same? With monotonic stacks! Maintain two monotonic stacks, one for each of \(\max/\min\). Clearly the ranges whose endpoints are two adjacent elements of a stack have the same \(\max/\min\), so we simply update the segment tree while maintaining the monotonic stacks.

See the code for the details of the maintenance.

After so much dry explanation you are probably lost in the fog, so let us look at a picture first. Warning: it is a long one!

p2

Implementation

Finally, here is an implementation for reference. The code is taken from Damibing's blog, with some comments added.

  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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <algorithm>
#include <cstdio>
using namespace std;
constexpr int N = 200010;

int n, m, a[N], st1[N], st2[N], tp1, tp2, rt;
int L[N], R[N], M[N], id[N], cnt, typ[N], bin[20], st[N], tp;

// the source problem of this code should be CERC2017 Intrinsic Interval
// the array a is the permutation of that problem
// st1 and st2 are the two monotonic stacks, tp1 and tp2 are their tops, rt is the root of the permutation tree
// the arrays L and R hold the left and right endpoints of a permutation tree node; the role of the array M is explained where the permutation tree is built
// id stores the index of the node for each position of the permutation, typ marks a node as a cut node or a join node
// st is the stack that stores the indices of permutation tree nodes, tp is its top
struct RMQ {  // precompute RMQ (Max & Min)
  int lg[N], mn[N][17], mx[N][17];

  void chkmn(int& x, int y) {
    if (x > y) x = y;
  }

  void chkmx(int& x, int y) {
    if (x < y) x = y;
  }

  void build() {
    for (int i = bin[0] = 1; i < 20; ++i) bin[i] = bin[i - 1] << 1;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) mn[i][0] = mx[i][0] = a[i];
    for (int i = 1; i < 17; ++i)
      for (int j = 1; j + bin[i] - 1 <= n; ++j)
        mn[j][i] = min(mn[j][i - 1], mn[j + bin[i - 1]][i - 1]),
        mx[j][i] = max(mx[j][i - 1], mx[j + bin[i - 1]][i - 1]);
  }

  int ask_mn(int l, int r) {
    int t = lg[r - l + 1];
    return min(mn[l][t], mn[r - bin[t] + 1][t]);
  }

  int ask_mx(int l, int r) {
    int t = lg[r - l + 1];
    return max(mx[l][t], mx[r - bin[t] + 1][t]);
  }
} D;

// maintain L_i

struct SEG {  // segment tree
#define ls (k << 1)
#define rs (k << 1 | 1)
  int mn[N << 1], ly[N << 1];  // range addition; range minimum

  void pushup(int k) { mn[k] = min(mn[ls], mn[rs]); }

  void mfy(int k, int v) { mn[k] += v, ly[k] += v; }

  void pushdown(int k) {
    if (ly[k]) mfy(ls, ly[k]), mfy(rs, ly[k]), ly[k] = 0;
  }

  void update(int k, int l, int r, int x, int y, int v) {
    if (l == x && r == y) {
      mfy(k, v);
      return;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if (y <= mid)
      update(ls, l, mid, x, y, v);
    else if (x > mid)
      update(rs, mid + 1, r, x, y, v);
    else
      update(ls, l, mid, x, mid, v), update(rs, mid + 1, r, mid + 1, y, v);
    pushup(k);
  }

  int query(int k, int l, int r) {  // query the position of a 0
    if (l == r) return l;
    pushdown(k);
    int mid = (l + r) >> 1;
    if (!mn[ls])
      return query(ls, l, mid);
    else
      return query(rs, mid + 1, r);
    // if no position holds 0, this automatically returns the position you are currently querying
  }
} T;

int o = 1, hd[N], dep[N], fa[N][18];

struct Edge {
  int v, nt;
} E[N << 1];

void add(int u, int v) {  // add an edge of the tree
  E[o] = Edge{v, hd[u]};
  hd[u] = o++;
}

void dfs(int u) {
  for (int i = 1; bin[i] <= dep[u]; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int i = hd[u]; i; i = E[i].nt) {
    int v = E[i].v;
    dep[v] = dep[u] + 1;
    fa[v][0] = u;
    dfs(v);
  }
}

int go(int u, int d) {
  for (int i = 0; i < 18 && d; ++i)
    if (bin[i] & d) d ^= bin[i], u = fa[u][i];
  return u;
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  u = go(u, dep[u] - dep[v]);
  if (u == v) return u;
  for (int i = 17; ~i; --i)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}

// check whether the current range is a contiguous segment
bool judge(int l, int r) { return D.ask_mx(l, r) - D.ask_mn(l, r) == r - l; }

// build the tree
void build() {
  for (int i = 1; i <= n; ++i) {
    // monotonic stacks
    // the minimum over the range [st1[tp1-1]+1,st1[tp1]] is a[st1[tp1]]
    // popping it now means adding back the Min that was subtracted in excess.
    // the leaf at position j of the segment tree holds, for the range from j to the current i,
    // Max{j,i}-Min{j,i}-(i-j)
    // the range addition is just a Tag.
    // the monotonic stacks are maintained to help the segment tree go from i-1 to i.
    // once it is updated to i, querying the global minimum is enough to know whether there is a solution

    while (tp1 && a[i] <= a[st1[tp1]])  // increasing monotonic stack, maintains Min
      T.update(1, 1, n, st1[tp1 - 1] + 1, st1[tp1], a[st1[tp1]]), tp1--;
    while (tp2 && a[i] >= a[st2[tp2]])
      T.update(1, 1, n, st2[tp2 - 1] + 1, st2[tp2], -a[st2[tp2]]), tp2--;

    T.update(1, 1, n, st1[tp1] + 1, i, -a[i]);
    st1[++tp1] = i;
    T.update(1, 1, n, st2[tp2] + 1, i, a[i]);
    st2[++tp2] = i;

    id[i] = ++cnt;
    L[cnt] = R[cnt] = i;  // here L,R are the left and right endpoints of the range of the node
    int le = T.query(1, 1, n), now = cnt;
    while (tp && L[st[tp]] >= le) {
      if (typ[st[tp]] && judge(M[st[tp]], i)) {
        // check whether it can become a child; if it can, do it
        R[st[tp]] = i, M[st[tp]] = L[now], add(st[tp], now), now = st[tp--];
      } else if (judge(L[st[tp]], i)) {
        typ[++cnt] = 1;  // a join node is always created this way
        L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now];
        // the array M records the left endpoint of the rightmost child of a node; the check above for becoming a child uses it
        add(cnt, st[tp--]), add(cnt, now);
        now = cnt;
      } else {
        add(++cnt, now);  // create a new node and add now as its child
        // as long as the nodes from the current one on do not form a contiguous segment, keep merging,
        // until we find a node with which they form a contiguous segment. We are certain to find such
        // a node.
        do add(cnt, st[tp--]);
        while (tp && !judge(L[st[tp]], i));
        L[cnt] = L[st[tp]], R[cnt] = i, add(cnt, st[tp--]);
        now = cnt;
      }
    }
    st[++tp] = now;  // the increment is over: push the current node onto the stack

    T.update(1, 1, n, 1, i, -1);  // the right endpoint of the range moves one step to the right, so subtract 1 everywhere
  }

  rt = st[1];  // the node left on the stack at the end is the root
}

// two cases: the lca is a cut node or a join node; leaves are treated as cut nodes here
void query(int l, int r) {
  int x = id[l], y = id[r];
  int z = lca(x, y);
  if (typ[z] & 1)
    l = L[go(x, dep[x] - dep[z] - 1)], r = R[go(y, dep[y] - dep[z] - 1)];
  // join nodes are special-cased here because this join node is not necessarily the smallest contiguous segment containing l, r.
  // The subranges of the range that a join node represents are contiguous segments too, and one stretch of it is all we need.
  else
    l = L[z], r = R[z];
  printf("%d %d\n", l, r);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  D.build();
  build();
  dfs(rt);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    query(x, y);
  }
  return 0;
}

// 20190612
// permutation tree

Damibing's blog: [Study Notes] Permutation Tree (in Chinese)


  1. Cheng'ao Liu. Simple Data Structures for Contiguous Segments (in Chinese). WC2019 participant talks. ↩