Editorial for Range Additions

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

Applying each query directly to every element in $[l, r]$ ~[l, r]~ can take $O(nq)$ ~O(nq)~, which is too slow.

Instead, use a difference array:

To add $x$ ~x~ to every element in $[l, r]$ ~[l, r]~, add $x$ ~x~ at position $l$ ~l~.
Subtract $x$ ~x~ at position $r + 1$ ~r + 1~ if that position exists.
After processing all queries, take a prefix sum over the difference array to recover how much should be added to each index.

Then add that running total to the original array.

This processes all updates in $O(q)$ ~O(q)~ and the final reconstruction in $O(n)$ ~O(n)~, so the total time complexity is $O(n + q)$ ~O(n + q)~.

Solution (Python)

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)

n = next(it)
q = next(it)
a = [next(it) for _ in range(n)]
diff = [0] * (n + 1)

for _ in range(q):
    l = next(it) - 1
    r = next(it)
    x = next(it)
    diff[l] += x
    if r < n:
        diff[r] -= x

cur = 0
ans = []
for i in range(n):
    cur += diff[i]
    ans.append(str(a[i] + cur))

sys.stdout.write(" ".join(ans) + "\n")

Comments

There are no comments at the moment.