Range Sum

An array of $N$ positive integers is given. Your task is to answer $Q$ queries of the form "what is the sum of the numbers in the interval$[l,r]$".

Indata

The first line of input contains two integers $N, Q$ ($1 \leq N \leq 3 \cdot 10^5$, $1 \leq Q \leq 10^5$).

The next row contains $N$ positive integers $1 \leq A_i \leq 10^9$.

Afterwards, $Q$ lines follow, each containing two integers $L_{i},R_{i}$ ($0 \leq L_{i} \leq R_{i} \leq N-1$), the interval for the $i$:th question.

Output $Q$ rows, with the $i$:th one containing the answer to the $i$:th question.

Your program will be tested on two subtask groups. To get points for a group, your program must correctly solve in test case in the group.

Sample Input 1	Sample Output 1
5 4 1 4 3 1 2 0 3 0 1 2 3 1 2	9 5 4 7

Authors: Joshua Andersson, Gustav Kalander License: CC BY-SA

CCC lectures

To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 15:00:00, while regular practice lets you submit solutions without any constraints.

You must log in to register.
A Subset sum 2
B Subset sum 3
C Subset sum
D Range Sum
E Range Sum 2
F Range Sum 2.py
G Range Sum SIMD

You must log in to submit solutions to the problem.