Offline Deletions in $O(T(n)\log n)$

Suppose you have a structure that supports insert in true $O(T(n))$ (not amortized). You want delete as well, but only offline.

Trick: build a segment tree over time, place each element on the $O(\log n)$ nodes covering its lifetime, DFS the tree while inserting on enter and rolling back on leave.

Total: each insert/delete pair costs $O(T(n)\log n)$.

This lesson follows CP-Algorithms — Deleting from a data structure in $O(T(n)\log n)$.

The idea

1. Every element is alive on one or more time intervals [L, R).
2. Segment-tree the timeline of queries. Cover each lifetime with $O(\log T)$ nodes; store the element on those nodes.
3. Put “ask something” operations in the corresponding leaves.
4. DFS the segment tree:
   • Enter node → insert all elements stored there (push undo records).
   • Leaf → answer the query from the current structure.
   • Recurse to children.
   • Leave node → rollback exactly the inserts from this node.

If insert changes the structure in $O(T(n))$ and is reversible, rollback is also $O(T(n))$ via a change stack.

Amortized inserts break

Path compression, splay, etc. are amortized. After rollback you cannot rely on the amortized bound. Prefer union by rank without path compression for DSU-with-rollback.

Classic use: dynamic connectivity

Operations: add edge, remove edge, query number of connected components (or “are $u,v$ connected?”).

• DSU with union by rank + rollback stack (no path compression, or store full parent snapshots).
• Each edge’s lifetime [add_time, remove_time) goes onto the time segment tree.
• At each leaf that asks “how many components?”, read dsu.comps.

Interactive walkthrough

3 vertices. Edge A = $(0,1)$ alive on $[0,3)$; edge B = $(1,2)$ alive only at $t=1$. Step the DFS: add → query → rollback.

DSU with rollbacks

struct dsu_save {
    int v, rnkv, u, rnku;
};

struct dsu_with_rollbacks {
    vector<int> p, rnk;
    int comps;
    stack<dsu_save> op;

    dsu_with_rollbacks(int n) {
        p.resize(n);
        rnk.assign(n, 0);
        iota(p.begin(), p.end(), 0);
        comps = n;
    }

    int find_set(int v) {
        return v == p[v] ? v : find_set(p[v]); // no compression
    }

    bool unite(int v, int u) {
        v = find_set(v);
        u = find_set(u);
        if (v == u) return false;
        comps--;
        if (rnk[v] > rnk[u]) swap(v, u);
        op.push({v, rnk[v], u, rnk[u]});
        p[v] = u;
        if (rnk[u] == rnk[v]) rnk[u]++;
        return true;
    }

    void rollback() {
        auto x = op.top();
        op.pop();
        comps++;
        p[x.v] = x.v;
        rnk[x.v] = x.rnkv;
        rnk[x.u] = x.rnku;
    }
};

Time segment tree (query tree)

struct query {
    int v, u;
    bool united = false;
};

struct QueryTree {
    vector<vector<query>> t;
    dsu_with_rollbacks dsu;
    int T;

    QueryTree(int _T, int n) : T(_T), dsu(n) {
        t.resize(4 * T + 4);
    }

    void add_to_tree(int v, int l, int r, int ul, int ur, query q) {
        if (ul > ur) return;
        if (l == ul && r == ur) {
            t[v].push_back(q);
            return;
        }
        int mid = (l + r) / 2;
        add_to_tree(2 * v, l, mid, ul, min(ur, mid), q);
        add_to_tree(2 * v + 1, mid + 1, r, max(ul, mid + 1), ur, q);
    }

    void add_edge_lifetime(query q, int l, int r) {
        add_to_tree(1, 0, T - 1, l, r, q); // alive on [l, r]
    }

    void dfs(int v, int l, int r, vector<int>& ans) {
        for (query& q : t[v])
            q.united = dsu.unite(q.v, q.u);
        if (l == r)
            ans[l] = dsu.comps;
        else {
            int mid = (l + r) / 2;
            dfs(2 * v, l, mid, ans);
            dfs(2 * v + 1, mid + 1, r, ans);
        }
        for (query& q : t[v])
            if (q.united) dsu.rollback();
    }

    vector<int> solve() {
        vector<int> ans(T);
        dfs(1, 0, T - 1, ans);
        return ans;
    }
};

Complexity: O((n + q) · T_dsu · log q) with T_dsu = O(log n).

🧪 DSU rollback + tiny offline connectivity

Check: technique

Quiz

Offline deletions

1 / 4

This technique makes deletions…

Pick an answer to see if you are right.

Beyond DSU

Same skeleton works whenever you can insert + undo:

Structure	Offline deletes for…
DSU + rollback	Dynamic connectivity, bipartiteness
Convex hull / Li Chao (with undo)	Lines present on intervals
Segment tree / fenwick snapshots	Rare; usually rebuild
Linear basis with undo	XOR span over time

The “alive interval → $O(\log)$ nodes” idea also appears outside DS problems (divide-and-conquer on time).

Check: complexity & uses

Quiz

Applications

1 / 4

Dynamic connectivity offline is typically…

Pick an answer to see if you are right.

Practice drills

Activity: Cover interval

Timeline length T (times 0..T-1). Cover half-open [L, R) with $O(\log T)$ nodes of a segment tree on [0, T).

Print the number of nodes, then each node as l r (inclusive ranges in this drill), sorted by l then r.

Canonical cover: recurse; if the query fully covers a node, take it.

Contest problems

Connect and Disconnect

Judge: Codeforces Gym 100551A

Add/delete edges offline; answer connectivity queries. The article’s reference problem for dynamic connectivity.

Why this lesson?

Textbook time segment tree + DSU with rollbacks.

Cheat sheet

Step	Action
Lifetimes	Map each add/delete to [L,R)
Segment tree	Store element on $O(\\log T)$ nodes
DFS enter	Insert + push undo
Leaf	Answer query
DFS leave	Rollback
DSU	Rank + stack; no path compression

Previous: Convex Hull Trick · Centroid Decomposition

Source: CP-Algorithms — Deleting from a data structure in $O(T(n)\\log n)$