To answer , split the range into three parts:
Left tail: elements from to the end of 's block
Complete blocks: all blocks fully contained in
Right tail: elements from the start of 's block to For the tails, iterate through individual elements. For complete blocks, add precomputed sums. If and are in the same block, just iterate from to directly. Time: . The tails have at most elements each, and there are at most complete blocks. Both terms are .