Introduction to Time-Based Divide and Conquer
Segment Tree Divide and Conquer is an advanced offline algorithmic technique typicalyl used to solve problems involving dynamic modifications that persist over specific time intervals. The core idea is to map the time dimension onto a segment tree, allowing us to decompose the lifespan of operations into logarithmic segments.
This technique is particularly powerful when combined with data structures that support rollback (undo operations). Unlike standard segment trees that store aggregate values, here we store "events" or "modifications" in the nodes. We traverse the tree in a Depth First Search (DFS) manner. When entering a node, we apply all modifications stored there to our current data structure; when leaving the node, we roll back (undo) these modifications to restore the state for the parent node.
Algorithmic Complexity
Let the total number of operations be $n$, the time range be $m$, and the cost of modifying/rollling back the auxiliary data structure be $M(n)$ and $R(n)$ respectively. Each operation with an active interval $[L, R]$ is inserted into $O(\log m)$ nodes of the segment tree. Consequently, we perform a modification and a rollback $O(n \log m)$ times. The total time complexity is $O(n \log m (M(n) + R(n)))$. If we query answers at leaf nodes, we add $O(m Q(n))$, where $Q(n)$ is the query cost.
The Core Template: Rollback DSU
The most common companion data structure for this technique is the Disjoint Set Union (DSU) with Union by Size or Rank. Path compression cannot be used because it destroys the tree structure required for efficient rollback (undoing a path compression is complex). Instead, we use Union by Size and a stack to record history.
#include <bits/stdc++.h>
using namespace std;
// Structure to record history for rollback
struct DSUHistory {
int child, parent, size_child;
};
template<int MAXN>
struct RollbackDSU {
int parent[MAXN];
int component_size[MAXN];
stack<DSUHistory> history_stack;
void init(int n) {
for (int i = 1; i <= n; ++i) {
parent[i] = i;
component_size[i] = 1;
}
}
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
// Returns true if a merge happened, false if already connected
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
// Ensure 'a' is the smaller tree (Union by Size)
if (component_size[a] > component_size[b]) swap(a, b);
// Record state before modification
history_stack.push({a, a, component_size[a]});
// Merge 'a' into 'b'
parent[a] = b;
component_size[b] += component_size[a];
return true;
}
void undo() {
if (history_stack.empty()) return;
DSUHistory h = history_stack.top();
history_stack.pop();
// Restore state
parent[h.child] = h.parent;
component_size[h.parent] -= h.size_child;
// Note: If parent was b, and child was a merged into b
// we simply need to restore parent[a]=a and size[b]-=size[a]
// The logic above assumes we always attach root A to root B
// Correction based on union logic:
// actually we attached 'a' to 'b' (where 'a' was the smaller root).
// So parent[a] becomes a. size[b] restores.
}
// Snapshot mechanism for non-DSU structures or complex state
int get_snapshot() {
return history_stack.size();
}
void rollback_to_snapshot(int snapshot_id) {
while ((int)history_stack.size() > snapshot_id) {
undo();
}
}
};
Problem: Dynamic Bipartite Graph Checking
Scenario: Given edges that appear and disappear over time intervals, determine if the graph is bipartite at every discrete time point.
Solution: Use the "Extended Field" DSU technique (2-SAT style). For each node $u$, create $u$ and $u+N$. If we connect $u$ and $v$, we merge $u$ with $v+N$ and $v$ with $u+N$. If we find $u$ and $v$ in the same set during a merge, the graph is not bipartite.
Implementation Strategy: Build a segment tree over the time axis. Insert each edge $(u, v)$ with interval $[L, R]$ into the segment tree nodes. DFS the tree. At the leaves (time points), if the DSU is valid, output "Yes"; otherwise "No".
const int N = 1e5 + 5;
struct Edge { int u, v; };
struct SegNode {
vector<Edge> edges;
};
struct Solver {
RollbackDSU<N * 2> dsu; // 2x for bipartite extension
SegNode tree[N * 4];
int n, time_len;
void add_edge(int node, int l, int r, int ql, int qr, Edge e) {
if (ql <= l && r <= qr) {
tree[node].edges.push_back(e);
return;
}
int mid = (l + r) / 2;
if (ql <= mid) add_edge(node * 2, l, mid, ql, qr, e);
if (qr > mid) add_edge(node * 2 + 1, mid + 1, r, ql, qr, e);
}
void dfs(int node, int l, int r) {
int snapshot = dsu.get_snapshot();
bool is_valid = true;
for (auto& e : tree[node].edges) {
int root_u = dsu.find(e.u);
int root_v_ext = dsu.find(e.v + n);
if (root_u == root_v_ext) {
is_valid = false;
break;
}
dsu.unite(e.u, e.v + n);
dsu.unite(e.u + n, e.v);
}
if (!is_valid) {
// If invalid at this node, it remains invalid in subtree
// Optimization: Skip recursion if we just need boolean answer
} else {
if (l == r) {
cout << "Yes\n";
} else {
int mid = (l + r) / 2;
dfs(node * 2, l, mid);
dfs(node * 2 + 1, mid + 1, r);
}
}
dsu.rollback_to_snapshot(snapshot);
}
};
Problem: Minimum MEX Spanning Tree
Scenario: Find the minimum $k$ such that the graph formed by all edges with weight $\neq k$ is still connected (i.e., forms a spanning tree with available edges).
Solution: Iterate $k$ or binary search it. For a fixed $k$, we need to check connectivity using all edges except those with weight $k$. Equivalently, edges with weight $w$ are "active" for all time $t \neq w$. We can set up a segment tree over the range of weights. An edge with weight $w$ is added to all intervals $[1, w-1]$ and $[w+1, MAX]$. We traverse the tree, and at leaf $k$, we check if the DSU is fully connected.
// Inside DFS:
void dfs(int p, int l, int r) {
int snap = dsu.get_snapshot();
for (auto& e : tree[p].edges) {
dsu.unite(e.u, e.v);
}
if (l == r) {
if (dsu.component_size[dsu.find(1)] == n) {
// Connected at this weight point
// Record answer
}
} else {
int mid = (l + r) / 2;
dfs(p * 2, l, mid);
dfs(p * 2 + 1, mid + 1, r);
}
dsu.rollback_to_snapshot(snap);
}
Problem: Communication Towers (Tagged DSU)
Scenario: Nodes are active during specific intervals. We need to calculate the sum of sizes of connected components containing node 1 for each time unit.
Challenge: Naively marking every node in a component is too slow ($O(N^2)$). We need to maintain a "tag" on the root of the DSU component.
**Trick:**1. Maintain tag\[root\] representing how many times this component has been "counted" or "activated" due to specific events. 2. When merging $X$ into $Y$, if we just sum tags, we might double-count or carry wrong tags. 3. Standard solution: When attaching $X$ (root) to $Y$ (root), do tag\[X\] -= tag\[Y\]. 4. When rolling back (splitting $X$ from $Y$), do tag\[X\] += tag\[Y\]. 5. At a leaf (time $t$), if node $t$ (mapped to an index) is active, we increment the tag of its root. 6. Query result is simply tag\[root\_of\_1\].
struct TaggedDSU : public RollbackDSU<MAXN> {
int tag[MAXN];
void init(int n) {
RollbackDSU<MAXN>::init(n);
fill(tag, tag + n + 1, 0);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (component_size[a] > component_size[b]) swap(a, b);
history_stack.push({a, a, component_size[a]}); // Basic DSU history
// Additional history for tag logic might be needed depending on implementation details
// Here we assume tag logic is implicit in the relationship
// Key logic: Before linking, adjust tag to avoid carry-over
tag[a] -= tag[b];
parent[a] = b;
component_size[b] += component_size[a];
}
void rollback() {
// ... standard DSU rollback ...
// When separating 'a' from 'b':
// tag[a] += tag[b]; // Restore the difference
}
};
Problem: A Museum Robbery (Dynamic Knapsack)
Scenario: Items appear and disappear. At specific times, we need to answer the standard 0/1 Knapsack query: maximum value for capacity $W$.
Solution: Since Knapsack DP ($dp[i] = \max(dp[i], dp[i-w] + v)$) is not easily invertible, we cannot just "undo" an operation efficiently in $O(1)$. Instead, we use the Snapshot method.
When entering a segment tree node, take a full copy of the DP array (or a hash of changes). Apply items in this node to the DP. Recurse. After recursion, restore the DP array from the snapshot.
struct KnapsackSolver {
int dp[1005]; // DP array
int max_capacity;
// Map time to items in segment tree...
void dfs(int node, int l, int r) {
// 1. Snapshot
vector<int> backup(dp, dp + max_capacity + 1);
// 2. Apply items at this node
for (auto& item : tree[node].items) {
for (int j = max_capacity; j >= item.weight; --j) {
dp[j] = max(dp[j], dp[j - item.weight] + item.value);
}
}
if (l == r) {
// Answer query at time l
long long ans = 0;
for(int j=0; j<=max_capacity; ++j) ans = max(ans, (long long)dp[j]);
// Compute polynomial hash or whatever the problem asks
} else {
int mid = (l + r) / 2;
dfs(node * 2, l, mid);
dfs(node * 2 + 1, mid + 1, r);
}
// 3. Restore from Snapshot
dp.assign(backup.begin(), backup.end());
// Or memcpy for speed
memcpy(dp, backup.data(), sizeof(int) * (max_capacity + 1));
}
};
Problem: Painting Edges (Multi-Color Bipartite Check)
Scenario: We have a graph with edges. Queries change the color of an edge. The constraint is: For each color $c$, the subgraph containing only edges of color $c$ must be bipartite. Determine if each query operation is valid (can be applied).
Complexity: $K$ colors (up to 50). We cannot run 50 separate segment trees due to memory/time. Instead, we run one segment tree, but maintain $K$ separate DSUs.
Offline Logic: An edge of color $c$ is active from its assignment time $t$ until the next query affecting this edge. We need to pre-calculate these intervals.
**Algorithm:**1. Proces queries offline. Use an array next\_query\[edge\_index\] to find when the current color assignment ends. 2. Traverse the segment tree. At each node, for each edge $(u, v, col)$ stored there, attempt to unite $u, v$ in DSUs\[col\]. 3. If any DSUs\[col\] detects a conflict (odd cycle), the entire time range of this node is invalid for these operations. 4. If we are at a leaf (answering a query), and it's valid, we update the edge's color and calculate its next active interval.
struct MultiColorSolver {
RollbackDSU<MAXN * 2> dsu[51]; // 50 colors
int current_color[MAXN]; // Tracks color of edge i
void dfs(int p, int l, int r) {
int snapshot[51];
for(int i=1; i<=50; ++i) snapshot[i] = dsu[i].get_snapshot();
bool ok = true;
for (auto& op : tree[p].ops) {
int u = op.u, v = op.v, c = op.c;
// Check bipartite condition: u and v+N cannot be connected
if (dsu[c].find(u) == dsu[c].find(v + n)) {
ok = false; break;
}
dsu[c].unite(u, v + n);
dsu[c].unite(u + n, v);
}
if (ok) {
if (l == r) {
// Query is successful
int edge_idx = query_at_time[l].edge_id;
int new_color = query_at_time[l].target_color;
cout << "YES\n";
// Determine interval for this new state
// It lasts from l+1 until the next query involving edge_idx
int next_time = next_occurrence[edge_idx];
if (l + 1 <= next_time - 1) {
add_edge(1, 1, total_time, l+1, next_time-1, {edges[edge_idx].u, edges[edge_idx].v, new_color});
}
current_color[edge_idx] = new_color;
} else {
int mid = (l+r)/2;
dfs(p*2, l, mid);
dfs(p*2+1, mid+1, r);
}
} else {
// If invalid, all queries in [l, r] fail
// However, in this problem, if a query fails, the state doesn't change.
// So we don't need to do anything special for future intervals in this branch.
if (l == r) cout << "NO\n";
else {
// Optimization: We can skip recursion if we know all answers are NO
// But careful: The input implies we might need to output NO for each time point.
for (int i = l; i <= r; ++i) cout << "NO\n";
}
}
// Rollback all DSUs
for(int i=1; i<=50; ++i) {
dsu[i].rollback_to_snapshot(snapshot[i]);
}
}
};