Introduction
Prefix Sum is one of the most important techniques in Competitive Programming. It helps us answer range sum queries efficiently.
Definition
Given an array:
1 2 3 4 5
The prefix sum array is:
1 3 6 10 15
Where:
prefix[i] = prefix[i-1] + a[i]
Why Use Prefix Sum?
Without Prefix Sum: Range Sum Query = O(n)
With Prefix Sum: Range Sum Query = O(1)
Formula
Sum from index l to r:
prefix[r] — prefix[l-1]
Example
Array: 1 2 3 4 5
Prefix: 1 3 6 10 15
Sum(2,4):
2 + 3 + 4 = 9
Using Prefix Sum:
10 — 1 = 9
Code Example (Python)
n = int(input()) a = list(map(int, input().split()))
prefix = [0]
for x in a: prefix.append(prefix[-1] + x)
l, r = map(int, input().split()) print(prefix[r] — prefix[l-1])
Practice Problems
- Codeforces 363B — Fence
- Codeforces 433B — Kuriyama Mirai's Stones
- Codeforces 255A — Greg's Workout
Conclusion
Prefix Sum is a basic but powerful technique that appears frequently in Codeforces contests and should be mastered before learning Sliding Window, Binary Search, and Dynamic Programming.
include 0 in the prefix array for better understanding, many people would get confused what p[i-1] is at the start.
For those wondering, the main idea behind
prefix[r] - prefix[l-1]is "adding all stuff before removing the unwanted ones". For instance:sum(2, 4) of {1, 2, 3, 4, 5}You want
2 + 3 + 4, which is(1 + 2 + 3 + 4) - (1):By removing the latter section from the former section, you get the wanted part. This is why
prefix[r] - prefix[l-1]works.