#range-update

Difference Array

Difference Array A difference array stores how each element changes from the previous element. It lets you apply range additions in constant time and reconstruct the final array with a prefix sum. You use it when many range updates are applied before the final values are needed. Problem Given an array $A$ of length $n$, support range updates of the form: $$ A[i] = A[i] + x $$ for every...