Add to a range with two markers
Record boundary changes and reconstruct all values after the updates.
Differences remember change
For one-based values with a conceptual a[0] = 0, define D[1] = a[1] and D[i] = a[i] − a[i − 1]. For [4, −2, 7, 0, 3], the differences are [4, −6, 9, −7, 3]. A running sum of D reconstructs each original value because the intermediate terms cancel.
Keep the meanings separate: P[i] is a total through position i, a[i] is the value there, and D[i] is the change from the previous value. This course’s partial-sums range-update topic uses difference arrays; std::partial_sum is a separate numeric-library operation.
Turn an addition on, then turn it off
For an initially zero array, adding delta to every inclusive position [l, r] needs D[l] += delta and D[r + 1] −= delta. During reconstruction, the addition is active from l through r and canceled immediately after it.
Allocate n + 2 entries: index 0 is padding and n + 1 is a cancellation sentinel. Print only positions 1 through n. Ending an update at n still has a valid r + 1 marker. Canceling at r would incorrectly exclude the right endpoint.
// Complete C++23 program. Input: n updates, then inclusive l r delta.
// Start with n zeros. All updates occur before reconstruction.
#include <iostream>
#include <vector>
int main() {
int n, updates;
std::cin >> n >> updates;
std::vector<long long> diff(n + 2, 0);
for (int j = 0; j < updates; ++j) {
int l, r;
long long delta;
std::cin >> l >> r >> delta;
diff[l] += delta;
diff[r + 1] -= delta;
}
long long current = 0;
for (int i = 1; i <= n; ++i) {
current += diff[i];
if (i > 1) std::cout << ' ';
std::cout << current;
}
std::cout << '\n';
}Overlaps add; assignments are different
Accumulate markers with += and −=. Several updates may start or stop at the same boundary, and assigning a marker would overwrite earlier contributions. Negative updates work with the same rule; an update and its opposite cancel.
This method implements addition, not “set every element to x.” Independent additive contributions can be summed, whereas assignments depend on replacement order. Recording u updates is O(u), but initialization, reconstruction, and output add O(n), for O(n + u) total time and O(n) storage.
Difference array
Start with eight zeroes. Add to an inclusive range using d[l] += v and d[r + 1] -= v. The last cell is a sentinel.
Difference array (index 8 is the sentinel)
Values after accumulation
No updates yet. Choose a range, then apply an addition.
Guided simulation · Change the inputs to test your understanding.
To add 4 to inclusive positions [2, 5], where does the negative marker belong?
Turn the idea into code
Start with five zeros. Apply [2,4] += 3, [1,2] += −1, [4,5] += 2. Find both the six real-and-sentinel markers and the five final values.
Give me a hint
Add all boundary contributions first, then take one running sum.
Show the explained solution
Markers at indices 1..6 are [−1, 3, 1, 2, −3, −2]. The five final values are [−1, 2, 3, 5, 2]. Including the sentinel returns the running added amount to zero.
Your notes
Mark complete when you can explain it yourself.