Difference array
= 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\mathrel{+}=v$ and, when present, $d_{r+1}\mathrel{-}=v$.