I know that difference array is a well-known and important topic of Comptetive programming

There is a famous blogpost about difference array in codeforces. I saw that and I tried to understand by the documentation. but I struggled very much .

Here is my understanding of difference array .

first I shall give a simple overview of difference array . It's an algorithm that let's you do queries in a O(n) complexity.

Here's I see solve a difference array problem :

• You’ve got an array.
• Instead of updating every element in a range [l,r], you just mark the boundaries.
• At l, you add +x → “start adding here.”
• At r+1, you add -x → “stop adding after r.”
• Then you take a prefix sum of this difference array.
• That prefix sum tells you exactly how much to add at each position.
• Finally, overlay it on the original array → boom, all range updates applied in O(n+q).

Example Array size = 5, initially [0,0,0,0,0] Query: add +3 to range [2,4] Steps: - Difference array: diff[2] += 3, diff[5] -= 3 → diff = [0,0,3,0,0,-3] - Prefix sum: [0,0,3,3,3,0] - Apply to original: [0,3,3,3,0]

And here is the code :

int main() { int n, q, l, r, x; cin >> n >> q; vi arr(n + 5), diff(n + 5), preSum(n + 5); cf(i, 1, n) cin >> arr[i]; while (q--) { cin >> l >> r >> x; diff[l] += x; diff[r + 1] -= x; } for (int i = 1; i <= n; i++) { preSum[i] = preSum[i — 1] + diff[i]; } for (int i = 1; i <= n; i++) { arr[i] += preSum[i]; } for (int i = 1; i <= n; i++) cout << arr[i] << " "; }

just by using l and r method of partial sum and adding and substracting it. We have done it so easily