Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 63 ยท Data Structures in Contest Practice

Offline Queries, DSU Rollback and Persistence

Answer queries out of order, undo union-find merges for dynamic connectivity, keep old versions with a persistent segment tree, and use a Cartesian tree. Python, tested.

Most data structures in this track answer a query the moment it arrives. A powerful family of tricks does something sneakier: it reads all queries first, reorders them, and only then answers. If you are allowed to read the whole input before printing (which is true for almost every contest problem that does not say "online"), you can often replace a complicated structure with sorting and a DSU.

This lesson shows four tools that share the "think about time differently" flavor: offline processing in sorted order, a rollback DSU that can undo merges, a persistent segment tree that remembers every old version, and a Cartesian tree that turns "maximum of a range" into tree structure.

Offline: sort the questions, not just the data

Suppose each query is "are u and v connected using only edges of weight at most w?" If you answer queries in the order given, every query needs a fresh graph. But if you sort the queries by w and the edges by weight, and sweep with one pointer, the graph only ever grows. You add edges while their weight is at most the current limit, then ask the DSU. Merging is easy; the DSU never needs to forget anything.

The pattern is general. Sort by the threshold, keep a structure that supports adding, and answer each query in sorted order, storing the answer at its original index:

Query Sort by Structure while sweeping
Connected using edges of weight at most w? w DSU
Count elements at most x in a[l..r] x Fenwick tree over positions
Number of distinct values in a[l..r] right end r Fenwick tree with "last occurrence" updates
Smallest k such that vertices are connected edge weight DSU (Kruskal-style)
Python Offline connectivity by edge-weight limit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results are stored by the original query index, so the output order is unchanged. The brute force rebuilds a DSU for every query. When you have 10^5 queries that is the difference between a second and an hour.

Rollback DSU: merges you can undo

Offline sorting works when the graph only grows. What if edges also disappear? A DSU cannot delete an edge. But it can undo the most recent merges, if you promise to undo in reverse order.

Path compression changes many parents at once, which makes undoing hard. So a rollback DSU uses union by size and no path compression. Each union changes exactly two numbers (a parent pointer and a size), so one history entry per union is enough. find is O(log n) because trees stay shallow. Undoing a union restores those two numbers.

That gives offline dynamic connectivity. Every edge exists during a time interval [start, end). Build a segment tree over time; place each edge in the O(log T) nodes that cover its interval. Then walk the tree depth first: entering a node, union all its edges; at a leaf (one moment in time) read the answer; leaving a node, roll back to the snapshot taken on entry. Each edge is applied O(log T) times, so the total cost is O((n + m) log T log n).

flowchart TD
    R["time 0..8: edges alive the whole time"] --> L["time 0..4: edges alive during these four moments"]
    R --> Rr["time 4..8"]
    L --> L1["0..2"]
    L --> L2["2..4"]
    L1 --> a["leaf t=0: read answer"]
    L1 --> b["leaf t=1: read answer"]

Entering a node applies its edges; leaving it undoes them. A leaf sees exactly the edges alive at that moment.

Python Dynamic connectivity with a segment tree over time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line has the edge (0, 1) alive on [0, 4) and (1, 2) on [2, 6). Components over time: two components for t = 0, 1, one for t = 2, 3, then two again at t = 4, 5 after the first edge leaves. The recursive walk has depth only about log2(T), so Python's recursion limit is no problem here.

Persistent segment tree: every old version stays available

A persistent structure never overwrites; an update creates a new version and leaves the old one intact. For a segment tree this is cheap, because an update changes only the nodes along one root-to-leaf path. Copy those O(log n) nodes, point them at the unchanged siblings, and you have a new root.

The classic use is k-th smallest in a range with no updates. Build version i as "the counts of the first i elements" (a counting tree over the compressed values). The elements of a[l..r) are the difference between version r and version l. To find the k-th smallest, descend both trees together: if the left child holds at least k more elements in version r than in version l, go left; otherwise subtract that count and go right.

Python K-th smallest in a range with a persistent tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The node count printed at the start shows the memory bound: about n * (log m + 1) nodes, not n * m. Persistence also supports "the array as it was after update number 17", which is the key to many online-looking problems that can be answered after reading the whole input.

Cartesian tree: a range maximum as a tree

A Cartesian tree of an array puts the maximum at the root, then recursively builds the left part as the left subtree and the right part as the right subtree. The index order stays the in-order traversal. It can be built in O(n) with a stack, exactly like the monotonic stack in Monotonic Stacks, Heaps and Deques.

Why care? Because the subtree of a node i is exactly the range in which a[i] is the maximum. So the number of subarrays where a[i] is the maximum is (size of left subtree + 1) * (size of right subtree + 1). The maximum of any range [l, r] is the LCA of l and r in this tree, which connects Cartesian trees to the LCA techniques you already know.

Python Cartesian tree and subarrays where each element is the maximum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sum check at the end is a nice sanity test: every one of the n(n+1)/2 subarrays has exactly one designated maximum, so the counts must add up to that number. Ties are broken towards the leftmost element, which is why the test with repeated values still matches.

Which tool when

  • Queries have a threshold and the structure only grows: sort offline.
  • Edges or items appear and disappear, and all lifetimes are known: rollback DSU with a segment tree over time.
  • You need the state at an earlier moment or the difference of two prefixes: persistent tree.
  • The question is about maxima of ranges and how far each element dominates: Cartesian tree or a monotonic stack.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can offline sorted-by-weight processing answer 'connected with edges of weight at most w' using a plain DSU?

    As the limit increases, edges are only added. Merging is exactly what a DSU does well.
  2. 2. Why does a rollback DSU avoid path compression?

    With union by size only, each union changes two values, so a single history entry is enough to undo it. Find stays O(log n).
  3. 3. How many new nodes does one update of a persistent segment tree create?

    Only the nodes on the root-to-leaf path change; every other subtree is shared with the previous version.
  4. 4. In a max-Cartesian tree, how many subarrays have a[i] as their maximum (all values distinct)?

    The left end can be any of the left-subtree positions or i itself, and the right end likewise, giving the product.

Summary

  • If you may read all queries first, sort them by a threshold and sweep with a growing structure.
  • A DSU with union by size and no path compression can roll back unions in reverse order.
  • Putting each edge's lifetime into a segment tree over time and walking it with rollbacks solves offline dynamic connectivity.
  • A persistent segment tree creates O(log n) nodes per update and keeps every version, which gives range k-th smallest as the difference of two prefix versions.
  • A Cartesian tree is built in O(n) with a stack, and its subtree sizes count the subarrays where each element is the maximum.

Next: Graph Problems: Modeling and Traversal