Question

Jojo is given N integers, A1, A2, ..., AN by his teacher. His teacher also give him 2M integers, L1,L2,...,LM and R1,R2,...,RM. For each i from 1 to M, his teacher asked him to calculate the sum of odd index numbers from index Li to Ri. For example if Li = 3 and Ri = 7, then he has to calculate the value of (A3 + A5 + A7). Help him by making the program to calculate it quickly!

Format Input

The first line consist of two integers, N and M. The second line consist of N integers, A1, A2, ..., AN . The next M lines consist of two integers, Li and Ri.

Format Output

Output M lines, the answer for Li and Ri, where i is an integer from 1 to M. Constraints

• 1 ≤ N, M ≤ 105 • 1≤Ai ≤102
• 1≤Li ≤Ri ≤N

Sample Input 1 (standard input)

53
13 7 1 5 9 11
22
25

Sample Output 1 (standard output)

13 0 10

please use c/c++ language

Answer 1

If you like the solution please give it a thumbs up. And if you have any query please let me know in the comments.

Solution :-

C++ Code :-

#include <iostream>
using namespace std;
  
int main() {
    int n,m;
    cin>>n>>m;

    int a[n+1];
    a[0] = 0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    int sum[n];
    sum[0] = a[0];
    /* sum array is kind of prefix array, sum[i] stores sum of all odd
     index numbers upto ith index */
    for(int i=1;i<=n;i++)
    {
        // if index is odd then only add
        if(i%2 == 1)
            sum[i] = sum[i-1] + a[i];
        else 
            sum[i] = sum[i-1];
    }

    // now simply result for any query (l,r) will sum(r)-sum(l) --> (taking sum upto r index and then excluding upto l)
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;

        cout<<sum[r]-sum[l-1]<<" ";
    }

}

Sample input :-

6 4
4 12 9 5 31 8
1 4
1 6
1 1
3 6

Sample Output :-

13 44 4 40