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↵
↵
↵
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()
{
for (int i = 1; i <= n; i++)
{↵
{↵
}↵
↵
