Building Block Sums

Start with range sum queries. Precompute the sum of each block in $O(n)$ time. For each element at index $i$, add it to $blockSum[\lfloor i/B \rfloor]$.

After processing all elements, $blockSum[k]$ holds the sum of block $k$. This preprocessing happens once.

Now queries can skip entire blocks by using precomputed sums instead of iterating through every element. The space is $O(\sqrt{n})$ for the block sums array.