Prefix Sum - Step by Step Understanding

Why Do We Need Prefix Sum?

Let us start with a problem.

nums = [2, 5, 3, 1]

Question: Find sum from index 1 to 3.

Normal way:

s = 0
for i in range(1, 4):
    s += nums[i]

Output: 5 + 3 + 1 = **9**

This is fine.

But imagine:

• You have 1000 such questions
• Every time you run a loop

This becomes slow.

Idea of Prefix Sum

Instead of calculating again and again,

we calculate something once, and reuse it.

That something is called a prefix sum array.

What is Prefix Sum?

Prefix means:

“Everything from the start up to this point.”

---

Building Prefix Array

nums = [2, 5, 3, 1]

prefix = [0] * (len(nums) + 1)

for i in range(len(nums)):
    prefix[i + 1] = prefix[i] + nums[i]

print(prefix)

Output:

[0, 2, 7, 10, 11]

---

Understanding This Clearly

Index	Meaning	Value
prefix[0]	no elements	0
prefix[1]	sum of [2]	2
prefix[2]	sum of [2, 5]	7
prefix[3]	sum of [2, 5, 3]	10
prefix[4]	sum of [2, 5, 3, 1]	11

---

Most Important Formula

To find sum from l to r (inclusive, 0-based on nums):

segment_sum = prefix[r + 1] - prefix[l]

---

Example

nums = [2, 5, 3, 1]
prefix = [0, 2, 7, 10, 11]

l = 1
r = 3

print(prefix[r + 1] - prefix[l])

Here: prefix[4] - prefix[1] → 11 − 2 = 9.

Correct answer: 5 + 3 + 1 = 9

---

Why This Works (Very Simple Idea)

Instead of adding again,

we do:

Total till r
minus total till before l

That gives exactly the middle part.

---

Time Complexity

• Build prefix → O(n)
• Each query → O(1)

So after one setup, everything becomes very fast.

---

Prefix Sum + Subarray Thinking

We already know:

Subarray sum = sum from l to r.

Now using prefix:

sum(l … r) = prefix[r + 1] - prefix[l]

So prefix sum helps in all subarray sum problems after preprocessing.

---

Product accumulation - product_accumulation

The same “prefix once, query fast” idea works with multiplication instead of addition.

Build a prefix product array (start with 1 so empty prefix is neutral):

nums = [2, 5, 3, 4]

pref = [1] * (len(nums) + 1)

for i in range(len(nums)):
    pref[i + 1] = pref[i] * nums[i]

For inclusive range l…r on nums (0-based), the product is:

segment_product = pref[r + 1] // pref[l]

Example

nums = [2, 5, 3, 4]
pref = [1, 2, 10, 30, 120]

l, r = 1, 2  # values 5 and 3 → product 15
print(pref[r + 1] // pref[l])  # 30 // 2 = 15

Important note (zeros)

If a range can contain 0, division alone is not enough - you usually track whether the range has a zero separately. Many interview problems avoid zeros or use modulo tricks instead.

---

Important Concept (Complement Idea)

Sometimes the question is:

“Find subarray(s) with sum = k.”

Instead of checking all pairs,

we use this idea:

current_sum - previous_sum = k

Which means:

previous_sum = current_sum - k

Simple Example

nums = [1, 2, 3]
k = 3

Subarrays with sum k:

• [1, 2] → sum 3
• [3] → sum 3

Answer = 2

How We Think

While moving:

• Keep current sum
• Check if (current_sum - k) already appeared

If yes → we found a valid subarray.

---

Difference Array (Basic Idea)

Now a different type of problem:

“Add +5 from index 1 to 3.”

Normal way: update each element → slow

Better idea:

• Add +5 at index 1
• Subtract 5 just after the range ends (example: index 4 if [1…3] is inclusive)

Then rebuild using prefix over the markers.

Example (diff)

diff = [0, 5, 0, 0, -5]

Then apply prefix (conceptually):

arr[0] = diff[0]
arr[1] = arr[0] + diff[1]
arr[2] = arr[1] + diff[2]
# ...

The final array becomes correct after one pass.

---

Overlap counting - overlap_counting

Sometimes we have many ranges (intervals) on a line - like meeting times - and we need to know how many overlap or how many are active at once.

When do two ranges overlap?

For inclusive ranges [a1, b1] and [a2, b2], they overlap if:

a1 <= b2 and a2 <= b1

Example: [1, 3] and [2, 4] overlap (they share 2…3).

Counting many ranges with difference + prefix

Idea: turn each range into two events.

• +1 at the start of a range
• -1 right after the end (so the range still includes the end index)

Then take a prefix sum over those marks. The running value tells you how many ranges cover that position. The maximum value is a classic “maximum overlapping meetings” answer.

# Inclusive ranges [L, R] on a small integer timeline
ranges = [(1, 2), (2, 3), (2, 2)]
M = 6  # big enough for R + 1

diff = [0] * M
for L, R in ranges:
    diff[L] += 1
    if R + 1 < M:
        diff[R + 1] -= 1

active = 0
max_overlap = 0
for x in diff:
    active += x
    max_overlap = max(max_overlap, active)

print(max_overlap)  # 3

This is the same difference array spirit as the section above: mark boundaries once, then one pass (prefix) to read overlaps.

---

Common Mistakes

• Using wrong index in the formula
• Forgetting prefix size = n + 1
• Confusing what each prefix index means
• Recalculating sum unnecessarily

---

Practice Questions

• Build prefix for [4, -1, 2, 3]
• Find sum from index 1 to 3 using prefix
• Count subarrays with sum = 5
• Explain why prefix[r + 1] - prefix[l] works
• Given a list of time ranges, find maximum overlap using +1 / -1 marks and a prefix pass
• Build prefix product and answer a range product query in O(1) (watch zeros)

---

Final Understanding

Prefix sum is:

• A pre-calculation technique
• Makes repeated work faster
• Used in:
  • Range sum
  • Range product (product accumulation)
  • Subarray problems
  • Counting problems (including overlap counting on a timeline)