Divide and Combine Tree

On Segments

We start with a neat problem:

For a permutation of \(1-n\), we call a value-contiguous interval a segment. Find the number of segments in a permutation. For example, \(\{5 ,3 ,4, 1 ,2\}\) has segments: \([1,1],[2,2],[3,3],[4,4],[5,5],[2,3],[4,5],[1,3],[2,5],[1,5]\).

Looking at this, it seems we need to maintain the value set of intervals, which seems quite complex. Segment trees can query whether an interval is a segment, but they aren't great for counting segments.

Here we introduce this magical data structure—the Divide-Combine Tree!

Continuous Segments

Before introducing the Divide-Combine Tree, we first set some prerequisite conditions. Since the definitions given in LCA's course materials are not easy to understand, for the reader's convenience, we give some less rigorous (but easier to understand) definitions.

Permutations and Continuous Segments

Permutation: Define an \(n\)-order permutation \(P\) as a sequence of size \(n\) such that \(P_i\) takes all values \(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\).

   Continuous Segment: For a permutation \(P\), define a continuous segment \((P,[l,r])\) as an interval \([l,r]\) such that the value range of \(P_{l\sim r}\) is contiguous. More formally, for permutation \(P\), a continuous segment 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 consider this an empty continuous segment, denoted as \((P,\varnothing)\).

We denote the set of all continuous segments of permutation \(P\) as \(I_P\), and we consider \((P,\varnothing)\in I_P\).

Operations on Continuous Segments

Continuous segments are defined based on intervals and value ranges, so we can define intersection, union, and difference operations on them.

Define \(A=(P,[a,b]),B=(P,[x,y])\), and \(A,B\in I_P\). Then the relations and operations on continuous segments can be expressed 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]\})\).

Essentially, these operations are just ordinary set intersection, union, and difference applied to intervals.

Properties of Continuous Segments

Some obvious properties of continuous segments. Define \(A,B\in I_P,A \cap B \neq \varnothing,A \notin B,B \notin A\), then we have \(A\cup B,A\cap B,A\setminus B,B\setminus A\in I_P\).

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

Divide-Combine Tree

Alright, now we get to the main point. You might have guessed it: the Divide-Combine Tree is exactly a tree composed of continuous segments. But note that a permutation can have up to \(O(n^2)\) continuous segments, so we need to extract the more fundamental continuous segments to form the Divide-Combine Tree.

Primitive Segments

Actually, the full name of this definition is primitive continuous segment. But the author believes "primitive segment" is more concise.

For a permutation \(P\), we consider a primitive segment \(M\) to be one such that in the set \(I_P\), there exists no continuous segment that intersects it but does not contain it. Formally, we consider \(X\in I_P\) satisfying \(\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\). Obviously, \((P,\varnothing)\in M_P\).

Clearly, primitive segments are either disjoint or have an inclusion relationship. And you'll find that a continuous segment can be composed of several disjoint primitive segments. The largest primitive segment is the entire permutation itself, which contains all other primitive segments. Therefore, we consider that primitive segments can form a tree structure, which we call the Divide-Combine Tree. More strictly, the Divide-Combine Tree of permutation \(P\) consists of all primitive segments of permutation \(P\).

After all these definitions, we need some diagrams. Consider permutation \(P=\{9,1,10,3,2,5,7,6,8,4\}\). Its Divide-Combine Tree formed by primitive segments is as follows:

In the diagram, we did not label the primitive segments. Each node in the diagram represents a primitive segment. We only labeled the value range of each primitive segment. For example, node \([5,8]\) represents the primitive segment \((P,[6,9])=\{5,7,6,8\}\). So here comes a question: What are divide nodes and combine nodes?

Divide Nodes and Combine Nodes

Here we give the definitions directly, and discuss their correctness later.

1. Value Range Interval: For a node \(u\), denote its value range interval as \([u_l,u_r]\).
2. Child Sequence: For a node \(u\) on the Divide-Combine Tree, assume its child nodes form an ordered sequence, where the elements are value range intervals (a single number \(x\) can be understood as interval \([x,x]\)). We call this sequence the child sequence. Denote it as \(S_u\).
3. Child Permutation: For a child sequence \(S_u\), after discretizing its elements into positive integers, the resulting permutation is called the child permutation. For example, for node \([5,8]\), its child sequence is \(\{[5,5],[6,7],[8,8]\}\). After sorting the intervals and labeling them, its child permutation becomes \(\{1,2,3\}\); similarly, the child permutation of node \([4,8]\) is \(\{2,1\}\). Denote the child permutation of node \(u\) as \(P_u\).
4. Combine Node: We consider nodes whose child permutation is either increasing or decreasing as combine nodes. Formally, nodes satisfying \(P_u=\{1,2,\cdots,|S_u|\}\) or \(P_u=\{|S_u|,|S_u-1|,\cdots,1\}\) are called combine nodes. Leaf nodes have no child permutation, but we also consider them as combine nodes.
5. Divide Node: Nodes that are not combine nodes are divide nodes.

