Loading...
Loading...
Loading...
A shop has n daily sales figures. Answer q questions. Each gives days l and r (1-based, inclusive); print the total sales from day l to day r. Adding up each range separately is too slow.
Example
Input
5 2 4 1 7 3 9 2 4 1 5
Output
11 24
Try the problem first. Open one hint at a time.
Summing each range costs up to n, so q queries cost q × n.
Build prefix[k] = the total of the first k days once. A range total is prefix[r] - prefix[l - 1].
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor