AIOJ

Problems combining segment trees with offline queries also appear in the OI field．This technique is also known as segment-tree divide and conquer．

Suppose you need to maintain some information that is present during certain time intervals and answer, offline, what the information is at a particular time．In that case, you can consider using segment-tree divide and conquer．

In practice, segment-tree divide and conquer is often used for the following purposes：

Simulate deletion operations with a data structure that does not originally support deletion but does support undoing operations．For example, a naive disjoint-set union cannot efficiently support deleting edges．
Compute data with different attributes separately．For example, find the answer for all colors other than a particular color．

If this is not clear to you yet, that is fine．We will explain both uses in the example problems．

Process

First, we build a segment tree over time．Each node maintains a vector to store the information that lies within its time interval．

Inserting information into the segment tree is similar to an ordinary segment-tree range update．

Next, we consider how to process the information for every time interval．Starting from the root, we perform divide and conquer while maintaining the current aggregate information; whenever we reach a node, we merge all of that node's information．When backtracking, we undo the contribution from this part．When we finally reach a leaf, its aggregate information is the answer for the corresponding time．

If changing the information takes $O(T(n))$ time, a stack can be used to preserve the changes, allowing them to be undone in $O(T(n))$ time．Undoing does not retain the amortized complexity．

The total time complexity of the entire divide-and-conquer process is $O(n\log n(T(n) + M(n)))$ , where merging information takes $O(M(n))$ time, and the space complexity is $O(n\log n)$ ．

Implementation

#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)

vector<Object> tree[N << 2];  // segment tree

void update(int ql, int qr, Object obj, int i, int l, int r) {  // insertion
  if (ql <= l && r <= qr) {
    tree[i].push_back(obj);
    return;
  }
  if (ql <= mid) update(ql, qr, obj, ls, l, mid);
  if (qr > mid) update(ql, qr, obj, rs, mid + 1, r);
}

stack<Object> sta;  // stack for undoing changes
Object now;         // current aggregate information
Object ans[N];      // answers

void solve(int i, int l, int r) {
  auto lvl = sta.size();  // record how far to undo
  for (Object x : tree[i]) sta.push(now), now = Merge(now, x);  // merge information
  if (l == r)
    ans[i] = now;  // record the answer
  else
    solve(ls, l, mid), solve(rs, mid + 1, r);  // divide and conquer
  while (sta.size() != lvl) {                  // undo changes
    now = sta.top();
    sta.pop();
  }
}

Examples

luogu P5787 Bipartite Graph / [Template] Segment Tree Divide and Conquer

You need to maintain an undirected graph with $n$ vertices and $m$ edges．The $i$ -th edge is $(x_i,y_i)$ , appears during the time interval $[l_i,r_i)$ , and disappears at all other times．

For every time, if the graph at that time is bipartite, output Yes; otherwise, output No．

Solution

Use a disjoint-set union with parity to maintain whether a graph is bipartite, and then apply segment-tree divide and conquer．

Note that a rollback disjoint-set union cannot use path compression; it can only use union by rank．

Reference Code

#include <iostream>
#include <stack>
#include <vector>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

int n, m, k;
constexpr int N = 2e5 + 5;
int fa[N << 1], siz[N << 1];

struct UndoObject {
  int pos, val;

  UndoObject(int p, int v) { pos = p, val = v; }
};

stack<UndoObject> undo_sz, undo_fa;

int find(int x) {
  if (fa[x] == x)
    return x;
  else
    return find(fa[x]);
}

void merge(int u, int v) {
  int x = find(u), y = find(v);
  if (x == y) return;
  if (siz[x] < siz[y]) {
    swap(x, y);
  }
  undo_sz.push(UndoObject(x, siz[x]));
  siz[x] += siz[y];
  undo_fa.push(UndoObject(y, fa[y]));
  fa[y] = x;
}

void undo() {
  fa[undo_fa.top().pos] = undo_fa.top().val;
  undo_fa.pop();
  siz[undo_sz.top().pos] = undo_sz.top().val;
  undo_sz.pop();
}

vector<int> tree[N << 2];

void update(int ql, int qr, int v, int i, int l, int r) {
  if (ql <= l && r <= qr) {
    tree[i].push_back(v);
    return;
  }
  if (ql <= mid) update(ql, qr, v, ls, l, mid);
  if (qr > mid) update(ql, qr, v, rs, mid + 1, r);
}

struct edge {
  int u, v;
} g[N];

