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:
- \(|P|=n\).
- \(\forall i,P_i\in[1,n]\).
-
\(\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:
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:
- \(A\subseteq B\iff x\le a\wedge b\le y\).
- \(A=B\iff a=x\wedge b=y\).
- \(A\cap B=(P,[\max(a,x),\min(b,y)])\).
- \(A\cup B=(P,[\min(a,x),\max(b,y)])\).
- \(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:
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.
- Value range: for a node \(u\), we write \([u_l,u_r]\) for its value range.
- 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\).
- 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\).
- 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.
- 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\).
- 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.
- 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.
- 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\).
- If \(L_i\) does not exist, the current node clearly cannot be merged.
- If \(t_l=L_i\), two nodes are merged, and the result is a join node.
- 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,
Moreover, because \(P\) is a permutation, every range \([l,r]\) satisfies
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,
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:
- 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.
- Update \(\min\) in the same way.
- Subtract \(1\) from every \(Q_j\), because the length of the range grows by \(1\).
- 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!
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 | |
References and links
Damibing's blog: [Study Notes] Permutation Tree (in Chinese)
-
Cheng'ao Liu. Simple Data Structures for Contiguous Segments (in Chinese). WC2019 participant talks. ↩
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Ir1d, sshwy, Xeonacid, abc1763613206, 24OI-bot, ouuan, xyjg, QAQAutoMaton, H-J-Granger, StudyingFather, zyouxam, Enter-tainer, swiftqwq, diauweb, ksyx, Tiphereth-A, r-value, alphagocc, Early0v0, lailai0916 (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.