Range Add Queries (Difference Array)
Programming Interview
Hard
7 views
Problem Description
For each testcase you get n and q updates. Each update adds val to all positions l..r (1-based). After all updates output final array.
Input Format
First integer t. For each: n q, then q lines: l r val.
Output Format
t lines final arrays.
Sample Test Case
Input:
1
5 3
1 3 10
2 5 -2
5 5 7
Constraints
Sum of n+q over all testcases
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it)); q=int(next(it))
diff=[0]*(n+2)
for i in range(q):
l=int(next(it)); r=int(next(it)); v=int(next(it))
diff[l]+=v
diff[r+1]-=v
cur=0
arr=[]
for i in range(1,n+1):
cur+=diff[i]
arr.append(str(cur))
out.append(' '.join(arr))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!