🐬 Techniques

A technique is a specific, reusable trick that recognizes a problem shape and cuts its cost — narrower than a full paradigm (greedy, DP, divide and conquer), not a single named algorithm that solves one well-defined problem outright (Dijkstra, KMP), and not a data structure on its own (though several techniques are built on top of one). Each row below is a map pointer, not a re-explanation — read the linked note for the real derivation, proof and tested code.

Array and sequence techniques

Technique	Recognizes	Note	Gain
Two pointers / sliding window	a contiguous-range condition that’s monotone as both ends advance	Two Pointers	$O(n^2)\to O(n)$
Prefix sums / difference arrays	many range-sum queries, or many range-add updates, all upfront	Prefix Sums	$O(nq)\to O(n+q)$
Monotonic stack	”nearest greater/smaller”, or a sum over all subarrays’ min/max	Monotonic Stack	$O(n^2)\to O(n)$
Binary search on the answer	the answer is a threshold with a monotone feasibility check	Binary Search	removes a search dimension, $\times \log (\text{range})$
Ternary / golden-section search	the objective is unimodal (convex-shaped), not monotone	Ternary Search	$O(\text{range})\to O(\log (\text{range}))$
Coordinate compression	values span a huge range but only $n$ of them matter	Sorting	lets array-indexed structures replace value-indexed ones

Search-space techniques

Technique	Recognizes	Note	Gain
Meet in the middle	brute force over $n\le 40$ items, split in half	Meet in the Middle	$O(2^n)\to O(2^{n/2})$
Sqrt decomposition	per-operation cost that trades off against block count	Sqrt Decomposition	$O(n)\to O(\sqrt{n})$ amortized
Randomized hashing of sets	compare multisets/subarrays for equality cheaply	Randomized Algorithms	$O(n)\to O(1)$ compare, w.h.p. correct

Offline and batching techniques

Technique	Recognizes	Note	Gain
Small-to-large merging	merge sets/maps at tree nodes, total work independent of depth	Small to Large	$O(n^2)\to O(n\log n)$
Sort-and-sweep (offline)	events with a natural order, no need to answer online	Offline Techniques	turns a DS problem into a sort
CDQ divide and conquer	an update/query pair ordered in one dimension, interacting in others	CDQ	removes one dimension per pass, $\times \log n$
Parallel binary search (a.k.a. fracturing search)	many queries, each its own binary search over a shared incremental structure	Parallel Binary Search	$O(q\log m\cdot \text{rebuild})\to O((m+q)\log m)$
Persistence	need to query an old version of a structure after further updates	Persistence	$O(1)$ extra per version instead of a full copy

Tree techniques

Technique	Recognizes	Note	Gain
Euler tour flattening	subtree queries, turn them into range queries	Euler Tour	lets any array range-query structure handle subtrees
Centroid decomposition	count/aggregate over all paths through each vertex	Centroid Decomposition	$O(n^2)\to O(n\log n)$
Virtual tree construction	DP restricted to $k$ marked vertices and their pairwise structure	Virtual Tree	$O(n)\to O(k\log n)$ per query
Rerooting	need the answer for every choice of root, not just one	Tree DP and Rerooting	$O(n^2)\to O(n)$ total
Kruskal reconstruction tree	”max edge weight on path” / “min threshold connecting $u,v$”, answered online	Kruskal Reconstruction Tree	turns the question into an LCA query

Bit techniques

Technique	Recognizes	Note	Gain
Submask enumeration / SOS DP	need $f(\text{every submask})$ from values at single bits	Submasks and SOS DP	$O(4^n)\to O(3^n)$ pairs, or $O(n{2}^n)$ for SOS
XOR basis	max/count of XOR-combinations of a vector set	XOR Basis	$O(2^n)\to O(n\log (\max ))$, linear algebra over ${\mathbb{F}}_2$

DP-layered techniques

These sit on top of the DP paradigm, exploiting extra structure (usually convexity) in the transition.

Technique	Recognizes	Note	Gain
Digit DP	count numbers in $[L,R]$ with a digit-local property	Digit DP	$O(R-L)\to O({\log }_{10}R)$
Divide and conquer optimization	$d{p}_i={\min }_j(\text{cost}(j,i))$ with the optimal $j$ monotone in $i$	D&C Optimization	$O(n^2)\to O(n\log n)$
Knuth’s optimization	interval DP with a quadrangle-inequality cost	Knuth’s Optimization	$O(n^3)\to O(n^2)$
Monotone queue optimization	$d{p}_i={\min }_{i-k\le j<i}d{p}_j+c_i$, a sliding window of candidates	Monotone Optimizations	$O(nk)\to O(n)$
Convex hull trick / Li Chao	$d{p}_i={\min }_j(a_j{x}_i+b_j)$, lines added and queried online	CHT, Li Chao Tree	$O(n^2)\to O(n\log n)$ or $O(n)$
Slope trick	the DP value, as a function of one parameter, stays convex piecewise-linear	Slope Trick	keeps the whole function in $O(\log n)$-per-op heaps instead of recomputing it
Aliens trick / WQS binary search	”exactly $k$ items” on an answer that’s convex in $k$	Aliens Trick	removes the $k$ dimension via a penalty + binary search

Proof and design techniques

Not data manipulation tricks — ways of finding and proving a solution, reusable across paradigms.

Technique	Recognizes	Note
Contribution technique	a sum over all pairs/subarrays/subsets, reframed as a sum over elements	Contribution
Exchange argument	proving a greedy order is optimal by showing any swap doesn’t help	Greedy and Exchange Arguments