Range Add Queries (Difference Array)

Range Add Queries (Difference Array)

Hard Programming Interview Data Structures 24 views
Explanation Complexity

Problem Statement

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.

Example

1
5 3
1 3 10
2 5 -2
5 5 7
10 8 8 -2 5

Constraints

Sum of n+q over all testcases

Input / Output Format

Input Format
First integer t. For each: n q, then q lines: l r val.
Output Format
t lines final arrays.
Constraints
Sum of n+q over all testcases

Examples

Input:
1 5 3 1 3 10 2 5 -2 5 5 7
Output:
10 8 8 -2 5

Example Solution (Public)

Programming Interview 
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))

Official Solution Code

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))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.