Chapter 9: Offline Techniques

Overview

Sometimes the key insight is not answering queries in order. Offline techniques let you batch, sort, and reorder queries to exploit structure that's invisible when processing them one at a time. Sweep line turns 2D problems into 1D event processing; Mo's algorithm answers range queries by cleverly reordering them; CDQ and parallel binary search batch independent searches over a shared timeline. These techniques are the difference between "I know this needs a segment tree" and "I can actually solve it."

Sqrt decomposition is grouped here as well, even though it is not strictly an offline technique -- it supports online point updates and range queries. It belongs in this chapter as a block-based $O(\sqrt{n})$ fallback and, more importantly, as the prerequisite for Mo's algorithm. Treat it as the bridge between "I have $n\le 2\times {10}^5$ and a tight time limit" and "I can use the block-decomposition idea to sort queries cleverly."

When can you go offline? The technique is available only when the problem statement does not require online output or query-dependent input. Watch for these recognition rules:

• All queries given upfront with no inter-query dependency -- you can sort, batch, sweep.
• Forced online -- the next query is XORed with the previous answer, or each query updates a state the next query reads. CDQ, Mo's, and PBS all break here; reach for persistent structures.
• Static array, no updates between queries -- enables Mo's and sort-by-R sweeps.
• Updates and queries interleaved but offline -- CDQ on time, or Mo with updates.

Navigation

Coming from: Chapter 8 — Geometry — computational geometry primitives and convex hull algorithms
Going to: Chapter 10 — Patterns and Recipes — meta-patterns for recognizing which technique to apply

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	Offline Queries	Beginner	"Process queries in a different order than given"
02	Sqrt Decomposition	Intermediate	"Block-based O(√n) queries" — universal fallback
03	Mo's Algorithm	Advanced	"Distinct values in [l, r]" or "frequency queries on static array"
04	CDQ Divide and Conquer	Advanced	"3D partial order" or "multi-dimensional point queries"
05	Parallel Binary Search	Advanced	"Binary search on answer for each query simultaneously"
06	Sweep Line	Intermediate	"Union of intervals," "overlapping rectangles," "sorted events"
07	Offline D&C for DP	Advanced	"Monotone minima" in DP transitions → O(n log n) per layer

If You Only Read 3 Files

1. Sweep Line — because event-based processing of sorted geometric/interval events is one of the most broadly applicable techniques. It turns "count overlapping intervals" and "closest pair" into clean O(n log n) solutions.
2. Mo's Algorithm — because it's the go-to technique when you have range queries on a static array and no update structure works. "Count distinct elements in [l, r]" is the canonical example, but it applies to many query types.
3. Sqrt Decomposition — because it's the universal fallback when nothing else works. O(√n) per query isn't glamorous, but it handles problems that are too hard for segment trees and too large for brute force.

Cross-Chapter Connections

• Sweep Line often needs Segment Tree or Segment Tree with Lazy from Chapter 2 as the sweep data structure
• Sweep Line problems usually require Coordinate Compression from Chapter 1
• Mo's Algorithm generalizes the Two Pointers technique from Chapter 1
• CDQ Divide and Conquer can replace Persistent Segment Tree for some problems
• Parallel Binary Search extends Binary Search from Chapter 1 to handle multiple queries

---

File Listing

File	Topic	Level
offline-queries	Offline Queries	⭐
sweep-line	Sweep Line	⭐⭐
sqrt-decomposition	Sqrt Decomposition	⭐⭐
mo-algorithm	Mo's Algorithm	⭐⭐⭐
cdq-divide-and-conquer	CDQ Divide and Conquer	⭐⭐⭐
parallel-binary-search	Parallel Binary Search	⭐⭐⭐
offline-dc-optimization	Offline D&C for DP Optimization	⭐⭐⭐

Suggested Reading Order

1. offline-queries — reorder queries for efficient batch processing
2. sweep-line — process sorted events for interval and geometric problems
3. sqrt-decomposition — block-based O(√n) queries and updates
4. mo-algorithm — answer range queries via intelligent query sorting
5. cdq-divide-and-conquer — solve multi-dimensional problems with recursion
6. parallel-binary-search — run multiple binary searches simultaneously
7. offline-dc-optimization — D&C technique for monotone-minima DP transitions