Try a small problem: repeated range sums
For the array [3, 1, 4, 2], the sum from index 1 through index 3 is 1 + 4 + 2 = 7. A loop answers this once. If you need many range sums on an unchanged array, repeating the loop repeats work.
Store running totals with an initial zero: [0, 3, 4, 8, 10]. The total before index 1 is 3; the total through index 3 is 10. Subtract them to get 7. For inclusive indices left and right, use prefix[right + 1] − prefix[left].
Building the prefix array takes O(n) time and O(n) extra space. Each query then takes O(1). If the original values change, these saved totals need updating; this simple method suits many queries on fixed data.
Learn array operations and complexity →