Difference arrays

A difference array applies many changes of the form "add x to every element from l to r" with two small writes each, and one running total at the end gives the final array. If the values must be read between the changes, use a Fenwick tree instead.

Explanation

An array has 5 elements, all 0, and 3 must be added to elements 2 to 4. In a second row, write +3 under element 2 and −3 under element 5, then take the running total of that row (each cell plus everything before it) from left to right: 0, 3, 3, 3, 0. The −3 is what stops the change: without it, the running total would carry the 3 on into element 5.

Fig. 1. +3 under element 2 and −3 under element 5 add 3 to elements 2 to 4.

Real problems have many changes, and they overlap. A bike shop rents out bikes for 8 days. There are four rentals: 3 bikes on days 2 to 5, 2 bikes on days 4 to 8, 1 bike on days 1 to 3, and 4 bikes on days 6 to 7. How many bikes are out on each day? Writing each rental into every day it covers takes 4 + 5 + 3 + 2 = 14 additions here. With 10^6 days and 10^6 rentals that can be 10^{12} additions, far too slow.

A running total carries each number forward to every later day, so each rental needs only two marks: its number on its first day, and minus its number on the first day it no longer covers. Rental 1 gets +3 on day 2 and −3 on day 6.

This row of marks is the difference array. Using it takes two steps: mark each change with +x at l and −x at r + 1, then build the final values with one running total.

Before any rental is marked, every mark is 0.

Rental 1 adds 3 at day 2 and takes 3 away at day 6.

Rental 2 adds 2 at day 4 and takes 2 away at cell 9, past the last day.

Rental 3 adds 1 at day 1 and takes 1 away at day 4; the mark on day 4 is now 2 − 1 = 1.

Rental 4 adds 4 at day 6 and takes 4 away at day 8; the mark on day 6 is now −3 + 4 = 1.

Day 1: 0 + 1 = 1.

Day 2: 1 + 3 = 4.

Day 3: 4 + 0 = 4.

Day 4: 4 + 1 = 5.

Day 5: 5 + 0 = 5.

Day 6: 5 + 1 = 6.

Day 7: 6 + 0 = 6.

Day 8: 6 − 4 = 2.

1/13

Fig. 2. Step through the marks and the running total with the buttons or the arrow keys. Blue +x marks add a rental, red −x marks take it away, and the outlined cells are the ones being added.

The build gave every day's count at once, 1, 4, 4, 5, 5, 6, 6, 2, with 8 marks and one pass over the days instead of 14 additions.

Each mark is a day's count minus the count of the day before: day 6 has 6 bikes, day 5 has 5, and the mark on day 6 is 1. So if the array doesn't start at zeros, first read it into marks, each one the element minus the element before it. The array 4, 4, 7, 7, 7, 2 gives marks 4, 0, 3, 0, 0, −5. Adding 1 to elements 2 to 3 makes them 4, 1, 3, −1, 0, −5, and the running total gives 4, 5, 8, 7, 7, 2.

Fig. 3. The change touches only cells 2 and 4; every other mark keeps the difference it started with.

Reach for a difference array when a problem has many changes to ranges of consecutive elements, and the values are read only after all of them.

In C++

The elements are a[1] to a[n], with a[0] = 0. Rental 1 above becomes d[2] += 3 and d[6] -= 3.

vector<long long> d(n + 2, 0);   // n + 2 cells: the mark at r + 1 can land at n + 1;
                                 // with n + 1 cells it writes past the end

// read
for (int i = 1; i <= n; i++)
    d[i] = a[i] - a[i - 1];      // differences of the starting array (all 0 if it starts at zeros)

// mark: add x to elements l to r
d[l] += x;
d[r + 1] -= x;

// build
for (int i = 1; i <= n; i++)
    a[i] = a[i - 1] + d[i];

The range must have l ≤ r. If the input may give the ends in either order, swap them first: with l = 4, r = 2 the marks would subtract 1 from element 3.

Each change takes $O(1)$ and the build takes $O(n)$, so k changes take O(n + k) time and $O(n)$ memory.

Cover counts and the busiest point

When every change adds 1, or the size of a booking, the built values count what covers each element, and the largest one is the busiest element. On the rentals, the largest value is 6 bikes, on days 6 and 7. Keeping the maximum while building gives it.

// mark: each interval adds x (x = 1 to count intervals)
for (int j = 0; j < k; j++) {
    int l, r;
    long long x;
    cin >> l >> r >> x;
    d[l] += x;
    d[r + 1] -= x;
}

// build, keeping the largest value
long long best = 0;
for (int i = 1; i <= n; i++) {
    a[i] = a[i - 1] + d[i];
    best = max(best, a[i]);
}

If an interval is given as [l, r), so that it doesn't cover r, the −x mark goes at r. If times start at 0, add 1 to every time. To count the elements covered at least c times, replace best = max(best, a[i]) with if (a[i] >= c) cnt++.

Common mistakes

• Forgetting the −x mark keeps a change in the total forever. With only first-day marks on the rentals, the totals are 1, 4, 4, 6, 6, 10, 10, 10, so day 6 shows 10 instead of 6. Every change needs both marks.

Similar techniques

Prefix sums answer range-sum questions about an array that doesn't change.

2D prefix sums apply changes to rectangles of a table with four marks each.

When the questions ask for range sums or minimums between range changes, use a segment tree with lazy propagation. For questions about one element, the Fenwick tree from the question above is enough.

A sweep line uses the same marks when coordinates reach 10^9 and no array fits: it sorts the $2k$ marks in O(k \log k) and walks them in order.

Practice