AIOJ

Segment tree merging and splitting are common techniques for segment trees, often used when a value segment tree maintains a multiset.

For example, suppose there are several operations at some nodes of a tree. If information from child nodes needs to be passed upward to their parents, and the information at each individual node is convenient to maintain with a segment tree, the segment tree merging technique can be used to control the overall complexity.

Segment Tree Merging

Process

As the name suggests, segment tree merging means building a new segment tree whose every node is the result of merging the corresponding nodes of two original segment trees. It is often used to maintain information on a tree or graph.

Clearly, it is impossible to build a new full segment tree every time, so we need the dynamic-opening segment tree described above.

The process of segment tree merging is essentially quite brute-force:

Suppose the two segment trees are A and B. We recursively merge them starting from node 1.

When the recursion reaches a node, if the corresponding node in either tree A or tree B is empty, return the corresponding node in the other tree directly; this uses the property of a dynamically opened segment tree.

If the recursion reaches a leaf, merge the corresponding nodes of the two trees.

Finally, update the current node from its children and return it.

Complexity of Segment Tree Merging

Clearly, for two full segment trees, one merge operation has complexity $O(n)$ . In practice, however, value segment trees are usually used, and the total number of nodes in all segment trees to be merged is not much larger than $n$ . Moreover, a segment tree is generally not merged repeatedly. Thus, the total number of nodes added is roughly on the order of $n\log n$ , and the total complexity of merging all segment trees is also on the order of $O(n\log n)$ . In some cases, of course, a meldable heap may be a better choice.

Implementation

int merge(int a, int b, int l, int r) {
  if (!a) return b;
  if (!b) return a;
  if (l == r) {
    // do something...
    return a;
  }
  int mid = (l + r) >> 1;
  tr[a].l = merge(tr[a].l, tr[b].l, l, mid);
  tr[a].r = merge(tr[a].r, tr[b].r, mid + 1, r);
  pushup(a);
  return a;
}

Example Problems

luogu P4556 [Vani Has a Date] Tail of a Rainy Day / [Template] Segment Tree Merging

Solution

A template problem for segment tree merging. Use differences to turn tree modifications into point modifications, then perform segment tree merging during a DFS from the leaves upward to count the answer.

Reference Code

#include <iostream>
#include <vector>
using namespace std;
int n, fa[100005][22], dep[100005], rt[100005];
int sum[5000005], cnt = 0, res[5000005], ls[5000005], rs[5000005];
int m, ans[100005];
vector<int> v[100005];

void update(int x) {
  if (sum[ls[x]] < sum[rs[x]]) {
    res[x] = res[rs[x]];
    sum[x] = sum[rs[x]];
  } else {
    res[x] = res[ls[x]];
    sum[x] = sum[ls[x]];
  }
}

int merge(int a, int b, int x, int y) {
  if (!a) return b;
  if (!b) return a;
  if (x == y) {
    sum[a] += sum[b];
    return a;
  }
  int mid = (x + y) >> 1;
  ls[a] = merge(ls[a], ls[b], x, mid);
  rs[a] = merge(rs[a], rs[b], mid + 1, y);
  update(a);
  return a;
}

int add(int id, int x, int y, int co, int val) {
  if (!id) id = ++cnt;
  if (x == y) {
    sum[id] += val;
    res[id] = co;
    return id;
  }
  int mid = (x + y) >> 1;
  if (co <= mid)
    ls[id] = add(ls[id], x, mid, co, val);
  else
    rs[id] = add(rs[id], mid + 1, y, co, val);
  update(id);
  return id;
}

void initlca(int x) {
  for (int i = 0; i <= 20; i++) fa[x][i + 1] = fa[fa[x][i]][i];
  for (int i : v[x]) {
    if (i == fa[x][0]) continue;
    dep[i] = dep[x] + 1;
    fa[i][0] = x;
    initlca(i);
  }
}

int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int d = dep[x] - dep[y], i = 0; d; d >>= 1, i++)
    if (d & 1) x = fa[x][i];
  if (x == y) return x;
  for (int i = 20; i >= 0; i--)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}

void cacl(int x) {
  for (int i : v[x]) {
    if (i == fa[x][0]) continue;
    cacl(i);
    rt[x] = merge(rt[x], rt[i], 1, 100000);
  }
  ans[x] = res[rt[x]];
  if (sum[rt[x]] == 0) ans[x] = 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  initlca(1);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    rt[a] = add(rt[a], 1, 100000, c, 1);
    rt[b] = add(rt[b], 1, 100000, c, 1);
    int t = lca(a, b);
    rt[t] = add(rt[t], 1, 100000, c, -1);
    rt[fa[t][0]] = add(rt[fa[t][0]], 1, 100000, c, -1);
  }
  cacl(1);
  for (int i = 1; i <= n; i++) cout << ans[i] << endl;
  return 0;
}

Segment Tree Splitting

Process

The essence of segment tree splitting is the reverse of segment tree merging. Segment tree splitting applies only to ordered sequences; splitting an unordered sequence is meaningless. It is commonly used with dynamically opened value segment trees.

When both splitting and merging are present, note that nodes must be reclaimed during merging to avoid possible duplicate node occupancy during splitting.

