EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
Data Structures & Algorithms

Advanced Tricks

These topics are the part of competitive programming that is hardest to compress into one sentence but easiest to recognize after enough practice.

7 published notes
5 planned topics
3 advanced or expert notes
intermediate starting level
Back to DSA Competitive Programming
Category Overview

Advanced Tricks

Offline reordering, amortized arguments, and techniques that show up when standard tools are almost enough.

Raw TeX

Overview

This category is for techniques that are not a single data structure or a single graph routine, but still recur often enough that they deserve a stable write-up.

Examples

Mo's algorithm, offline reordering, sqrt decomposition, amortized arguments, and parametric search all live here for the same reason: once the pattern is visible, many problems stop feeling ad hoc.

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 0 intermediate: 4 advanced: 3 expert: 0
4 intermediate
intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Binary Search on Answer, Mo's Algorithm, Offline Queries, Sqrt Decomposition

3 advanced
advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

Parallel Binary Search, Small-to-Large Merging, Bitset Optimization

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

01
intermediate

Binary Search on Answer

Turn optimization into repeated feasibility checks by designing a monotone predicate over the answer space.

optimization monotone predicate / modeling
02
advanced

Parallel Binary Search

Answer many monotone offline queries at once by testing them in batches at shared midpoints.

offline batching / monotonicity
03
intermediate

Mo's Algorithm

Offline range-query ordering that trades sorting plus add/remove operations for fast answers on static arrays.

offline queries sqrt decomposition / frequency counting
04
intermediate

Offline Queries

Reorder queries so that one sweep or one monotone data-structure state can answer them more cheaply than online processing.

offline processing sorting / Fenwick tree
05
advanced

Small-to-Large Merging

Amortize repeated subtree merges by always moving the smaller container into the larger one.

amortized analysis trees / multisets
06
intermediate

Sqrt Decomposition

Split the array into blocks so point updates and range queries become simple block-level work instead of full rescans.

block decomposition range queries / tradeoffs
07
advanced

Bitset Optimization

Use machine-word parallelism to update or compare dozens of boolean states with one operation.

bitset word parallelism / optimization
Study Order

Recommended order to read this branch

The default order follows each note's dependency weight: early notes establish primitives, later notes reuse them or assume the same invariants without re-explaining them.

01
intermediate

Binary Search on Answer

Turn optimization into repeated feasibility checks by designing a monotone predicate over the answer space.

optimization monotone predicate / modeling
02
advanced

Parallel Binary Search

Answer many monotone offline queries at once by testing them in batches at shared midpoints.

offline batching / monotonicity
03
intermediate

Mo's Algorithm

Offline range-query ordering that trades sorting plus add/remove operations for fast answers on static arrays.

offline queries sqrt decomposition / frequency counting
04
intermediate

Offline Queries

Reorder queries so that one sweep or one monotone data-structure state can answer them more cheaply than online processing.

offline processing sorting / Fenwick tree
05
advanced

Small-to-Large Merging

Amortize repeated subtree merges by always moving the smaller container into the larger one.

amortized analysis trees / multisets
06
intermediate

Sqrt Decomposition

Split the array into blocks so point updates and range queries become simple block-level work instead of full rescans.

block decomposition range queries / tradeoffs
07
advanced

Bitset Optimization

Use machine-word parallelism to update or compare dozens of boolean states with one operation.

bitset word parallelism / optimization
Planned topics

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Divide and conquer on answer planned Randomization planned Amortized analysis planned Potential method planned Parametric search planned
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
Category TeX sourcecompetitive_programming/dsa/advanced-tricks/index.tex