Section Recap

You now understand sqrt decomposition:

$1.$ Block decomposition splits an array into $\sqrt{n}$ blocks for $O(\sqrt{n})$ queries

$2.$ Point updates are $O(1)$ for sum, $O(\sqrt{n})$ for min/max

$3.$ MO's algorithm reorders offline queries to minimize boundary movement

$4.$ The add/remove pattern handles queries that segment trees can't

$5.$ Lazy block updates extend the technique to range modifications Sqrt decomposition isn't the fastest tool, but it's often the simplest correct solution. In contests, that matters. Next, you'll learn advanced tree structures that combine ideas from everything you've seen so far.