How to build difference array
A difference array is a useful technique for applying many range updates efficiently.
Instead of changing every element in a segment , we update only a few positions in an auxiliary array. After processing all updates, we rebuild the final array using prefix sums.
This makes each range update run in time.
Given an array of length , we define its difference array diff as:
So diff[i] shows how much the value changes when we move from position i - 1 to position i.
If we want to add to every element in the range , we do:
diff[L] += xdiff[R + 1] -= x if Why does this work?
L, all values should increase by xR + 1, that increase should stopAfter applying all updates, we rebuild the array with prefix sums:
diff[L] += xdiff[R + 1] -= x if it is inside the arraySuppose:
Then the difference array is:
Now apply the update: add to the range .
We update:
diff[2] += 3There is no need to apply diff[5] -= 3 because position 5 is outside the array.
Now:
Rebuilding the array:
So the final array becomes:
You are given an array of zeros and operations. Each operation adds to all elements in a range . After all operations, print the final array.
vector<long long> diff(n + 2, 0);
diff[1] = a[1];
for (int i = 2; i <= n; i++) {
diff[i] = a[i] - a[i - 1];
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> diff(n + 2, 0);
for (int i = 1; i <= q; i++) {
int L, R;
long long x;
cin >> L >> R >> x;
diff[L] += x;
if (R + 1 <= n) {
diff[R + 1] -= x;
}
}
vector<long long> a(n + 1, 0);
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + diff[i];
cout << a[i] << " ";
}
cout << "\n";
return 0;
}