Concepts10
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.
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.
Merge Sort Tree
A Merge Sort Tree is a segment tree where every node stores the sorted list of values in its segment.
Iterative Segment Tree
An iterative segment tree stores all leaves in tree[n..2n-1] and internal nodes in tree[1..n-1], enabling O(\log n) point updates and range queries without recursion.
Segment Tree with Lazy Propagation
A segment tree with lazy propagation supports fast range updates and range queries in O(\log n) time.
Segment Tree Basics
A segment tree is a complete binary tree that stores information about array intervals to answer range queries and support point updates in O(log n).