Ref
Original problem: https://codeforces.com/contest/295/problem/A
Intro
The difference array is a mathematical technique built on top of prefix sums. It computes and stores the differences between adjacent values of the original array, applies range additions/subtractions in O(1) per operation, and finally runs one prefix sum pass over the difference array to reconstruct the array after all the range updates. It is commonly used for static range-update problems.
The Math Behind It
Imagine this scenario: you're given multiple ranges [l, r], and for each range, every value between l and r must be incremented by 1. The brute-force approach is easy — just iterate over the range in the original array and add, at O(n) per operation — but the performance simply doesn't cut it. Here's the key observation: if an entire range is incremented or decremented together, the differences between adjacent values inside that range stay the same. For example, [1,1,1,1,1] becomes [1,2,2,2,1] — the differences among the middle 2,2,2 are still 0; only the differences at the boundaries of the range (where it meets its neighbors) change. So let's write out the difference array before and after the change. The formula is d[i] = a[i] - a[i - 1], and we also need two zero-valued sentinel nodes at the head and tail (marked with * here):
[0*, 1, 0, 0, 0, 0, 0*] -> [0*, 1, 1, 0, 0, -1, 0*]
Before reading on, try taking the prefix sum of this difference array yourself — if the prefix sum result equals the original array, that proves the difference array is correct.
Looking at how the difference array changed: our operation was to add 1 to every element in the range [2, 4] (1-indexed), and on the difference array this translates to diff[l] += 1 and diff[r + 1] -= 1 (0-indexed). There are many ways to prove this rule holds (prove by AC!).
With this, we only need to apply n range operations on the difference array, each an O(1) change, then restore the array with one O(n) prefix sum pass — completing all the range operations in linear time.
Limitations
The difference array is static: it can only answer "what is the final state after a series of operations" type questions. If you need to solve the problem dynamically — e.g., perform operation 1, inspect the state, then perform operation 2, inspect the state again — the difference array degrades back to O(n²). To handle that, you'll have to reach for a segment tree or a Fenwick tree (binary indexed tree).
Example Problem
(CF 179 Div1 A) You are given an original array of size n, an operation-definition array of size m, and an operation-execution array of size k. An operation definition adds c to every element of the original array in the range [l, r]; an operation execution runs each operation definition in the range [l, r] once. Compute the final array.
Approach
After my simplified restatement of the problem, you should easily see that this problem calls for two layers of difference arrays. First, apply a difference array to the operation executions: apply the changes, then restore, to obtain how many times each operation is executed. Then apply a difference array to the original array, apply each operation the corresponding number of times, and finally restore the array to get the answer. We store all operations in an ops array, use an execs array to record the execution count of the operation at each index, and then for each operation op, on the difference array diff, perform diff[op.l] += op.c * execs and diff[op.r] += op.c * execs.
The Ancestral Rule
The ancestral rule of prefix sums still applies: anything prefix-sum-related must use long long. That means even the difference array uses long long, because it will ultimately be restored via a prefix sum. In this problem, a 32-bit int will overflow and fail on test 14.
Also, the sentinel node at the head is mandatory; the sentinel at the tail can be dropped in this particular problem.
Original Implementation (C++)
AC
#include <cstdio>
#include <iostream>
#include <vector>
int main() {
// freopen("greg.in", "r", stdin);
// freopen("greg.out", "w", stdout);
struct Operation {
int l;
int r;
long long c;
};
int n, m, k;
std::cin >> n >> m >> k;
// * Build diff array for original array
std::vector<long long> vec(n + 2);
for (int i = 1; i <= n; ++i) {
std::cin >> vec[i];
}
std::vector<long long> diff(n + 2);
for (int i = 1; i <= n; ++i) {
diff[i] = vec[i] - vec[i - 1];
}
std::vector<Operation> ops(m);
for (int i = 0; i < m; ++i) {
int l, r, c;
std::cin >> l >> r >> c;
ops[i] = {l, r, c};
}
// * Build diff array for operation executions
std::vector<long long> execs(m + 2); // op idx -> count
for (int i = 0; i < k; ++i) {
int l, r;
std::cin >> l >> r;
execs[l] += 1;
execs[r + 1] -= 1;
}
// Revert exec to get execution times for each operation of index i
for (int i = 1; i <= m; ++i) {
execs[i] += execs[i - 1];
}
// Apply changes
for (int i = 1; i <= m; ++i) {
const auto& op = ops[i - 1]; // since ops is 0-indexed
int op_count = execs[i];
diff[op.l] += op.c * op_count;
diff[op.r + 1] -= op.c * op_count;
}
// Revert diff to get final array
for (int i = 1; i <= n; ++i) {
diff[i] += diff[i - 1];
std::cout << diff[i] << " ";
}
std::cout << "\n";
}