Sqrt Decomposition

Imagine you have a list of a million numbers and you need to answer two kinds of requests that keep arriving in any order: range-sum queries ("what is the sum of elements from index $l$ to $r$?") and point updates ("change element $i$ to value $v$"). How fast can you do both?

The naive approach is immediate: keep the raw array. An update costs $O(1)$ — just write to one slot. But a query costs $O(n)$ — you have to add up every element in the range. The opposite approach, a prefix-sum table, flips the trade: queries drop to $O(1)$, but now every update forces you to recompute the whole table in $O(n)$.

Neither extreme is satisfying when queries and updates arrive equally often. The beautiful insight of sqrt decomposition (also called block decomposition) is that you can split the difference exactly. Partition the array into blocks of size $B \approx \sqrt{n}$ and store the sum of each block alongside the raw elements. Queries walk at most two partial blocks ($O(B)$) plus at most $n/B$ whole blocks — totaling $O(B + n/B)$. Updates touch one element and rebuild one block sum in $O(1)$. Setting $B = \sqrt{n}$ minimizes $B + n/B$ to exactly $2\sqrt{n}$: both operations cost $O(\sqrt{n})$.

That perfect balance is not a coincidence. It is a minimax argument: you choose $B$ to make the two cost terms equal, and the crossing point is always $\sqrt{n}$.

The array below has 16 elements split into blocks of size 4 (since $\lfloor\sqrt{16}\rfloor = 4$). Each colored bar represents one block; the number inside the bar is the block's running sum.

<p class="hint">{{hint}}</p>
<div id="blocks-row" class="blocks-row"></div>
<div id="array-row" class="array-row"></div>
<div class="controls">
  <div class="ctrl-group">
    <label>{{lbl_update_index}} <span class="range-hint">{{range_hint}}</span></label>
    <div class="ctrl-row">
      <input id="upd-idx" type="number" min="0" max="15" value="5" />
      <input id="upd-val" type="number" min="0" max="99" value="42" />
      <button id="btn-update" type="button">{{btn_update}}</button>
    </div>
  </div>
  <div class="ctrl-group">
    <label>{{lbl_query_range}} <span class="range-hint">{{range_hint}}</span></label>
    <div class="ctrl-row">
      <input id="qry-l" type="number" min="0" max="15" value="2" />
      <input id="qry-r" type="number" min="0" max="15" value="11" />
      <button id="btn-query" type="button">{{btn_query}}</button>
    </div>
  </div>
