Segment Tree Divide and Conquer Overview
Segment tree divide and conquer is typically used to solve problems with two key characteristics: operations are only effective within specific time intervals, and queries require the ressult of all operations at a particular time point. We can build a segment tree over time, attach operations to corresponding nodes, and queries to leaf nodes. Traversing the segment tree from the root left to right, we execute operations at each node when entering, undo them when backtracking, and query at leaf nodes. Thus, segment tree merging always combines with data structures supporting addition and rollback.
Example Problems
Bipartite Graph / Template: Segment Tree Divide and Conquer
Problem Statement
A template problem for segment tree divide and conquer.
Solution
To determine if a graph is bipartite, we use a coloring method to check for adjacent nodes with the same color. However, in this problem, the graph is dynamic, so we cannot re-run the check each time. Instead, we use an extended union-find set (disjoint set union with rollback). Since we need to undo operations, we avoid path compression and use union by rank.
Core Code:
void solve(int node) {
int cnt = 0;
bool isBipartite = true;
for (auto& edge : edgesAtNode[node]) {
if (unionFind.find(edge.u) == unionFind.find(edge.v)) {
for (int i = leftBound(node); i <= rightBound(node); ++i) {
isBipartiteFlag[i] = false;
}
isBipartite = false;
break;
}
int u = edge.u, v = edge.v;
unionFind.merge(u + n, v, cnt);
unionFind.merge(u, v + n, cnt);
}
if (isBipartite && leftBound(node) != rightBound(node)) {
solve(node << 1);
solve(node << 1 | 1);
}
while (cnt--) {
auto top = undoStack.top();
undoStack.pop();
unionFind.parent[top.x] = top.x;
unionFind.rank[top.parent] -= top.rank;
}
}
[HAOI2017] Eight Directions
Problem Statement
Segment tree divide and conquer combined with linear basis.
Solution
XOR operations have useful properties, such as x XOR x = 0. Here, we need to find cycles with maximum XOR sum. By selecting a spanning tree initially, we only need to record cycles formed by new edges and the spanning tree. This conclusion, combined with segment tree divide and conquer, solves the problem.
Core Code:
// Union-find operations
int find(int x) {
while (x != parent[x]) x = parent[x];
return x;
}
bitset<maxBits> findXorDistance(int x) {
bitset<maxBits> res;
res.reset();
while (x != parent[x]) {
res ^= xorDistance[x];
x = parent[x];
}
res ^= xorDistance[x];
return res;
}
void merge(Node& current) {
int u = current.u, v = current.v;
bitset<maxBits> w = current.w;
int fu = find(u), fv = find(v);
if (fu == fv) {
linearBasis.insert(findXorDistance(u) ^ findXorDistance(v) ^ w);
return;
}
if (size[fu] > size[fv]) swap(fu, fv), swap(u, v);
undoStack.push({fu, fv, size[fv]});
xorDistance[fu] = findXorDistance(u) ^ findXorDistance(v) ^ w;
parent[fu] = fv;
size[fv] += size[fu];
}
[FJOI2015] Mars Shop Problem
Problem Statement
Segment tree divide and conquer combined with persistent 01 trie.
Solution
The problem statement is complex, but the implementation is straightforward.
Core Code:
// Persistent 01 trie
struct PersistentTrie {
int children[maxn * 20][2], count[maxn * 20], total = 0;
inline int buildNode() {
return ++total;
}
void insert(int current, int previous, int value) {
count[current] = count[previous] + 1;
for (int i = 19; i >= 0; --i) {
int bit = (value >> i) & 1;
children[current][bit ^ 1] = children[previous][bit ^ 1];
children[current][bit] = buildNode();
current = children[current][bit];
previous = children[previous][bit];
count[current] = count[previous] + 1;
}
}
int query(int current, int previous, int value) {
int res = 0;
for (int i = 19; i >= 0; --i) {
int bit = (value >> i) & 1;
if (count[children[previous][bit ^ 1]] > count[children[current][bit ^ 1]]) {
res += (1 << i);
bit ^= 1;
}
current = children[current][bit];
previous = children[previous][bit];
}
return res;
}
} trie;
Envy
Problem Statement
A problem involving properties of minimum spanning trees.
Solution
We use two properties of minimum spanning trees: 1) The number of edges with the same weight is fixed across all MSTs. 2) The connectivity after adding edges with weight ≤ a certain value is consistent. By separating edges by weight and checking for cycles, we solve the problem.
Code
Extending Set of Points
Problem Statement
If we view rows as left vertices and columns as right vertices in a bipartite graph, each grid point corresponds to an edge. A connected component contributes sx * sy to the answer, where sx and sy are the counts of left and right vertices. Segment tree divide and conquer applies directly.
Code
Forced Online Queries Problem
Problem Statement
A challenging problem with "forced online" constraints.
Solution
Despite the "forced online" label, this is a trick problem. Segment tree divide and conquer processes queries in time order, so when handling the i-th operation, the last answer is already known. Since the last answer is only 0/1, we insert both cases into the segment tree and choose the correct edge during union-find merging.
Code
「Yali Training 2018 Day10」Playful Blue Moon
Problem Statement
Segment tree divide and conquer combined with knapsack (trivial problem).
Core Code:
void calculate(int node) {
for (auto& item : itemsAtNode[node]) {
itemCount++;
for (int j = 0; j < mod; ++j) {
dp[itemCount][j] = dp[itemCount - 1][j];
}
for (int j = 0; j < mod; ++j) {
dp[itemCount][(item.first + j) % mod] = max(dp[itemCount][(item.first + j) % mod], dp[itemCount - 1][j] + item.second);
}
}
}
BZOJ4184-shallot
Problem Statement
A simplified version of "Eight Directions", using segment tree divide and conquer with linear basis.
[bzoj4644] Classic Problem
Problem Statement
Define a node's value as the XOR sum of its connected edges. Selecting both endpoints of an edge is equivalent to not selecting it, so we need to choose nodes to maximize the XOR sum. During segment tree divide and conquer, insert the node's value at its time interval.