jainvidhika410's blog

Prefix Sum Tutorial for Beginners
By jainvidhika410, history, 11 hours ago, In English

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

  1. Codeforces 363B — Fence
  2. Codeforces 433B — Kuriyama Mirai's Stones
  3. 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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

include 0 in the prefix array for better understanding, many people would get confused what p[i-1] is at the start.

→ Reply
»
7 hours ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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):

prefix[r]  :  |-----|
prefix[l-1]:  |-|
              1 2 3 4 5
wanted part:    |---|

By removing the latter section from the former section, you get the wanted part. This is why prefix[r] - prefix[l-1] works.

→ Reply