Prefix Sums: Answer Range Questions Instantly

Running totals

A prefix sum array stores running totals: pre[i] = the sum of the first i numbers. We make it one longer than the data and set pre[0] = 0. Then the total from index i to j is just pre[j + 1] - pre[i].

Think of it like this: A trip meter in a car shows the total distance so far. Distance between two towns = meter at the second town minus meter at the first. No need to re-measure the road.

public class Main {
    public static void main(String[] args) {
        int[] steps = {4000, 6500, 3000, 8000, 7200, 5100, 9900};   // Mon..Sun
        long[] pre = new long[steps.length + 1];
        for (int i = 0; i < steps.length; i++) {
            pre[i + 1] = pre[i] + steps[i];
        }
        System.out.println(java.util.Arrays.toString(pre));
        // total from Tuesday (1) to Friday (4)
        System.out.println("Tue..Fri: " + (pre[5] - pre[1]));
        // weekend (5..6)
        System.out.println("weekend: " + (pre[7] - pre[5]));
    }
}

Output

[0, 4000, 10500, 13500, 21500, 28700, 33800, 43700]
Tue..Fri: 24700
weekend: 15000

Common mistake: Off-by-one errors. With the extra 0 at the front, the range i..j is pre[j + 1] - pre[i]. Write one small example by hand to check.