IntermediatePrefix Sums2000 ms256 MB
Prefix Sum Queries
Answer range sum queries on a list using 1-based inclusive indexes.
Statement
Answer range sum queries on a list using 1-based inclusive indexes.
Input
First line: `n q`. Second line: `n` integers. Next `q` lines: `l r`.
Output
Print each range sum on its own line.
Constraints
- `1 <= n, q <= 100000`
Examples
Example 1
Input
5 3
2 4 6 8 10
1 3
2 5
4 4Output
12
28
8Use prefix sums to answer each range quickly.
Sample runs use visible examples. Full submissions are checked securely on the server, and private test cases are not shown in the browser.