Decomposition Tree

The problem of segments

We begin with a fresh and simple problem:

For a permutation of $1-n$, call an interval with a consecutive value range a segment. Find the number of segments in 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 glance, maintaining the set of values in an interval seems necessary, which does not look very friendly in terms of complexity. A segment tree can query whether an interval is a segment, but it is not very suitable for counting the number of segments.

Here we introduce this wonderful data structure—the decomposition tree!

Consecutive segments

Before introducing the decomposition tree, let us first state some prerequisites. The definition in the LCA lecture notes is not easy to understand, so for the reader's convenience, here are some less rigorous but easier-to-understand definitions.

Permutations and consecutive segments

Permutation: An $n$-order permutation $P$ is a sequence of size $n$ in which $P_i$ takes every value in $1,2,\cdots,n$. More formally, an $n$-order permutation $P$ is an ordered set satisfying:

1. $|P|=n$.

2. $\forall i,P_i\in[1,n]$.

3. $\nexists i,j\in[1,n],P_i=P_j$.

   Consecutive segment: For a permutation $P$, define a consecutive segment $(P,[l,r])$ as an interval $[l,r]$ whose value range $P_{l\sim r}$ is consecutive. More formally, a consecutive segment of $P$ is an interval $[l,r]$ satisfying:

$$(\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 consecutive segment, denoted by $(P,\varnothing)$.

Let the set of all consecutive segments of $P$ be $I_P$, and include $(P,\varnothing)\in I_P$.

Operations on consecutive segments

Since a consecutive segment is defined by an interval and its value range, we can define intersection, union, and difference operations on consecutive segments.

Let $A=(P,[a,b]),B=(P,[x,y])$, where $A,B\in I_P$. The relations and operations on consecutive segments are:

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 operations are simply the usual set intersection, union, and difference applied to intervals.

Properties of consecutive segments

Some properties of consecutive segments are immediate. 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$.

Proof? The proof is essentially just the operations of set intersection, union, and difference.

Decomposition trees

Now we reach the main point. You may have guessed that a decomposition tree is a tree formed by consecutive segments. However, a permutation may have as many as $O(n^2)$ consecutive segments, so we need to extract the more fundamental consecutive segments to form the decomposition tree.

Strong intervals

The full name of this definition is actually strong consecutive segment, but strong segment is more concise.

For a permutation $P$, a strong segment $M$ is an element of $I_P$ such that there is no consecutive segment that intersects it without containing it. Formally, $X\in I_P$ is a strong segment if $\forall A\in I_P,\ X\cap A= (P,\varnothing)\vee X\subseteq A\vee A\subseteq X$.

Let the set of all strong segments be $M_P$. Clearly, $(P,\varnothing)\in M_P$.

Clearly, strong segments are either disjoint or nested. Moreover, a consecutive segment can be formed from several pairwise disjoint strong segments. The largest strong segment is the permutation itself, which contains every other strong segment. Thus strong segments form a tree structure, which we call a decomposition tree. More precisely, the decomposition tree of permutation $P$ consists of all strong segments of $P$.

After all these definitions, we should have a picture. Consider the permutation $P=\{9,1,10,3,2,5,7,6,8,4\}$. Its strong segments form the following decomposition tree:

The strong segments are not labeled in the figure. Every node represents a strong segment. We label only the value range of each strong segment. For example, node $[5,8]$ represents the strong segment $(P,[6,9])=\{5,7,6,8\}$. This raises a question: what are decomposition and union nodes?

Decomposition and union nodes

We give the definitions directly and discuss their correctness later.

1. Value interval: For a node $u$, write $[u_l,u_r]$ for its value interval.
2. Child sequence: For a node $u$ in the decomposition tree, suppose its child nodes form an ordered sequence whose elements are value intervals (a single number $x$ can be understood as the interval $[x,x]$). We call this sequence the child sequence and denote it by $S_u$.
3. Child permutation: Discretize the elements of a child sequence $S_u$ into positive integers; the resulting permutation is the child permutation. For example, for node $[5,8]$, its child sequence is $\{[5,5],[6,7],[8,8]\}$. Sorting the intervals and numbering them gives the child permutation $\{1,2,3\}$. Similarly, the child permutation of node $[4,8]$ is $\{2,1\}$. Denote the child permutation of node $u$ by $P_u$.
4. Union node: A node whose child permutation is in increasing or decreasing order is a union node. Formally, a node satisfying $P_u=\{1,2,\cdots,|S_u|\}$ or $P_u=\{|S_u|,|S_u-1|,\cdots,1\}$ is a union node. A leaf has no child permutation, and is also considered a union node.
5. Decomposition node: Any node that is not a union node.

As can be seen from the figure, only $[1,10]$ is not a union node, because its child permutation is $\{3,1,4,2\}$. The interval $[1,10]$ is therefore the only one that is not a union node.

Properties of decomposition and union nodes

The names decomposition node and union node come from their properties. First, an obvious property is that for any node $u$ in the decomposition tree, the union of the intervals in its child sequence is the value interval of $u$, namely $\bigcup_{i=1}^{|S_u|}S_u[i]=[u_l,u_r]$.

For a union node $u$, every subinterval of its child sequence forms a consecutive segment. Formally, $\forall S_u[l\sim r]$, we have $\bigcup_{i=l}^rS_u[i]\in I_P$.

For a decomposition node $u$, every subinterval of its child sequence of length greater than 1 (where length means the number of elements in the child sequence, not the length of the index interval) does not form a consecutive segment. Formally, $\forall S_u[l\sim r],l<r$, we have $\bigcup_{i=l}^rS_u[i]\notin I_P$.

The property of a union node is easy to prove. Its child permutation is either increasing or decreasing, and the value intervals are adjacent, so every consecutive sub-sequence (interval) is a consecutive segment.

The property of a decomposition node may be less intuitive: why does every subinterval of length greater than $1$ fail to form a consecutive segment?

Use contradiction. Suppose that for a node $u$, the longest interval $S_u[l\sim r]$ in its child sequence forms a consecutive segment. Then $A=\bigcup_{i=l}^rS_u[i]\in I_P$, which means that $A$ is a strong segment! (Because $A$ is the longest interval in the child sequence, there is no consecutive segment intersecting it without containing it.) Then the decomposition tree was not formed from all strong segments, a contradiction.

Constructing the decomposition tree

For constructing a decomposition tree, LCA provides a linear-time construction algorithm[^ref1]. Below is a relatively easy-to-understand $O(n\log n)$ algorithm.

Incremental method

Consider the incremental method. Use a stack to maintain the decomposition forest formed by the first $i-1$ elements. It is important to emphasize that a decomposition forest means that, at every moment, each node in the stack is either a decomposition node or a union node. Now consider the current node $P_i$.

1. First check whether it can become a child of the top node of the stack. If so, make it a child of the top node, then pop the top node and treat it as the current node. Repeat until the stack is empty or the current node can no longer become a child of the top node.
2. If it cannot become a child of the top node, check whether several consecutive nodes at the top of the stack can be merged with the current node into one node (the method for checking whether merging is possible is given below), and use the merged node as the current node.
3. Repeat the above process until no further operation is possible. Then finish this incremental step and push the current node onto the stack.

Let us explain this carefully.

Concrete strategy

If the current node can become a child of the top node, we regard the top node as a union node. If it were a decomposition node, merging it would create a consecutive subsegment under that decomposition node, violating the property of a decomposition node. Therefore it must be a union node.

If the current node cannot become a child of the top node, check whether several consecutive nodes at the top can be merged with the current node. Let $l$ be the left endpoint of the interval containing the current node. Compute $L_i$, the maximum left endpoint $< l$ among consecutive segments whose right endpoint index is $i$. Let the current node be $P_i$ and the top node be $t$.

1. If $L_i$ does not exist, the current node clearly cannot be merged.
2. If $t_l=L_i$, these are two nodes being merged, and the result is a union node.
3. Otherwise, there must be a node $t'$ in the stack whose left endpoint is ${t'}_l=L_i$, and the nodes from the current node through $t'$ can be merged to form a decomposition node.

