Prefix Sums

Prefix sums preprocess cumulative totals so any static interval sum is a subtraction instead of another scan. They work with positive, zero or negative values. The indexing convention is the key: prefix[i] is the sum of the first i elements, so prefix[0]=0. We implement one-dimensional sums, then provide a separate complete two-dimensional example using inclusion–exclusion.

Prerequisites: Arrays; loops; long-long arithmetic.

Build the idea

1. 1. Give each prefix a precise meaning

   For zero-based input a, define P[0]=0 and P[i+1]=P[i]+a[i]. Allocate n+1 entries even though the input has n elements. This extra leading zero represents an empty prefix and avoids a special case for intervals starting at index zero. P[i] is not the sum through index i; it stops BEFORE that index.

2. 2. Subtract the unwanted prefix

   For inclusive [l,r], the desired answer is P[r+1]−P[l]. P[r+1] contains elements 0..r; subtracting P[l] removes exactly 0..l−1. This proof is purely additive, so signed values cause no issue. Queries do not alter the data. A later point change would make stored prefixes after it stale.

3. 3. Trace a signed array

   For [3,−1,4,2], P is [0,3,2,6,8]. Query [1,3] is P[4]−P[1]=8−3=5. Query [0,0] gives 3, and [2,2] gives 4. The prefix array has one more entry than the input, and its values need not be increasing when negatives exist.

   Prefix index	0	1	2	3	4
   Sum of first i values	0	3	2	6	8

4. 4. Extend to a rectangle

   Let P[r][c] sum rows before r and columns before c. With an extra zero row/column, P[r+1][c+1]=a[r][c]+P[r][c+1]+P[r+1][c]−P[r][c]. The upper-left overlap was included twice, so subtract it once. An inclusive rectangle is large prefix minus upper strip minus left strip plus their overlap. The second program makes all four coordinates zero-based externally.

5. 5. Decide when preprocessing pays

   Building prefixes costs linear time in the input size, then each query is O(1). For one tiny query a direct sum may be enough; for many static queries preprocessing is valuable. For updates mixed with queries use Fenwick or segment trees later. Choose long long based on the largest total, not only the largest single element.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n,q;
    std::cin>>n>>q;
    std::vector<long long>prefix(n+1,0);
    for(int i=0;i<n;++i){
        long long x;
        std::cin>>x;
        prefix[i+1]=prefix[i]+x;
    }
    while(q--){
        int l,r;
        std::cin>>l>>r;
        std::cout<<prefix[r+1]-prefix[l]<<'\n'; // Inclusive zero-based [l,r].
    }
}

Complexity analysis

1D: O(n) preprocessing, O(1) per query, O(n) memory. 2D: O(rows·cols) preprocessing/storage and O(1) per rectangle query. The whole program includes input reading and q queries. With 1D n≤200000 or 2D rows·cols≤10^6 and |entry|≤10^9, cumulative values fit long long.

Example input and output

Read n q (0≤n≤200000), then n values |value|≤10^9 and q valid inclusive zero-based intervals l r. n=0 requires q=0. Print each interval sum.

Input

4 3
3 -1 4 2
1 3
0 0
2 2

Output

5
3
4

The prefix table [0,3,2,6,8] gives 8−3=5, 3−0=3 and 6−2=4.

Read rows cols q (positive dimensions, rows·cols≤10^6), then the grid with |entry|≤10^9. Each query r1 c1 r2 c2 is an inclusive zero-based valid rectangle.

// Key idea: 5. Decide when preprocessing pays Building prefixes costs linear time in the input size,
// then each query is O(1).
#include<iostream>
#include<vector>
int main(){
    int rows,cols,q;
    std::cin>>rows>>cols>>q;
    std::vector<std::vector<long long>>p(rows+1,std::vector<long long>(cols+1,0));
    for(int r=0;r<rows;++r){
        for(int c=0;c<cols;++c){
            long long x;
            std::cin>>x;
            p[r+1][c+1]=x+p[r][c+1]+p[r+1][c]-p[r][c];
        }
    }
    while(q--){
        int r1,c1,r2,c2;
        std::cin>>r1>>c1>>r2>>c2;
        std::cout<<p[r2+1][c2+1]-p[r1][c2+1]-p[r2+1][c1]+p[r1][c1]<<'\n';
    }
}

Input

2 3 2
1 2 3
4 5 6
0 1 1 2
1 0 1 0

Output

16
4

The first rectangle contains 2,3,5,6; the second contains only 4.

Complexity: O(rows·cols+q) total time, O(rows·cols) storage.

Practical applications

Use for static range sums, subarray-sum formulas, counting cumulative occurrences and rectangle totals. Difference arrays reverse this viewpoint for batches of updates. Fenwick and segment trees support dynamic sums with logarithmic rather than constant query/update costs.

Check your understanding

If P[i] sums the first i elements, how do you sum inclusive [l,r]?

Put it into practice

Use a frequency prefix to answer how many negative elements lie in each range.