Prefix Sum 1D

Concept

Prefix sum precomputes cumulative sums so that any range sum query can be answered in O(1). Build a prefix array where pref[i] = sum of first i elements, then the sum of range [a, b] is simply pref[b] - pref[a-1].

When to Use

• ▸Answering multiple range sum queries on a static array
• ▸Problems that ask 'sum of elements from index L to R'
• ▸Reducing repeated sum calculations from O(n) to O(1) per query
• ▸Subarray sum problems combined with other techniques

Intuition

Imagine you have a running total as you walk through the array. If you know the total up to position B and the total up to position A-1, the difference gives you exactly the sum of elements between A and B. It's like checking how much you spent this week by subtracting last week's balance from today's balance.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    vector<int> pref(n+1, 0);
    int x;
    for(int i = 0; i < n; i++){
        cin >> x;
        pref[i+1] = pref[i]+x;
    }

    int m, a, b, sum;
    cin >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        sum = pref[b] - pref[a-1];
        cout << sum << "\n";
    }

    return 0;
}

// Sample Input:
// 8
// 3 2 4 5 1 1 5 3
// 4
// 2 4
// 5 6
// 1 8
// 3 3
//
// Sample Output:
// 11
// 2
// 24
// 4