Checking whether merging is possible

Finally, let us consider how to handle $L_i$. A consecutive segment $(P,[l,r])$ is equivalent to the range difference being equal to the interval length minus 1, namely

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

Since P is a permutation, every interval $[l,r]$ satisfies

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

Thus we maintain $\max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i-(r-l)$; finding a consecutive segment is equivalent to querying for a minimum!

With this idea, the algorithm is not difficult to derive. For the current $i$ in the incremental process, maintain an array $Q$ representing the range difference minus the length of interval $[j,i]$, namely

Q_j=\max_{j\le k\le i}P_k-\min_{j\le k\le i}P_k-(i-j),\ \ 0<j\max$ 或者 $P_{i+1}<\min$ 都会造成 $Q_j$ 发生变化．如何变化？如果 $P_{i+1}>\max$，相当于我们把 $Q_j$ 先减掉 $\max$ 再加上 $P_{i+1}$ 就完成了 $Q_j$ 的更新；$P_{i+1}<\min$ 同理，相当于 $Q_j=Q_j+\min-P_{i+1}$. Now suppose that for an interval $[x,y]$, the interval $\max$ values of $P_{x\sim i},P_{x+1\sim i},P_{x+2\sim i},\cdots,P_{y\sim i}$ are all equal. Then we are performing a range-add operation. Likewise, when the interval $\min$ values of $P_{x\sim i},P_{x+1\sim i},\cdots,P_{y\sim i}$ are all equal, that is also a range-add operation. The updates of $\max$ and $\min$ are independent, so they can be maintained separately. Therefore, $Q$ can be maintained as follows: 1. Find the largest $j$ such that $P_{j}>P_{i+1}$. Then all numbers in $P_{j+1\sim i}$ are smaller than $P_{i+1}$, so update the $\max$ values of $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})$ are nondecreasing, apply the same update to each maximal equal block; this is a range-add operation. 2. Update the $\min$ analogously. 3. Subtract $1$ from every $Q_j$, because the interval length increases by $1$. 4. Query $L_i$, namely the **index** at which the minimum of $Q$ occurs. Indeed, we can use a segment tree to maintain $Q$! There is still one question: how do we find blocks on which $\max/\min$ is equal? Use monotonic stacks! Maintain two monotonic stacks for $\max/\min$. Then the $\max/\min$ on the interval whose endpoints are two adjacent stack elements is equal, so update the segment tree while maintaining the monotonic stacks. The concrete maintenance method is shown in the code. That was a lot of dry explanation, and it may have been difficult to follow, so let us look at a picture first. Long-image warning!  ### Implementation Here is an implementation for reference. The code is from [Damibing's blog](https://www.cnblogs.com/Paul-Guderian/p/11020708.html), with some comments added. ```cpp #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 original problem of this code is CERC2017 Intrinsic Interval // The array a is the permutation in the original problem // st1 and st2 are the two monotonic stacks; tp1 and tp2 are their respective tops, and rt is the root of the decomposition tree // The L and R arrays store the left and right endpoints of each decomposition-tree node; the role of M is described during tree construction // id stores the node number corresponding to each position in the permutation; typ marks a decomposition or union node // st stores decomposition-tree node numbers, and tp is its top struct RMQ { // Preprocessed 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 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 there is no position containing 0, the current query position is returned automatically } } 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 a tree edge 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]; } // Determine whether the current interval is a consecutive 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 on [st1[tp1-1]+1,st1[tp1]] is a[st1[tp1]] // Popping it means adding back the Min that was subtracted too many times. // The segment-tree leaf at position j stores, from j to the current i, // Max{j,i}-Min{j,i}-(i-j) // Range addition is only a Tag. // The monotonic stacks help the segment tree update from i-1 to i. // After updating to i, querying the global minimum tells whether a solution exists. while (tp1 && a[i] <= a[st1[tp1]]) // Increasing stack, maintaining 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 interval represented by 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 so, 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 union node is always created in this way. L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now]; // M stores the left endpoint of the rightmost child of the node, add(cnt, st[tp--]), add(cnt, now); now = cnt; } else { add(++cnt, now); // and is used above to check whether a node can become a child. // Create a new node and add now as a child. // If the current node cannot form a consecutive segment, merge. // Continue until finding a node that can form a consecutive segment. Such a node is guaranteed to exist. 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; // Finish the incremental step and push the current node T.update(1, 1, n, 1, i, -1); // The right endpoint moves one position right, so subtract 1 everywhere. } rt = st[1]; // The last node remaining in the stack is the root. } // Divide the LCA into decomposition or union; regard leaves as decomposition nodes. 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)]; // The special handling of a union node is needed because this union node is not necessarily the smallest consecutive segment containing l,r. // Since every subinterval represented by a union node is also a consecutive segment, we only need one of them. 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 // Decomposition tree ``` ## References and links [Damibing's blog - Study notes: Decomposition tree](https://www.cnblogs.com/Paul-Guderian/p/11020708.html) [^ref1]: Liu Cheng'ao. Simple consecutive-segment data structure. WC2019 camper exchange.