PrevNext
Has Not Appeared
 0/5

Offline Deletion

Authors: Benjamin Qi, Siyong Huang

Erasing from non-amortized insert-only data structures.

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-Algorithmsincludes code (but no explanation) for dynamic connectivity

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 NameDifficultyTagsSolution
YSNormal
Show Tags

DSUrb

View Solution

DSU With Rollback

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

StatusSourceProblem NameDifficultyTagsSolution
YSEasy
Show Tags

DSUrb

View Solution

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.
explanation? check Guide to CP?

Warning: Watch Out!

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

Implementation

C++

1int p[MN], r[MN];
2int *t[MN*40], v[MN*40], X;
3int setv(int *a, int b)
4{
5 if(*a != b) t[X] = a, v[X] = *a, *a = b, ++X;
6 return b;
7}
8void rollback(int x) {for(;X>x;) --X, *t[X] = v[X];}
9int find(int n) {return p[n] ? find(p[n]) : n;}
10bool merge(int a, int b)

Problems

StatusSourceProblem NameDifficultyTagsSolution
CFNormal
Show Tags

DSUrb

Check CF
CFHard
Show Tags

Dynacon

Check CF
CFVery Hard
Show Tags

D&C, DSUrb

Check CF

Module Progress:

Give Us Feedback on Offline Deletion!

PrevNext