Skip to content
CCC Python Course

Sqrt decomposition

Stage
7
Module
M7.9
Lessons
1

In this module

  • Partition a large problem into heavy and light groups.
  • Process heavy items as special cases and light items with standard algorithms.
  • Use square-root blocking to balance preprocessing and query time.
  • Recognize when Python performance limits apply and accept partial-mark subtasks.

Before this module

M6.10Fenwick tree (Binary Indexed Tree)M2.9Complexity analysis and deriving the target from N

Lessons

  1. 1Sqrt decomposition

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2017 S5
    RMT (opens on DMOJ in a new tab) DMOJ

    Many queries over a transit network's routes.

    Why DMOJ: An older problem with a large number of queries, good for practicing where a partial, unoptimized attempt still scores.