Medium · Lazy Difference Tree
Understand → Visualise → Practice.
Apply inclusive range additions to a zero array and return values at requested points.
Instead of touching every cell, add x at the left end and subtract x just past the right end. A single running sum then rebuilds every value.
For update [l, r, x], do diff[l] += x and diff[r + 1] −= x.
Walk left to right keeping a running total of diff; the running total at i is the final value at i.
Return the rebuilt values at the requested positions.
O(n + u + q) time and O(n) space for n cells, u updates and q points.
Allocate diff with length + 1 entries so diff[r + 1] is safe when r is the last index.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.