Why Prefix Sum Array in DSA C?

The Big Idea

What if you could answer any sum question instantly without adding numbers again and again?

The Scenario

Imagine you have a long list of daily expenses and you want to quickly find out how much you spent between two specific days.

Doing this by adding each day's expense every time you ask is like counting coins one by one every time you want to know your total.

The Problem

Manually adding numbers for each query is slow and tiring, especially if you have many queries.

It is easy to make mistakes by missing a number or adding the wrong range.

This wastes time and causes frustration.

The Solution

A prefix sum array keeps a running total of expenses up to each day.

With this, you can find the sum between any two days by subtracting two prefix sums.

This makes queries very fast and simple.

Before vs After

✗ Before

int sumRange(int expenses[], int start, int end) {
    int total = 0;
    for (int i = start; i <= end; i++) {
        total += expenses[i];
    }
    return total;
}

✓ After

void buildPrefixSum(int expenses[], int prefixSum[], int size) {
    prefixSum[0] = expenses[0];
    for (int i = 1; i < size; i++) {
        prefixSum[i] = prefixSum[i - 1] + expenses[i];
    }
}

int sumRange(int prefixSum[], int start, int end) {
    if (start == 0) return prefixSum[end];
    return prefixSum[end] - prefixSum[start - 1];
}

What It Enables

This lets you answer sum queries instantly, even on huge lists, saving time and effort.

Real Life Example

Bank apps use prefix sums to quickly show your spending between any two dates without recalculating every time.

Key Takeaways

Manual summing is slow and error-prone for many queries.

Prefix sum arrays store running totals to speed up range sum queries.

They make repeated sum queries fast and simple.