Concepts18
Problem Classification Patterns
Many competitive programming problems map to a small set of classic patterns; recognizing keywords and constraints lets you pick the right tool fast.
Sweepline Technique
The sweep line technique processes geometric or time-based events in sorted order and maintains an active set that reflects the current state at the sweep position.
Invariant Maintenance
An invariant is a property you promise to keep true throughout an algorithm, and it is the anchor of both design and correctness proofs.
Segment Tree with Range Affine Transformation
A segment tree with lazy propagation can support range updates of the form x → a·x + b (affine transformations) and range-sum queries in O(log n) per operation.
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
Rectangle Union Area
The union area of many axis-aligned rectangles can be computed efficiently using a sweep line over x and a segment tree tracking covered y-length.
Line Sweep
Line sweep (plane sweep) is a technique that processes geometric objects by moving an imaginary line and handling events in sorted order.
LIS Variants
LIS variants extend the classic longest increasing subsequence to handle non-decreasing sequences, counting how many LIS exist, and maximizing the sum of a subsequence.
Coordinate Compression
Coordinate compression replaces large, sparse, or arbitrary values with small consecutive integers while preserving relative order.
Kinetic Tournament Tree
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
Euler Tour Tree
An Euler Tour Tree represents each rooted tree as a DFS open/close sequence so that every subtree is a single contiguous interval.
HLD - Path Queries and Updates
Heavy-Light Decomposition (HLD) breaks a tree into a small number of vertical chains so any path (u,v) becomes O(log n) contiguous segments in an array.