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)

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

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

q = int(input())
answers = []
for _ in range(q):
    l, r = map(int, input().split())
    answers.append(str(prefix[r] - prefix[l - 1]))

print("\n".join(answers))

Comments

There are no comments at the moment.