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.
Problems
Range Sum Query#6959
Very easy
Skiing#7171
Medium
Races#7174
Easy
Maximum#7257
Very easy
Segments#7287
Medium
Stations#7301
Easy
Memory Manager#7328
Medium
Zero quintuples#7448
Medium
UFO#7472
Medium
Trading#7482
Very easy
Adjustment Office#7561
Very easy
Landscape Improved#7572
Very hard
Square#7757
Medium
Cow Confinement#7774
Very hard
Guessing Camels#7868
Very easy
Shortcut#7977
Very hard