Data Structures19 sections · 729 units
Open in Course

Quiz: MO's Complexity

Understanding the analysis

Check Your Understanding

In MO's algorithm, why does sorting by (l-block, r) give O((n+q)√n) total movement?

  1. A.Because we visit each element exactly once
  2. B.Because r moves O(n) per l-block, and l moves O(√n) per query
  3. C.Because the queries are already sorted by r
  4. D.Because we use binary search to find ranges
Start the roadmap to answer the quizzes and solve the challenges