 Difference array

For an array $a$, its difference array stores $d_0=a_0$ and $d_i=a_i-a_{i-1}$ for $i>0$. The original entries are prefix sums of $d$. Adding $v$ on indices $[l,r]$ requires only $d_l+=v$ and, when present, $d_{r+1}-=v$.