</div>
<div class="status" id="status">{{status_ready}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.blocks-row { display: flex; gap: 6px; margin-bottom: 4px; }
.block-sum {
  flex: 1; height: 36px; border-radius: 8px 8px 0 0;
  display: flex; align-items: center; justify-content: center;
  font: 700 13px ui-monospace, monospace; color: #fff;
  transition: background .2s;
}
.array-row { display: flex; gap: 2px; margin-bottom: .8rem; }
.cell {
  flex: 1; height: 46px; border-radius: 0 0 6px 6px;
  display: flex; align-items: center; justify-content: center;
  font: 600 13px ui-monospace, monospace; border: 1.5px solid #cdd9e3;
  background: #e8eef3; color: #1d3557;
  transition: background .15s, color .15s;
}
.cell.highlight-partial { background: #fce07c; border-color: #d4a900; color: #5a3e00; }
.cell.highlight-full    { background: #6ec87a; border-color: #3a8f48; color: #fff; }
.cell.updated           { background: #e63946; border-color: #c92f3c; color: #fff; }
.block-sum.updated-blk  { background: #c92f3c !important; }
.controls { display: flex; flex-wrap: wrap; gap: .8rem; margin-bottom: .6rem; }
.ctrl-group { display: flex; flex-direction: column; gap: .3rem; }
.ctrl-group label { font-size: .82rem; font-weight: 600; color: #1d3557; }
.ctrl-group .range-hint { font-weight: 400; color: #666; }
.ctrl-row { display: flex; gap: .4rem; align-items: center; }
input[type=number] {
  width: 58px; padding: .35rem .4rem; border: 1px solid #adb1b8;
  border-radius: 6px; font: 600 14px ui-monospace, monospace; text-align: center;
}
button {
  font: 600 13px system-ui, sans-serif; padding: .4rem .8rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
  border-radius: 7px; cursor: pointer;
}
button:hover { background: #162840; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; color: #1d3557; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Click Update to change a single element — notice only that block's sum changes, everything else stays intact: $O(1)$ work. Click Query to sum a range — the highlighted cells show which elements are touched individually (partial blocks at the ends) and which blocks are swallowed whole. Count them: at most $2 \times 4 = 8$ individual cells plus at most 3 block sums, far less than 16 in the worst case.

This is the core trade-off behind Mo's algorithm and many competitive-programming tricks: structure your data into $\sqrt{n}$ groups and both directions stay symmetric.

Let $n$ be the array length and $B$ the block size. The two cost terms are:

• Query: walk at most $2B$ elements in partial end-blocks + at most $\lceil n/B \rceil$ block sums → $O(B + n/B)$.
• Update: write one element + recompute one block sum from $B$ elements → $O(B)$.

Minimizing $B + n/B$ over $B > 0$ gives $B^* = \sqrt{n}$ and total cost $2\sqrt{n}$, so:

A segment tree beats sqrt decomposition on paper ($\log n < \sqrt{n}$ for large $n$). Yet sqrt decomposition wins in practice for several reasons:

• Tiny constant: the inner loop is a tight array scan with no pointer chasing or branch mispredictions.
• Simplicity: the entire structure is a flat array plus a block-sum array — trivial to implement and debug.
• Offline flexibility: Mo's algorithm sorts queries by block and achieves $O(n\sqrt{n})$ for range problems that look quadratic at first glance.
• Non-standard operations: when the "merge" operation is expensive or hard to make lazy (e.g., range GCD, range median), keeping a flat block is often simpler than a lazy segment tree.

Sqrt decomposition is a proven, complete technique — not a heuristic or an open problem. It is the right tool whenever you need robust $O(\sqrt{n})$ guarantees with minimal implementation overhead.

The $\sqrt{n}$ block trick appears wherever two operations pull in opposite directions:

• Competitive programming: sqrt decomposition solves range-sum, range-min, range-GCD, range-mode, and dozens of other problems with a single unified approach. It is often the first data structure taught after prefix sums.
• Mo's algorithm: by sorting offline queries by their left endpoint's block index (and right endpoint within blocks), Mo's algorithm processes all $q$ queries in $O((n + q)\sqrt{n})$ time — turning what seems like an $O(n \cdot q)$ problem into something manageable.
• Square-root decomposition of time: the same idea applies to time instead of space. Process updates in batches of $\sqrt{n}$, answer queries against the current batch plus a precomputed baseline — a staple for offline dynamic connectivity and kinetic problems.
• Database buffer management: B-trees and external-memory data structures use block-aligned I/O for the same reason — touching one block is cheap, and blocks are sized to amortize overhead.
• String algorithms: suffix arrays, suffix automata, and heavy-path decompositions on trees all use block-level ideas to balance preprocessing against query time.

If you understand sqrt decomposition, you have internalized the central design question of algorithms: what is the optimal split point between two competing costs? The answer to that question is always found by calculus — set the derivatives equal — and for $B + n/B$ the answer is always $\sqrt{n}$.

Sqrt decomposition is a reminder that the cleverest ideas in algorithmics are often the most transparent. A single array, a handful of precomputed block sums, and one question — "what block size makes both operations equally fast?" — yield a technique that is easy to code, hard to break, and good enough for problems that would otherwise require a complex lazy segment tree.

The deeper lesson is a design principle: whenever two costs pull in opposite directions, set them equal. That minimax argument produces $\sqrt{n}$ here, $\log n$ in balanced trees, and $n^{2/3}$ in cache-oblivious algorithms. Each is the answer to the same optimization question, asked at a different scale.

Next time you face a problem with two competing costs, remember the square root — it might be all you need. And if you want to see how the same block idea plays out in a more exotic setting, explore Mo's algorithm or the dynamic shortest paths problem.