# Can anyone find optimal solution for this problem

Sum of Subarrays
Given an array of integers, answer queries of the form: [i, j] : Print the sum of array elements from A[i] to A[j], both inclusive.

Input Format

First line of input contains N - size of the array. The next line contains N integers - elements of the array. The next line contains Q - number of queries. Each of the next Q lines contains 2 space separated indexes: i and j.

Constraints

30 points
1 <= N,Q <= 10000

70 points
1 <= N,Q <= 500000

General Constraints
-109 <= A[i] <= 109
0 <= i <= j <= N-1

Output Format

For each query, print the sum of array elements from A[i] to A[j], both inclusive, separated by newline.

Sample Input 0

10 1 30 13 -4 -5 12 -53 -12 43 100 4 0 5 1 7 2 3 7 9

Sample Output 0

47 -19 9 131

MY CODE:

``````#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
long long int size;
cin>>size;
long long int arr[size],sum=0;
for(long long int i=0;i<size;i++)
{
cin>>arr[i];
sum+=arr[i];
arr[i] = sum;
}
long long int que;
cin>>que;
while(que--)
{
long long int x,y;
cin>>x>>y;
if(x==0)
{
cout<<arr[y]<<endl;
}
else
{
cout<<arr[y]-arr[x-1]<<endl;
}
}
return 0;
}
``````

The above code gives tle for single test cases.