CSUMQ  Cumulative Sum Query
William Macfarlane wants to look at an array.
You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the sum of every number between the range [i, j] (inclusive).
Note: the query ranges are specified using 0based indexing.
Input
The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N1).
Output
For each query, output the answer to that query on its own line in the order the queries were made.
Example
Input: 3
1 4 1
3
1 1
1 2
0 2
Output: 4
5
6
hide comments
sourav_halder:
20210616 16:47:34
use partial sum 

eager_to_code:
20210616 16:14:44
is there any discussion tab? 

shreyasz_07:
20210613 14:52:53
use kruskal algorithm


sandy5823:
20210530 00:20:28
Striver 

sugam10:
20210428 06:57:37
use prefix sum


mazharul_sub:
20210322 20:53:53
i am a dumb


linhthebest:
20210223 03:09:18
I´m a faggot. Last edit: 20210223 10:52:10 

nitish_verma26:
20210201 14:18:29
Sparse table is best suited for these type of questions where original array is not changing. One should go for this. 

adikrmishra_1:
20200629 19:36:40
simple prefix sum question with some if else conditions :) 

shanto09:
20200619 17:59:08
Simple prefix sum problem. As the time constraint is very high brute force would work. 
Added by:  Joshua Kirstein 
Date:  20141027 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Hi Mom! 