Introduction

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 ll to rr?") and point updates ("change element ii to value vv"). How fast can you do both?

The naive approach is immediate: keep the raw array. An update costs O(1)O(1) — just write to one slot. But a query costs O(n)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)O(1), but now every update forces you to recompute the whole table in O(n)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≈nB \approx \sqrt{n} and store the sum of each block alongside the raw elements. Queries walk at most two partial blocks (O(B)O(B)) plus at most n/Bn/B whole blocks — totaling O(B+n/B)O(B + n/B). Updates touch one element and rebuild one block sum in O(1)O(1). Setting B=nB = \sqrt{n} minimizes B+n/BB + n/B to exactly 2n2\sqrt{n}: both operations cost O(n)O(\sqrt{n}).

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

Try It

The array below has 16 elements split into blocks of size 4 (since ⌊16⌋=4\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">Array of 16 elements split into 4 blocks of size 4. <b>Update</b> changes one element (O(1) block rebuild). <b>Query</b> sums a range using whole blocks + partial ends (O(√n)).</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>Update index <span class="range-hint">(0–15)</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">Update</button>
    </div>
  </div>
  <div class="ctrl-group">
    <label>Query range <span class="range-hint">(0–15)</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">Query</button>
    </div>
  </div>
</div>
<div class="status" id="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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Sqrt Decomposition: range-sum with point updates.
// Array length N=16, block size B=4 (= sqrt(16)).
// Block sums allow O(B) = O(4) query + O(1) update.
const N = 16, B = 4;
const BLOCK_COLORS = ['#1d6fa4','#2a8a5e','#8a4f2a','#6b3a7d'];

// Initialize array with some values
const arr = [7,3,9,2, 5,1,8,4, 6,10,2,7, 3,5,1,9];
const blockSum = new Array(N/B).fill(0);

function rebuildBlockSum(b) {
  let s = 0;
  for (let i = b*B; i < (b+1)*B; i++) s += arr[i];
  blockSum[b] = s;
}
// Build all block sums initially
for (let b = 0; b < N/B; b++) rebuildBlockSum(b);

function render(highlightCells, highlightBlocks, updatedIdx) {
  const blocksRow = document.getElementById('blocks-row');
  const arrayRow  = document.getElementById('array-row');
  blocksRow.innerHTML = '';
  arrayRow.innerHTML  = '';

  for (let b = 0; b < N/B; b++) {
    const div = document.createElement('div');
    div.className = 'block-sum' + (highlightBlocks && highlightBlocks.has(b) ? ' updated-blk' : '');
    div.style.background = highlightBlocks && highlightBlocks.has(b) ? '#3a8f48' : BLOCK_COLORS[b];
    div.textContent = 'Σ' + blockSum[b];
    blocksRow.appendChild(div);
  }
  for (let i = 0; i < N; i++) {
    const div = document.createElement('div');
    let cls = 'cell';
    if (updatedIdx === i) cls += ' updated';
    else if (highlightCells && highlightCells.type === 'partial' && highlightCells.set.has(i)) cls += ' highlight-partial';
    else if (highlightCells && highlightCells.type === 'full'    && highlightCells.set.has(i)) cls += ' highlight-full';
    div.className = cls;
    div.textContent = arr[i];
    arrayRow.appendChild(div);
  }
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg; s.className = 'status ' + (cls||'');
}

document.getElementById('btn-update').addEventListener('click', () => {
  const idx = parseInt(document.getElementById('upd-idx').value);
  const val = parseInt(document.getElementById('upd-val').value);
  if (isNaN(idx)||idx<0||idx>15||isNaN(val)||val<0||val>99) {
    setStatus('Index 0–15 and value 0–99 please.','bad'); return;
  }
  arr[idx] = val;
  const b = Math.floor(idx/B);
  rebuildBlockSum(b);
  render(null, new Set([b]), idx);
  setStatus(fmt('Updated a[%idx%] = %val%. Only block %b% sum rebuilt — O(B) = O(4).', { idx: idx, val: val, b: b }), 'ok');
  console.log(fmt('update idx=%idx% val=%val% blockSums=%blockSum%', { idx: idx, val: val, blockSum: blockSum.join(',') }));
});

document.getElementById('btn-query').addEventListener('click', () => {
  const l = parseInt(document.getElementById('qry-l').value);
  const r = parseInt(document.getElementById('qry-r').value);
  if (isNaN(l)||isNaN(r)||l<0||r>15||l>r) {
    setStatus('Need 0 ≤ l ≤ r ≤ 15.','bad'); return;
  }
  // Walk the range: partial left block, full middle blocks, partial right block
  const partialSet = new Set();
  const fullBlockSet = new Set();
  let sum = 0, steps = 0;
  let bL = Math.floor(l/B), bR = Math.floor(r/B);
  if (bL === bR) {
    // Same block — walk individually
    for (let i = l; i <= r; i++) { sum += arr[i]; steps++; partialSet.add(i); }
  } else {
    // Left partial
    const leftEnd = (bL+1)*B - 1;
    for (let i = l; i <= leftEnd; i++) { sum += arr[i]; steps++; partialSet.add(i); }
    // Full middle blocks
    for (let b = bL+1; b < bR; b++) { sum += blockSum[b]; steps++; fullBlockSet.add(b);
      for (let i = b*B; i < (b+1)*B; i++) partialSet.add(i); /* visualize */ }
    // Right partial
    for (let i = bR*B; i <= r; i++) { sum += arr[i]; steps++; partialSet.add(i); }
  }
  const allCells = new Set([...partialSet]);
  const highlightCells = { type: 'partial', set: allCells };
  render(highlightCells, fullBlockSet, null);
  // Color full-block cells distinctly
  const cells = document.querySelectorAll('.cell');
  fullBlockSet.forEach(b => {
    for (let i = b*B; i < (b+1)*B; i++) {
      cells[i].className = 'cell highlight-full';
    }
  });
  setStatus(fmt('Sum a[%l%…%r%] = %sum% (%steps% step%v%, yellow=partial, green=full block).', { l: l, r: r, sum: sum, steps: steps, v: steps!==1?'s':'' }), 'ok');
  console.log(fmt('query l=%l% r=%r% sum=%sum% steps=%steps%', { l: l, r: r, sum: sum, steps: steps }));
});

render(null, null, null);
Result
Console

Click Update to change a single element — notice only that block's sum changes, everything else stays intact: O(1)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×4=82 \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 n\sqrt{n} groups and both directions stay symmetric.

The Real Complexity

Let nn be the array length and BB the block size. The two cost terms are:

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

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

Operation Naive array Prefix-sum table Sqrt decomp Segment tree
Query O(n)O(n) O(1)O(1) O(n)O(\sqrt{n}) O(log⁡n)O(\log n)
Update O(1)O(1) O(n)O(n) O(n)O(\sqrt{n}) O(log⁡n)O(\log n)

A segment tree beats sqrt decomposition on paper (log⁡n<n\log n < \sqrt{n} for large nn). 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(nn)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(n)O(\sqrt{n}) guarantees with minimal implementation overhead.

Where It Matters

The n\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 qq queries in O((n+q)n)O((n + q)\sqrt{n}) time — turning what seems like an O(n⋅q)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 n\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/BB + n/B the answer is always n\sqrt{n}.

Conclusion

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 n\sqrt{n} here, log⁡n\log n in balanced trees, and n2/3n^{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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sqrt-decomposition/Content licensed under CC BY-NC 4.0.