This chapter introduces the ideas, common algorithms, and optimizations associated with offline algorithms.
An offline algorithm is designed under the assumption that all data is known before solving begins, and is suitable for problems with multiple queries. Its counterpart is the online algorithm.
For example, selection sort must know the global minimum element of the array before it can run, so it is an offline algorithm. Insertion sort, on the other hand, can receive data dynamically and sort it without requiring all data to be known beforehand, so it is an online algorithm.
For the same problem, offline algorithms are often easier to design than online algorithms. To prevent contestants from using an offline algorithm, a problem may sometimes enforce online processing: a common method is to make the parameters of the next query depend on the answer to the previous query. (Interactive problems and communication problems also belong to this category.)
Common approaches for offline algorithms include solving all queries together (such as CDQ divide and conquer) and using the answer to one query to obtain the answers to similar queries (such as parallel binary search and Mo's algorithm).
Because an offline algorithm is an idea rather than a specific algorithm, it can be combined with many different data structures and algorithms, so the corresponding problem types are also diverse.