Offline Binary Search
Offline Binary Search Offline binary search answers many queries after all updates and queries are already known. It is closely related to parallel binary search. The main idea is to avoid solving each query separately by grouping many midpoint checks into shared passes over the data. This method applies when each query asks for the earliest or smallest point at which a monotone condition becomes true. Problem Given: a sequence...