QARRAY2 - Query on an array II
Adeeb is the promising programmer of BSMRSTU . One day he was solving a problem of RMQ(Range Sum Query). The solution he was written is given below:
int n, q ;
scanf("%d %d",&n, &q) ;
int a[n];
for(int i = 0 ; i < n ; ++i){
scanf("%d",&a[i]) ;
}
int l, r ;
while(q--){
scanf("%d %d",&l, &r) ;
int res = 0 ;
for(int i = l ; i <= r ; ++i){
res += a[i] ;
}
printf("%d\n",res);
}
Input
There will be T test cases.
In every test case, you will be given n and q as the input.
The next line will contain n space separated integers, the value of the array a.
Constraint:
1 <= T <= 10
1 <= n, q <= 105
1 <= l <= r <= n, 1 <= ai <= 109 .
Output
In every test case, print q lines of output, one integer for the corresponding query.
Example
Input:
1 5 2
1 2 3 4 5
1 4
2 5 Output: 10
14
hide comments
boemogensen:
2019-03-30 06:19:40
Only Prefix Sum for Classic Problem ? Move this problem to tutorial |
Added by: | Prodip |
Date: | 2019-03-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |