Prefix sums · 3 of 3
Difference arrays
Apply many range additions with two writes each, then recover every value with one running sum.
- More on Prefix Sums Its difference arrays section solves Greg and Array on Codeforces, where the updates themselves arrive in ranges. usaco.guide (opens in a new tab)
- 前缀和 & 差分 (Prefix sums and differences) Difference arrays in one dimension, in two or more dimensions, and along the paths of a tree. oi-wiki.org (opens in a new tab)