vector<bool> ret;

void solve(int i, int l, int r) {
  auto level = undo_fa.size();
  bool ans = true;
  for (int u : tree[i]) {
    int a = find(g[u].u);
    int b = find(g[u].v);
    if (a == b) {
      for (int k = l; k <= r; k++) {
        ret.push_back(false);
      }
      ans = false;
      break;
    }
    merge(g[u].u, g[u].v + n);
    merge(g[u].v, g[u].u + n);
  }
  if (ans) {
    if (l == r) {
      ret.push_back(true);
    } else {
      solve(ls, l, mid);
      solve(rs, mid + 1, r);
    }
  }
  while (undo_fa.size() > level) {
    undo();
  }
}

signed main() {
  cin >> n >> m >> k;
  for (int i = 1; i <= (n << 1); i++) {
    fa[i] = i;
    siz[i] = 1;
  }
  for (int i = 1, l, r; i <= m; i++) {
    cin >> g[i].u >> g[i].v >> l >> r;
    update(l + 1, r, i, 1, 1, k);
  }
  solve(1, 1, k);
  for (bool i : ret) {
    cout << (i ? "Yes" : "No") << '\n';
  }
  return 0;
}

Color Restriction

An undirected graph has $n$ vertices and $m$ edges, with $k$ colors numbered from $0\sim k-1$ ．Each edge has one color．

For each color, determine whether the graph obtained by deleting all edges of that color is connected, and whether it is a tree．

Output the number of colors for which the graph remains connected after deletion and the number of colors for which the resulting graph is a tree．

Solution

For each color, create a time at which no edge of that color is present and all other edges are present．A disjoint-set union is enough to maintain the required information．

Reference Code

#include <bitset>
#include <iostream>
#include <stack>
#include <vector>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

int n, m, k;
constexpr int N = 1e5 + 5;

struct edge {
  int u, v, c;
} g[N];

vector<int> t[N << 2];
int fa[N], siz[N], cnt[N];

void update(int ql, int qr, int v, int i, int l, int r) {
  if (ql > qr) return;
  if (ql <= l && r <= qr) {
    t[i].push_back(v);
    return;
  }
  if (ql <= mid) update(ql, qr, v, ls, l, mid);
  if (qr > mid) update(ql, qr, v, rs, mid + 1, r);
}

stack<pair<int, int>> fas, sizs;

int find(int x) { return fa[x] == x ? x : find(fa[x]); }

void merge(int u, int v) {
  int fu = find(u), fv = find(v);
  if (fu == fv) return;
  if (siz[fu] < siz[fv]) swap(fu, fv);
  fas.push(make_pair(fv, fa[fv]));
  fa[fv] = fu;
  sizs.push(make_pair(fu, siz[fu]));
  siz[fu] += siz[fv];
}

bitset<N> ans;

void solve(int i, int l, int r) {
  unsigned lvl = fas.size();
  for (int eg : t[i]) merge(g[eg].u, g[eg].v);
  if (l == r)
    ans[l] = (siz[find(1)] == n);
  else
    solve(ls, l, mid), solve(rs, mid + 1, r);
  while (fas.size() != lvl) {
    auto p1 = fas.top(), p2 = sizs.top();
    fas.pop(), sizs.pop();
    fa[p1.first] = p1.second;
    siz[p2.first] = p2.second;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    cin >> g[i].u >> g[i].v >> g[i].c;
    g[i].c++;
    update(1, g[i].c - 1, i, 1, 1, k);
    update(g[i].c + 1, k, i, 1, 1, k);
    cnt[g[i].c]++;
  }
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
    siz[i] = 1;
  }
  solve(1, 1, k);
  int ans1 = 0, ans2 = 0;
  for (int i = 1; i <= k; i++) {
    ans1 += ans[i];
    ans2 += (ans[i] && (m - cnt[i]) == (n - 1));
  }
  cout << ans1 << ' ' << ans2;
  return 0;
}

luogu P4219 [BJOI2014] Big Fusion

You need to maintain a forest with $n$ vertices, initially consisting of isolated vertices．

There are $q$ operations, supporting：

A x y Add the edge $(x,y)$ ．
Q x y Output the number of paths passing through the edge $(x,y)$ ．

Offline processing is allowed．

Solution

Since offline processing is allowed, segment-tree divide and conquer comes to mind．

