Prefix Sum

🐷 Introduction: The Piggy Bank Problem

Imagine you have a piggy bank, and every day you put some coins in it.

• Day 1: 3 coins
• Day 2: 2 coins
• Day 3: 4 coins
• Day 4: 1 coin
• Day 5: 5 coins

If your friend asks, "How many coins did you put in from Day 1 to Day 3?", you would have to add them up: 3 + 2 + 4 = 9.

Then your friend asks, "How about from Day 2 to Day 5?". You have to add them up again: 2 + 4 + 1 + 5 = 12.

If your piggy bank had 100 days of coins, adding them up over and over again for different days would be super slow and make your brain hurt!

What if there was a magic trick to find the answer instantly without doing all that adding?

📝 The Magic Diary (Prefix Sum)

Instead of just writing down how many coins you added each day, what if you kept a special diary? In this diary, you write down the TOTAL number of coins currently in the piggy bank at the end of each day!

Let's make our special diary:

• Day 1: 3 coins -> Total: 3
• Day 2: 2 coins -> (3 + 2) = Total: 5
• Day 3: 4 coins -> (5 + 4) = Total: 9
• Day 4: 1 coin -> (9 + 1) = Total: 10
• Day 5: 5 coins -> (10 + 5) = Total: 15

This special "Total Diary" is what programmers call a Prefix Sum array!

✨ How to Use the Magic Diary

Now, if your friend asks, "How many coins did you add from Day 2 to Day 4?"

You don't need to add Day 2 + Day 3 + Day 4 anymore! You just do one simple math problem using your diary:

1. Look at the total on Day 4 (which is 10). This is all the coins from the very beginning.
2. We only want coins starting from Day 2, so we need to throw away the coins from Day 1. Look at the total on Day 1 (which is 3).
3. Subtract them! 10 - 3 = 7 coins!

You found the answer instantly! Formula: Sum from Day A to Day B = Total at Day B - Total right before Day A

---

🦸 Why Do We Need To Learn It?

In computer programming, we often have huge lists (arrays) with millions of numbers. Sometimes, the computer gets asked thousands of questions like "What is the sum of numbers from index 100 to index 5000?"

If the computer adds them up one by one every single time, it will take forever! (This is called O(N) time).

But if we spend a little time at the beginning to build our "Magic Diary" (Prefix Sum array), we can answer any question instantly in just one step! (This is called O(1) time). It makes our programs lightning fast!

---

🧮 Let's Look at Some Code! (Building the Diary)

Let's write code to take a normal array of numbers and turn it into a Prefix Sum array.

Complete Implementations

---

🧩 Problem 1: Range Sum Query

This is exactly like the piggy bank problem! You are given an array of numbers. Then, you will be asked many times to find the sum of numbers between two indices left and right.

The Strategy

1. First, build the Prefix Sum array (the magic diary).
2. When asked for the sum from left to right:
   • If left is 0, just return prefix[right].
   • Otherwise, return prefix[right] - prefix[left - 1]. (Take the big total and subtract the part we don't want!)

Complete Implementations

---

🚫 Common Mistakes

1. Off-by-One Errors: When subtracting, remember to subtract prefix[left - 1], NOT prefix[left]. If you subtract prefix[left], you accidentally throw away the starting number too!
2. Left is Zero: If left is 0, left - 1 is -1, which will crash your program. Always handle the left == 0 case separately!

---

📚 Summary

• Prefix Sum is like a magic diary that keeps track of a running total.
• It changes slow O(N) addition into lightning-fast O(1) subtraction.
• Formula: Sum(left, right) = Prefix[right] - Prefix[left - 1].

---

🎮 Practice Problems & Website Verifications

Verify your prefix sum logic by solving these interactive problems on our platform:

• Product of Array Except Self — Learn to use prefix and suffix arrays together!
• Maximum Subarray — Kadane's algorithm, a variation of prefix sum logic.