Get sum of some arrays' elements C++ -

how possibly sum of elements between 2 given points in array if given:

n - array length

m - number of questions array

a[n] - array numbers

m questions in format x y

example

input

3 3

-1 2 0

3 3

1 3

1 2

output

0

1

1

here code

#include <iostream> #include <numeric> using namespace std; int main() {     int n,m,x,y;     cin>>n>>m;     int [n];     int s [m];     (int = 0; < n; i++){         cin>>a[i];     }     (int = 0; < m ; i++){         cin>>x>>y;         if(x == y){             s[i] = a[x-1];             continue;         }         s[i] =  accumulate(a + x - 1, + y,0);     }     (int = 0; < m; i++){         cout<<s[i]<<endl;     }     return 0; } 

this not school homework, task internet - run on test server using standard streams input , result check.

i need program run in less 0.2 seconds with:

0 < n,m <= 50000

-1000 <= a[i] <= 1000

1<=x<=y<=n

how can make run more time efficiently?

a lot of time can spent in accummulate function when n , m large.

let's use following data in our example:

const int n = 10;  int a[n] = {6, 1, 3, 2, 9, 8, 7, 2, 0, 1}; 

let's create auxiliary array , fill sums a[0] a[i] each i. can made in single loop.

int s[n+1];  void precalculate() {     s[0] = 0;     (int = 0; < n; ++i) {         s[i+1] = s[i] + a[i];     }    } 

then whole accummulate function collapses single subtraction:

int accummulate(int i, int j) {     return s[j] - s[i-1]; } 

it works can demonstrated:

int main() {     precalculate();     assert(accummulate(1, 1) == 6);     assert(accummulate(10, 10) == 1);     assert(accummulate(1, 10) == 39);     return 0; }