From the diagram, we can see that only \([1,10]\) is not a combine node. Because the child permutation of \([1,10]\) is \(\{3,1,4,2\}\).

Properties of Divide Nodes and Combine Nodes

The naming of divide and combine nodes comes from their properties. First, we have a very obvious property: For any node \(u\) in the Divide-Combine Tree, the union of its child sequence intervals is exactly the value range interval of node \(u\). That is, \(\bigcup_{i=1}^{|S_u|}S_u[i]=[u_l,u_r]\).

For a combine node \(u\): any subinterval of its child sequence forms a continuous segment. Formally, \(\forall S_u[l\sim r]\), we have \(\bigcup_{i=l}^rS_u[i]\in I_P\).

For a divide node \(u\): any subinterval of length greater than 1 (here length refers to the number of elements in the child sequence, not the length of the index interval) of its child sequence does not form a continuous segment. Formally, \(\forall S_u[l\sim r],l<r\), we have \(\bigcup_{i=l}^rS_u[i]\notin I_P\).

The property of combine nodes is not hard to prove. Because the child permutation of a combine node is either increasing or decreasing, and the value range intervals are end-to-end connected, any contiguous subsequence (interval) is a continuous segment.

For the property of divide nodes, many readers might not understand: why do any subintervals of length greater than \(1\) not form a continuous segment?

Use proof by contradiction. Assume for a node \(u\), there exists a longest interval \(S_u[l\sim r]\) in its child sequence that forms a continuous segment. Then \(A=\bigcup_{i=l}^rS_u[i]\in I_P\), which means \(A\) is a primitive segment! (Because \(A\) is the longest in the child sequence, so we cannot find a continuous segment that intersects it but does not contain it.) Then you did not use all primitive segments to construct this Divide-Combine Tree. Contradiction.

Construction of the Divide-Combine Tree

For the specific construction of the Divide-Combine Tree, LCA provides a linear construction algorithm¹. Below we present a more understandable \(O(n\log n)\) algorithm.

Incremental Method

We consider the incremental method. Use a stack to maintain the Divide-Combine Forest formed by the first \(i-1\) elements. Here we need to emphasize that Divide-Combine Forest means at any time, nodes in the stack are either divide nodes or combine nodes. Now consider the current node \(P_i\).

1. First, we check if it can become a child of the top node of the stack. If yes, make it a child of the top node, then pop the top node and set it as the current node. Repeat this process until the stack is empty or it cannot become a child of the top node.
2. If it cannot become a child of the top node, check if we can merge several consecutive nodes at the top of the stack into one node (the method to determine whether merging is possible is described later). Take the merged node as the current node.
3. Repeat the above process until no further operations are possible. Then end this increment and directly push the current node onto the stack.

Next, we explain in detail.

Specific Strategy

We believe that if the current point can become a child of the top node, then the top node is a combine node. If it were a divide node, then after merging, this divide node would have a sub-continuous segment, violating the property of divide nodes. Therefore, it must be a combine node.

If it cannot become a child of the top node, then we check if several consecutive nodes at the top of the stack can merge with the current point. Let \(l\) be the left endpoint of the interval where the current point lies. We compute \(L_i\) as the maximum left endpoint \(< l\) among continuous segments with right endpoint index \(i\). The current node is \(P_i\), and the top node of the stack is denoted as \(t\).

1. If \(L_i\) does not exist, then obviously the current node cannot merge;
2. If \(t_l=L_i\), then these two nodes merge, and after merging, it becomes a combine node;
3. Otherwise, there must exist a node \(t'\) in the stack whose left endpoint \({t'}_l=L_i\), then we can merge from the current node to \(t'\) to form a divide node;

Determining Whether Merging is Possible

Finally, we consider how to handle \(L_i\). In fact, a continuous segment \((P,[l,r])\) is equivalent to the interval range (max-min) being equal to the interval length minus 1. That is

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

Moreover, since P is a permutation, for any interval \([l,r]\) we have

\[ \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)\), then finding a continuous segment is equivalent to querying a minimum value!

With the above idea, it's not hard to come up with such an algorithm. For the current \(i\) during the incremental process, we maintain an array \(Q\) representing the range minus length for interval \([j,i]\). 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 if there exists a smallest \(j\) in \(1\sim i-1\) such that \(Q_j=0\). This is equivalent to finding the minimum value of \(Q_{1\sim i-1}\). The smallest \(j\) found is \(L_i\). If none exists, then \(L_i=i\).

