📑 Prefix Sum Pattern

🔎 What is Prefix Sum?

A prefix sum is the cumulative sum of elements in an array up to a certain index.
It allows us to compute range sums and solve subarray problems efficiently.

Example:
Array = [1, 2, 3, 4]
Prefix Sum = [1, 3, 6, 10]

• Prefix[0] = 1
• Prefix[1] = 1 + 2 = 3
• Prefix[2] = 1 + 2 + 3 = 6
• Prefix[3] = 1 + 2 + 3 + 4 = 10

⚙️ Algorithm

1. Initialize an array prefix of the same length as input.
2. Set prefix[0] = arr[0].
3. For each i from 1 to n-1:
   prefix[i] = prefix[i-1] + arr[i]
4. Use the prefix array to answer queries in O(1).

⏱ Complexity Analysis

• Precomputation: O(n)
• Query: O(1)
• Space: O(n) for prefix array (O(1) if done in-place with careful handling)

❓ Why Use Prefix Sums?

Without prefix sums → range sum query [i, j] takes O(n).
With prefix sums → range sum query [i, j] takes O(1).

🧮 Example: Range Sum Query

Problem: Given an array arr and indices i, j, compute the sum between them.

class Solution:
    def compute_prefix_sum(self, arr):
        prefix = [0] * len(arr)
        prefix[0] = arr[0]
        for i in range(1, len(arr)):
            prefix[i] = prefix[i - 1] + arr[i]
        return prefix

    def range_sum_query(self, prefix, i, j):
        if i == 0:
            return prefix[j]
        return prefix[j] - prefix[i - 1]

# Example usage
arr = [1, 2, 3, 4]
sol = Solution()
prefix_sum = sol.compute_prefix_sum(arr)
print(sol.range_sum_query(prefix_sum, 1, 3))  # Output: 9

🛠 Applications

1. Range Sum Queries – O(1) retrieval of subarray sum.
2. Subarray Problems – find subarrays with given sum, max subarray sum, etc.
3. 2D Prefix Sums – efficient sum queries in submatrices.
4. Frequency Counting – cumulative counts for data analysis.
5. Load Balancing – distribute workloads evenly in systems.

🧾 Key Formula

For subarray sum from i to j:

• If i == 0: sum = prefix[j]
• Else: sum = prefix[j] - prefix[i - 1]

📌 Common Problems Solved Using Prefix Sum

1. Range Sum Query (LeetCode 303)

• Precompute prefix sums.
• Answer queries in O(1).

2. Subarray Sum Equals K (LeetCode 560)

• Use a hash map to store prefix sums seen so far.
• Check if (prefix_sum - k) exists → that means a subarray with sum k exists.

3. Maximum Subarray Sum (Kadane’s Alternative)

• Can be solved with prefix sums by tracking minimum prefix sum seen so far.

4. Equilibrium Index

• Index i where sum of left elements = sum of right elements.
• Use prefix sums to compute quickly.

5. Count of Subarrays Divisible by K

• Store prefix sums modulo K in a hash map.
• Count how many times each modulo value appears.

6. 2D Prefix Sum Problems (LeetCode 304)

• Precompute a 2D prefix matrix.
• Any submatrix sum can be queried in O(1).

7. Balanced Parentheses / Matching Problems

• Convert string to +1/-1 array.
• Use prefix sums to check validity efficiently.