Prefix Sums

Problems on prefix sums, including the sum of any subarray in constant time, two-dimensional sums over rectangles, difference arrays for range updates, counting subarrays with a given sum and balancing a sequence.

The prefix sums article in the Basics section explains the technique. Related problem sets are under Two pointers, Fenwick tree and Range queries.