But when the \(i\)-th increment ends, we need to quickly update the \(Q\) array to the situation of i+1. The original interval changes from \([j,i]\) to \([j,i+1]\). If \(P_{i+1}>\max\) or \(P_{i+1}<\min\), \(Q_j\) will change. How does it change? If \(P_{i+1}>\max\), it's equivalent to subtracting \(\max\) from \(Q_j\) and then adding \(P_{i+1}\) to complete the update of \(Q_j\); similarly for \(P_{i+1}<\min\), it's equivalent to \(Q_j=Q_j+\min-P_{i+1}\).

Then what if for an interval \([x,y]\), the interval \(\max\) of \(P_{x\sim i},P_{x+1\sim i},P_{x+2\sim i},\cdots,P_{y\sim i}\) are all the same? You've discovered that this is equivalent to performing a range addition operation; similarly, when the interval \(\min\) of \(P_{x\sim i},P_{x+1\sim i},\cdots,P_{y\sim i}\) are all the same, it's also a range addition operation. Meanwhile, the updates of \(\max\) and \(\min\) are independent, so they can be updated separately.

Therefore, our maintenance of \(Q\) can be described as follows:

1. Find the largest \(j\) such that \(P_{j}>P_{i+1}\). Then obviously, all numbers in \(P_{j+1\sim i}\) are less than \(P_{i+1}\), so we need to update the maximum value for \(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) monotonically increasing, we can perform the same update for each segment with the same \(\max\), i.e., a range addition operation.
2. Updating \(\min\) is similar.
3. Subtract \(1\) from every \(Q_j\). Because the interval length increases by \(1\).
4. Query \(L_i\): i.e., query the index where the minimum value of \(Q\) is located.

Yes, we can use a segment tree to maintain \(Q\)! Now there's another problem: how to find the same segment where their \(\max/\min\) are all the same? Use monotonic stacks! Maintain two monotonic stacks for \(\max\) and \(\min\) respectively. Then obviously, for intervals between adjacent elements in the stack, the \(\max/\min\) are the same. So while maintaining the monotonic stacks, we can update the segment tree accordingly.

See the code for specific maintenance methods.

After so much dry explanation, readers might be confused. So let's look at a diagram first. Long image warning!

Implementation

Finally, here is a reference implementation. The code is adapted from 大米饼's blog, with some comments added.

#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 for this code should be CERC2017 Intrinsic Interval
// Array a is the corresponding permutation in the original problem
// st1 and st2 are two monotonic stacks, tp1, tp2 are corresponding stack tops, rt is the root of the Divide-Combine Tree
// Arrays L, R represent the left and right endpoints of the D-C tree node, array M's role is mentioned during construction
// id stores the node number corresponding to a position in the permutation, typ marks whether it's a divide or combine node
// st is the stack storing D-C tree node numbers, tp is its top
struct RMQ {  // Preprocess 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 add; 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 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 position of 0 doesn't exist, it automatically returns the current query position
  }
} 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 edge to tree structure
  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 if current interval is a continuous segment
bool judge(int l, int r) { return D.ask_mx(l, r) - D.ask_mn(l, r) == r - l; }

// Build tree
void build() {
  for (int i = 1; i <= n; ++i) {
    // Monotonic stacks
    // The minimum in interval [st1[tp1-1]+1,st1[tp1]] is a[st1[tp1]]
    // Now popping it means we need to add back the extra subtracted Min.
    // Leaf node j of the segment tree maintains
    // Max{j,i}-Min{j,i}-(i-j) from j to current i.
    // Range add is just a Tag.
    // The purpose of maintaining monotonic stacks is to assist the segment tree update from i-1 to i.
    // After updating to i, we only need to query the global minimum to know if a solution exists.

    while (tp1 && a[i] <= a[st1[tp1]])  // Increasing 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 interval corresponding to 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 if it can become a child, if yes, 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;  // Combine nodes are always constructed this way
        L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now];
        // Here M array records the left endpoint of the rightmost child of a node, used for the above check of whether it can become a child.
        add(cnt, st[tp--]), add(cnt, now);
        now = cnt;
      } else {
        add(++cnt, now);  // Create a new node, add now as a child
        // If starting from the current node cannot form a continuous segment, merge.
        // Until we find a node that can form a continuous segment. And we can always 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;  // Increment ends, push current point onto stack

    T.update(1, 1, n, 1, i, -1);  // Because the right endpoint of the interval moves one step back, overall -1
  }

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

// Depending on whether lca is divide or combine, here leaves are considered as divide.
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)];
  // Special case for combine node because this combine node may not be the smallest continuous segment containing l, r.
  // Because subintervals of the interval represented by a combine node are also continuous segments, and 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
// Divide-Combine Tree

References and Links

大米饼's Blog -【学习笔记】析合树

---

1. Liu Cheng'ao. Simple Continuous Segment Data Structure. WC2019 Camp Exchange. ↩

---

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