Skip to content

Square Root Decomposition

Split an array into \(\approx \sqrt{n}\) blocks of size \(\approx \sqrt{n}\). Precompute an aggregate per block (sum, min, frequency). Point updates touch one block in \(O(\sqrt{n})\); range queries combine whole blocks in \(O(\sqrt{n})\) plus edges in \(O(\sqrt{n})\).

When to use

  • Array operations where segment tree is overkill or memory is tight.
  • Problems with mixed query types that fit block summaries.
  • Building intuition before Mo’s algorithm (different use of blocks).

Example: range sum with point updates

  • Block b stores blockSum[b].
  • Update index i: adjust a[i] and blockSum[i / B].
  • Query [l,r]: sum partial blocks at ends in \(O(B)\), sum complete blocks in \(O(\#\text{blocks})\).

Choose block size \(B \approx \sqrt{n}\) to balance.