Next, consider how to support operation Q．If the edge $(x,y)$ does not exist, the answer is the size of the connected component containing $x$ multiplied by the size of the connected component containing $y$ ．This can be maintained with a disjoint-set union．

Therefore, split Q into three times $k-1,k,k+1$ ．Here, $k-1$ is the time when the edge ends and $k+1$ is the time when the edge begins．At time $k$ , the edge is absent, which is exactly when the query should be answered．

Reference Code

#include <iostream>
#include <map>
#include <stack>
#include <vector>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

int n, m;
constexpr int N = 1e5 + 5;
int fa[N], siz[N], tim;

struct UndoObject {
  int pos, val;

  UndoObject(int p, int v) { pos = p, val = v; }
};

stack<UndoObject> undo_sz, undo_fa;

int find(int x) {
  if (fa[x] == x)
    return x;
  else
    return find(fa[x]);
}

void merge(int u, int v) {
  int x = find(u), y = find(v);
  if (x == y) return;
  if (siz[x] < siz[y]) {
    swap(x, y);
  }
  undo_sz.push(UndoObject(x, siz[x]));
  siz[x] += siz[y];
  undo_fa.push(UndoObject(y, fa[y]));
  fa[y] = x;
}

void undo() {
  fa[undo_fa.top().pos] = undo_fa.top().val;
  undo_fa.pop();
  siz[undo_sz.top().pos] = undo_sz.top().val;
  undo_sz.pop();
}

vector<pair<int, int>> tree[N << 4];

void update(int ql, int qr, pair<int, int> v, int i, int l, int r) {
  if (ql <= l && r <= qr) {
    tree[i].push_back(v);
    return;
  }
  if (ql <= mid) update(ql, qr, v, ls, l, mid);
  if (qr > mid) update(ql, qr, v, rs, mid + 1, r);
}

map<pair<int, int>, int> tims;

struct ops {
  int l, r;
  pair<int, int> v;
} opp[N << 3];

int opcnt;
map<int, int> queries;
map<int, pair<int, int>> querylr;
int ans[N << 3];

void solve(int i, int l, int r) {
  auto level = undo_fa.size();
  for (auto u : tree[i]) {
    merge(u.first, u.second);
  }
  if (l == r) {
    if (queries[l]) {
      int x = querylr[l].first;
      int y = querylr[l].second;
      // cout<<siz[find(x)]<<' '<<siz[find(y)]<<'\n';
      ans[l] = siz[find(x)] * siz[find(y)];
    }
  } else {
    solve(ls, l, mid);
    solve(rs, mid + 1, r);
  }
  while (undo_fa.size() > level) {
    undo();
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
    siz[i] = 1;
  }
  while (m--) {
    char op;
    int x, y;
    cin >> op >> x >> y;
    if (op == 'A') {
      tims[make_pair(x, y)] = ++tim;
    } else {
      pair<int, int> xy = make_pair(x, y);
      opp[++opcnt] = {tims[xy], (++tim), xy};
      queries[++tim] = 1;
      // cout<<tim<<'\n';
      querylr[tim] = xy;
      tims[xy] = ++tim;
    }
  }
  int tm = ++tim;
  for (auto i : tims) {
    opp[++opcnt] = {tims[i.first], tm, i.first};
  }
  for (int i = 1; i <= opcnt; i++) {
    // cout<<opp[i].l<<' '<<opp[i].r<<' '<<opp[i].v.first<<'
    // '<<opp[i].v.second<<'\n';
    update(opp[i].l, opp[i].r, opp[i].v, 1, 1, tim);
  }
  // cout<<tim<<'\n';
  solve(1, 1, tim);
  for (int i = 1; i <= tim; i++) {
    if (queries[i]) {
      cout << ans[i] << "\n";
    }
  }
  return 0;
}

luogu P2056 [ZJOI2007] Hide and Seek

Given a tree with $n$ vertices, each vertex has one of two colors, black or white．Initially, every vertex is black．There are $q$ operations, supporting：

C x Invert the color of vertex $x$ ．
G Ask for the maximum distance between two black vertices in the tree．If no black vertex exists, output $-1$ ．

Offline processing is allowed．

Solution

First, consider how to maintain the diameter of a set of vertices in the tree．The following deduction is useful：

For a set $S$ and a singleton set $\{P\}$ , if the diameter of $S$ is $(U,V)$ , then the diameter of $S\cap\{P\}$ can only be $(U,V),(U,P)$ , or $(V,P)$ ．

