Working with positions

Many problems compare each value with the one before it: loop from i = 1 and look at a[i - 1] and a[i].

A prefix sum array stores running totals: pre[i + 1] = pre[i] + a[i]. Then the sum of positions l to r is pre[r + 1] - pre[l], with no loop.