PrevNext
Has Not Appeared
 0/6

Offline Deletion

Authors: Benjamin Qi, Siyong Huang

Erasing from non-amortized insert-only data structures.

Edit This Page

Offline Deleting from a Data Structure

Using a persistent data structure or rollbacking, you are able to simulate deleting from a data structure while only using insertion operations.

Resources
CP-Algorithms
Deleting from a data structure in O(T(n) log n)

includes code (but no explanation) for dynamic connectivity

Dynamic Connectivity

Resources
GCP
15.5.4 - Dynamic Connectivity

Dynamic Connectivity is the most common problem using the deleting trick. The problem is to determine whether pairs of nodes are in the same connected component while edges are being inserted and removed.

StatusSourceProblem NameDifficultyTags
YS
Vertex Add Component Sum
Normal
Show TagsDSUrb

DSU With Rollback

DSU with rollback is a subproblem required to solve the above task.

StatusSourceProblem NameDifficultyTags
YS
Persistent Union Find
Easy
Show TagsDSUrb
DMOJ
Inaho
Easy
Show TagsDSUrb

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

explanation? check Guide to CP?

Warning: Watch Out!

Because path compression is amortized, it does not guarauntee O(Nlog⁡2N)\mathcal{O}(N \log^2 N) runtime. You must use merging by rank.

Implementation

C++

int p[MN], r[MN];
int *t[MN*40], v[MN*40], X;
int setv(int *a, int b)
{
	if(*a != b) t[X] = a, v[X] = *a, *a = b, ++X;
	return b;
}
void rollback(int x) {for(;X>x;) --X, *t[X] = v[X];}
int find(int n) {return p[n] ? find(p[n]) : n;}
bool merge(int a, int b)

Problems

StatusSourceProblem NameDifficultyTags
CF
Edu F - Extending Set of Points
Normal
Show TagsDSUrb
CF
Forced Online Queries Problem
Hard
Show TagsDynacon
Baltic OI
2020 - Joker
Very Hard
Show TagsD&C, DSUrb

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum
PrevNext