# Help with Prefix Sum Static Range Sum Problem C++

I’m working on Silver>Prefix Sum. Here is the exact problem I’m doing:

In my code, I correctly generated a prefix sum array. However, I’m confused on how to handle each query. Currently for each query (l, r), I’m simply doing prefixSum[r]-prefixSum[l]. This works for the example case, but not for the hidden cases. I’m not sure how to fix it.
Here is my code (C++)

#include <iostream>
#include <vector>
using namespace std;

int main(){
int N, Q;
cin >> N >> Q;
int prefixSum[N+1] = {0};
//Generates the prefix sum array
for (int i = 1; i<N+1; i++){
int val;
cin >> val;
prefixSum[i] = prefixSum[i-1] + val;
}
//Prints the prefix sum array
for (auto i:prefixSum){
cout << i << " ";
}
cout << endl;

//Calculates each query
for (int i = 0; i<Q; i++){
int l, r;
cin >> l >> r;

cout << (prefixSum[r]-prefixSum[l]) << endl;
}

return 0;
}


Again, I’m 99% sure the problem with my code is in  cout << (prefixSum[r]-prefixSum[l]) << endl; calculation. Please let me know how I should fix it.

Thanks!

You want to do prefixsum[r] - prefixsum(l-1).

You don’t want to subtract A(l).

(Sorry for poor formatting, I’m on mobile)

Hi! Yes I actually tried that before, but the problem with l-1, is that sometimes l = 0. Thus 0-1 doesn’t work.

The index on the question start from 0, meaning r or l can be 0. Please let me know if I’m mistaken!

but the problem with l-1, is that sometimes l = 0

That’s why prefix sum arrays are usually 1-indexed (the 0th element is usually 0).

Alternatively, you can just check to see if l = 0 and handle that case separately (by subtracting 0).

I think the best way to implement this is to create an n+1 size array, ps[n+1], and set ps=0. Then it works as needed because the prefix sum with no values is actually 0.

I recommend creating a function to handle ranges separately for convenience if you’re going to use zero-indexing (assuming for instance that your prefix sums array is \text{dp}):

// sum from l to r, inclusive, zero-indexed
// here, "inline" is just a request to the compiler to optimize overhead
// since what we're doing in the function is really just O(1)

inline int sum(int l, int r) {
return l == 0 ? dp[r] : dp[r] - dp[l - 1];
}


Then, replace the relevant lines in your code with \text{sum}(l,r).

Also watch out for integer overflow (use long longs).

Thank you everyone for your helpful suggestions! The error was actually integer overflow (thanks for catching that @dongliu0426)!