Method
offline queries
Articles
DS
Data structure
Disjoint set union
Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks.
O(α(n))
2 problems
TEC
Technique
Coordinate compression
Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks.
O(n log n) to compress
2 problems
Problems
Often together
array 2 disjoint sets 1 connectivity 1 tree 1 amortized 1 maps and navigation 1 images 1 science and physics 1 classic 1 range queries 1 sorting 1 binary search 1