Then consider the original problem．We can maintain the set of black vertices and the several time intervals during which each vertex belongs to the black set (specifically, use a bucket to record the time when it most recently entered the black set)．

It is then natural to process the problem offline and insert all time intervals into a segment tree．We perform divide and conquer on the segment tree; each node records the vertices newly added to the current time interval, and the diameter endpoints of the new vertex set can be found using the deduction above．

Undoing is straightforward: use a stack to record changes to the diameter endpoints．

Reference Code

#include <algorithm>
#include <bitset>
#include <iostream>
#include <stack>
#include <vector>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

constexpr int N = 5e5 + 5, M = 5e5 + 5;

int siz[N], dep[N], father[N], top[N], son[N];
int n, q;

struct edge {
  int nxt, to;
} g[N << 1];

int head[N], ec;

void add(int u, int v) {
  g[++ec].nxt = head[u];
  g[ec].to = v;
  head[u] = ec;
}

void dfs1(int u, int fa) {
  dep[u] = dep[fa] + 1;
  siz[u] = 1;
  father[u] = fa;
  for (int i = head[u]; i; i = g[i].nxt) {
    int v = g[i].to;
    if (v == fa) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[son[u]] < siz[v]) son[u] = v;
  }
}

void dfs2(int u, int fa) {
  if (son[u]) {
    top[son[u]] = top[u];
    dfs2(son[u], u);
  }
  for (int i = head[u]; i; i = g[i].nxt) {
    int v = g[i].to;
    if (v == fa || v == son[u]) continue;
    top[v] = v;
    dfs2(v, u);
  }
}

int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = father[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}

int dis(int x, int y) { return dep[x] + dep[y] - (dep[lca(x, y)] << 1); }

vector<int> t[N << 2];

void update(int ql, int qr, int v, int i, int l, int r) {
  if (ql <= l && r <= qr) {
    t[i].push_back(v);
    return;
  }
  if (ql <= mid) update(ql, qr, v, ls, l, mid);
  if (qr > mid) update(ql, qr, v, rs, mid + 1, r);
}

stack<pair<int, int>> stk;
int u, v;
int ans[M];

void solve(int i, int l, int r) {
  auto lvl = stk.size();
  for (int x : t[i]) {
    stk.push(make_pair(u, v));
    if (!u && !v)
      u = x, v = x;
    else {
      vector<int> vct = {dis(u, v), dis(u, x), dis(v, x)};
      sort(vct.begin(), vct.end(), greater<int>());
      if (vct[0] == dis(u, x))
        v = x;
      else if (vct[0] == dis(x, v))
        u = x;
    }
  }
  if (l == r)
    ans[l] = (!u || !v) ? -1 : dis(u, v);
  else
    solve(ls, l, mid), solve(rs, mid + 1, r);
  while (stk.size() != lvl) {
    auto top = stk.top();
    u = top.first, v = top.second;
    stk.pop();
  }
}

int lst[N];
bitset<N> col;
bitset<M> haveq;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  top[1] = 1;
  dfs1(1, 0);
  dfs2(1, 0);
  for (int i = 1; i <= n; i++) lst[i] = 1;
  cin >> q;
  for (int i = 2; i <= (q + 1); i++) {
    char c;
    int x;
    cin >> c;
    if (c == 'C') {
      cin >> x;
      if (!col[x]) {
        col[x] = 1;
        update(lst[x], i, x, 1, 1, q + 2);
      } else
        col[x] = 0, lst[x] = i;
    } else
      haveq[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    if (!col[i]) update(lst[i], q + 2, i, 1, 1, q + 2);
  }
  solve(1, 1, q + 2);
  for (int i = 1; i <= (q + 2); i++) {
    if (haveq[i]) cout << ans[i] << '\n';
  }
  return 0;
}

Exercises

CF601E A Museum Robbery Segment-tree divide and conquer + knapsack DP．
CF19E Fairy Segment-tree divide and conquer + disjoint-set union with parity．
luogu P5227 [AHOI2013] Connected Graph Segment-tree divide and conquer + disjoint-set union．
luogu P4319 Changing Roads Segment-tree divide and conquer + Link Cut Tree for maintaining a minimum spanning tree．
luogu P3733 [HAOI2017] Eight Verticals and Eight Horizontals Segment-tree divide and conquer + linear basis．

Some content on this page is adapted from the blog post Deleting from a data structure, licensed under CC-BY-SA 4.0．

Segment Tree and Offline Queries

Process

Examples

Exercises