Point Updates

To update $arr[i]$ to a new value $v$:

$1.$ Find which block $i$ belongs to: $b = \lfloor i/B \rfloor$

$2.$ Update the block sum: $blockSum[b] = blockSum[b] - arr[i] + v$

$3.$ Update the array: $arr[i] = v$ That's it. One block update, one array update. Time: $O(1)$. Compare this to segment trees where updates take $O(\log n)$. For problems with many updates, sqrt decomposition has faster updates but slower queries. The tradeoff depends on your query-to-update ratio.