Editorial for Scavenging in Fountains

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Precompute prefix sums, where prefix[i] stores the total value of the first $i$ ~i~ coins.

Then each query asking for the sum from $l$ ~l~ to $r$ ~r~ can be answered in constant time as prefix[r] - prefix[l - 1].

Building the prefix sums takes $O(n)$ ~O(n)~, and answering all queries takes $O(q)$ ~O(q)~, so the total time complexity is $O(n + q)$ ~O(n + q)~.

Solution (Python)

from sys import stdin, stdout

readline = stdin.buffer.readline
write = stdout.write

n = int(readline())
prefix = [0] * (n + 1)

for i, value in enumerate(map(int, readline().split()), start=1):
    prefix[i] = prefix[i - 1] + value

q = int(readline())
for _ in range(q):
    l, r = map(int, readline().split())
    write(f"{prefix[r] - prefix[l - 1]}\n")

Comments

There are no comments at the moment.