First we divide the array into sq = sqrt(n) equal parts Q₁, Q₂, ..., Q_sq , then we sort the queries and answer them offline.

For each part we sort the queries with l inside that part by their r.(Is this part clear?)

Then we use a kind of two pointer to answer the queries. We have two pointers s and e representing the segment that we have its answer at the time and an integer tot representing the answer of the segment [s, e].(At the beginning s = e = 0 and we have the answer of the [s, e] equal to a₀)

When we want to know the answer of a segment [l, r] we simply move s to l and e to r. As we have a good sorting the total number of times we move s and e is not too much :)

let's see how s and e move.

We answer the queries of each part separately so if we prove that the number of times we move e in Q_i is in O(n) then we can say that the total number times we move e is O(n * sqrt(n)).

As we sorted the queries in each part by their r so e moves at most n times(in each part). So e moves a total of n * sqrt(n) times(at the worst time).

Also for each query we change s at most sqrt(n) times (from the beginning of Q_i to the end of it) so the total number of times we change s is O(n * sqrt(n)).

Now it's easy to say that the total number of our moves is O(n * sqrt(n)). :)

Tell me if it was not clear enough.