Range Sum Query

To answer $sum(l, r)$, split the range into three parts:

$1.$ Left tail: elements from $l$ to the end of $l$'s block

$2.$ Complete blocks: all blocks fully contained in $[l, r]$

$3.$ Right tail: elements from the start of $r$'s block to $r$ For the tails, iterate through individual elements. For complete blocks, add precomputed sums. If $l$ and $r$ are in the same block, just iterate from $l$ to $r$ directly. Time: $O(\sqrt{n})$. The tails have at most $B$ elements each, and there are at most $n/B$ complete blocks. Both terms are $O(\sqrt{n})$.