Help with Prefix Sum Static Range Sum Problem C++

Problems and Contests
#1

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!

#2

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)

#3

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!

#4

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).

#5

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

#6

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

#7

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).

#8

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

#9

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