8821: [yosupo] Data Structure - Static Range Sum
[Creator : ]
Description
You are given a non-negative integer sequence $A = (a_0, a_1, \ldots, a_{N-1})$ with the length $N$. Process the following $Q$ queries in order:
- You are given integers $l_i$ and $r_i$. Print $\sum_{k=l_i}^{r_i-1} a_k$.
- You are given integers $l_i$ and $r_i$. Print $\sum_{k=l_i}^{r_i-1} a_k$.
Input
$N$ $Q$
$a_0$ $a_1$ $\ldots$ $a_{N-1}$
$l_1$ $r_1$
$\vdots$
$l_Q$ $r_Q$
$a_0$ $a_1$ $\ldots$ $a_{N-1}$
$l_1$ $r_1$
$\vdots$
$l_Q$ $r_Q$
Constraints
$1≤N≤500,000$
$1≤Q≤500,000$
$0≤a_i≤10^9$
$0≤l_i<r_i≤N$
Sample 1 Input
5 5
1 10 100 1000 10000
2 3
0 3
2 5
3 4
0 5
Sample 1 Output
100
111
11100
1000
11111