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.
