Data Structures19 sections · 729 units
Open in CourseQuiz: 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?
- A.Because we visit each element exactly once
- B.Because r moves O(n) per l-block, and l moves O(√n) per query
- C.Because the queries are already sorted by r
- D.Because we use binary search to find ranges