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; ↵
vi↵
vector<int> arr(n + 5), diff(n + 5), preSum(n + 5);↵
cf(i, 1, n↵
↵
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↵
↵
↵
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<int> 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↵
