Management now wants MANY such range totals answered quickly, for dozens of different day ranges, without recomputing from scratch each time. Read N integers and Q queries, each a range [L,R]. For each query print the sum of a[L..R]. Build a prefix sum array first so each query is O(1) — don't recompute sums from scratch each time.
Input
Line1: N Q. Line2: N integers. Next Q lines: L R.
Output
Q integers, one sum per line.
Constraints
1 ≤ N,Q ≤ 10^5
Sample Input
5 2 1 2 3 4 5 1 3 2 5
Sample Output
6 14
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.