Building a Difference Array

Implement build_diff(n, upd), which returns the raw difference array itself, not the final array of apply_updates. The convention is exact: the returned array has size n + 1. For each update (l, r, v) in upd (0-indexed, v added to every index in [l, r] inclusive), add v at diff[l] and subtract v at diff[r + 1], one slot past the end of the range, never at diff[r] itself.

That trailing slot, diff[n], only ever exists to absorb the -v from an update whose r reaches the last index (r == n - 1); it is never read back out by anything that only cares about indices 0..n-1.

Worked example: build_diff(5, {(1,3,2), (0,4,1)}):

• Start with diff = {0, 0, 0, 0, 0, 0} (size n + 1 = 6).
• Update (1, 3, 2): add 2 at diff[1], subtract 2 at diff[4] (r + 1 = 4) → {0, 2, 0, 0, -2, 0}.
• Update (0, 4, 1): add 1 at diff[0], subtract 1 at diff[5] (r + 1 = 5) → {1, 2, 0, 0, -2, -1}.
• Result: {1, 2, 0, 0, -2, -1}.

Prefix-summing indices 0..n-1 of that result (1, 1+2=3, 3+0=3, 3+0=3, 3+(-2)=1) gives {1, 3, 3, 3, 1}, exactly the array apply_updates(5, {(1,3,2), (0,4,1)}) returns. build_diff and apply_updates are the same idea split into its two halves: build the difference array, then prefix-sum it.

Input format: each test in tests/*.in is laid out as:

• Line 1: n k, the array length and the number of updates.
• Next k lines: l r v, one range update per line.

Test 06.in reads:

1 1
0 0 9

This is a length-1 array with one update, l = 0, r = 0, v = 9: the whole update touches just index 0.

Where you'll use it:

• 1109. Corporate Flight Bookings
• 1094. Car Pooling
• 2381. Shifting Letters II