Skills101
← All coding problems

Range Updates With a Difference Array

easyArrays & Prefix Sums+10 XPTime limit 2s

A row of n lamps all start with brightness 0. You receive q instructions "add x to the brightness of every lamp from l to r" (x may be negative). After all instructions, print the brightness of every lamp.

Input:

  • line 1: n q
  • next q lines: l r x (1-based, l ≤ r)

Output: one line with the n final brightness values.

Constraints: 1 ≤ n, q ≤ 10⁵, −10⁴ ≤ x ≤ 10⁴.

Think about it: updating every lamp in the range costs O(n) per instruction. Instead keep a difference array: add x at l and subtract x just after r. One prefix sum at the end turns the differences into the final values — O(n + q) in total.

Sample input 1

5 3
1 3 2
2 5 -1
4 4 10

Sample output 1

2 1 1 9 -1

Sample input 2

1 1
1 1 7

Sample output 2

7

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.