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 :

include <bits/stdc++.h>

using namespace std;

int main() {

int n, q, l, r, x;

cin >> n >> q;

vector arr(n + 5), diff(n + 5), preSum(n + 5);

for(int i =1; i<=n ; i++) 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] << " "; } return 0; }

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