Editorial for Scavenging in Fountains

Approach

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

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

Building the prefix sums takes $O(n)$, and answering all queries takes $O(q)$, so the total time complexity is $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))