From a segment tree whose interval is $[1,N]$ , split out $[l,r]$ and build a new tree:

Recursively split from node 1. If the node does not exist, or its represented interval $[s,t]$ has no intersection with $[l,r]$ , return immediately.

When $[s,t]$ intersects $[l,r]$ , create a new node.

When $[s,t]$ is contained in $[l,r]$ , attach the current node directly below the new tree and sever the old edge.

Complexity of Segment Tree Splitting

At most $\log n$ edges can be severed, so the time complexity of each split is $O(\log⁡ n)$ , which is the same as the complexity of a range query.

Implementation

void split(int &p, int &q, int s, int t, int l, int r) {
  if (t < l || r < s) return;
  if (!p) return;
  if (l <= s && t <= r) {
    q = p;
    p = 0;
    return;
  }
  if (!q) q = New();
  int m = s + t >> 1;
  if (l <= m) split(ls[p], ls[q], s, m, l, r);
  if (m < r) split(rs[p], rs[q], m + 1, t, l, r);
  push_up(p);
  push_up(q);
}

Example Problems

P5494 Template: Segment Tree Splitting

Solution

A template problem for segment tree splitting; split out $[x,y]$ .

Merge tree $t$ into tree $p$ : perform one merge.
In tree $p$ , insert $x$ copies of $q$ : perform a point modification.
Query the number of values in $[x,y]$ : perform a range sum query.
Query the $k$ -th smallest value.

Reference Code

#include <iostream>
using namespace std;
constexpr int N = 2e5 + 10;
int n, m;
int idx = 1;
long long sum[N << 5];
int ls[N << 5], rs[N << 5], root[N << 2], rub[N << 5], cnt, tot;

// memory allocation and reclamation
int New() { return cnt ? rub[cnt--] : ++tot; }

void Del(int &p) {
  ls[p] = rs[p] = sum[p] = 0;
  rub[++cnt] = p;
  p = 0;
}

void push_up(int p) { sum[p] = sum[ls[p]] + sum[rs[p]]; }

void build(int s, int t, int &p) {
  if (!p) p = New();
  if (s == t) {
    cin >> sum[p];
    return;
  }
  int m = (s + t) >> 1;
  build(s, m, ls[p]);
  build(m + 1, t, rs[p]);
  push_up(p);
}

// point modification
void update(int x, int c, int s, int t, int &p) {
  if (!p) p = New();
  if (s == t) {
    sum[p] += c;
    return;
  }
  int m = (s + t) >> 1;
  if (x <= m)
    update(x, c, s, m, ls[p]);
  else
    update(x, c, m + 1, t, rs[p]);
  push_up(p);
}

// merge
int merge(int p, int q, int s, int t) {
  if (!p || !q) return p + q;
  if (s == t) {
    sum[p] += sum[q];
    Del(q);
    return p;
  }
  int m = (s + t) >> 1;
  ls[p] = merge(ls[p], ls[q], s, m);
  rs[p] = merge(rs[p], rs[q], m + 1, t);
  push_up(p);
  Del(q);
  return p;
}

// split
void split(int &p, int &q, int s, int t, int l, int r) {
  if (t < l || r < s) return;
  if (!p) return;
  if (l <= s && t <= r) {
    q = p;
    p = 0;
    return;
  }
  if (!q) q = New();
  int m = (s + t) >> 1;
  if (l <= m) split(ls[p], ls[q], s, m, l, r);
  if (m < r) split(rs[p], rs[q], m + 1, t, l, r);
  push_up(p);
  push_up(q);
}

long long query(int l, int r, int s, int t, int p) {
  if (!p) return 0;
  if (l <= s && t <= r) return sum[p];
  int m = (s + t) >> 1;
  long long ans = 0;
  if (l <= m) ans += query(l, r, s, m, ls[p]);
  if (m < r) ans += query(l, r, m + 1, t, rs[p]);
  return ans;
}

int kth(int s, int t, int k, int p) {
  if (s == t) return s;
  int m = (s + t) >> 1;
  long long left = sum[ls[p]];
  if (k <= left)
    return kth(s, m, k, ls[p]);
  else
    return kth(m + 1, t, k - left, rs[p]);
}

int main() {
  cin >> n >> m;
  build(1, n, root[1]);
  while (m--) {
    int op;
    cin >> op;
    if (!op) {
      int p, x, y;
      cin >> p >> x >> y;
      split(root[p], root[++idx], 1, n, x, y);
    } else if (op == 1) {
      int p, t;
      cin >> p >> t;
      root[p] = merge(root[p], root[t], 1, n);
    } else if (op == 2) {
      int p, x, q;
      cin >> p >> x >> q;
      update(q, x, 1, n, root[p]);
    } else if (op == 3) {
      int p, x, y;
      cin >> p >> x >> y;
      cout << query(x, y, 1, n, root[p]) << endl;
    } else {
      int p, k;
      cin >> p >> k;
      if (sum[root[p]] < k)
        cout << -1 << endl;
      else
        cout << kth(1, n, k, root[p]) << endl;
    }
  }
}

Segment Tree Merging & Splitting

Segment Tree Merging

Process

Implementation

Example Problems

Segment Tree Splitting

Process

Implementation

Example Problems

Problems