Difference arrays

Why this matters

A common job is to add a number to every value in a range. A shop might add a discount to every day from day 3 to day 9. A game might raise the danger level of every tile in a corridor. A log tool might count one more event in every minute of a time window. Each job touches a range of values, and there may be thousands of jobs over an array of hundreds of thousands of values.

The direct method loops over the range for each job. If a job covers 500 values and you have 2,000 jobs, that is up to 1,000,000 additions. With larger numbers, the total grows quickly. The difference array in this lesson makes each job cost two additions no matter how long the range is. You then make one pass over the array at the end to get the final values.

This lesson assumes you know the basic array loop from the earlier lessons in this module. It does not cover rotating arrays, which the previous lesson covers, or the sliding window techniques earlier in the module. Those techniques answer questions about one window at a time. This one answers many updates before any value is read.

The idea: store the changes, not the values

Start with a small array of six zeros, numbered 0 to 5. Now add 4 to every value from index 1 to index 3. Doing this directly changes three values: index 1 becomes 4, index 2 becomes 4, and index 3 becomes 4.

Look at the array in a different way. The value at index 1 jumps up by 4 compared with index 0. The value at index 2 is the same as index 1, so it does not jump. The value at index 3 is the same as index 2, so it does not jump either. The value at index 4 drops by 4 compared with index 3, which brings it back to 0.

So the whole change can be written as two jumps:

• a jump of +4 at index 1, where the range starts
• a jump of -4 at index 4, the first index after the range

A difference array holds these jumps. The entry at position i stores the value at i minus the value at i - 1, which is the size of the jump at i. Position 0 stores the first value itself, because there is no earlier value to compare with.

Here is the array after the update:

value:  0 4 4 4 0 0
jump:   0 4 0 0 -4 0

The row jump is the difference array. Notice that it is almost all zeros. Only the two boundaries carry anything. This is why an update can be cheap: you only write two entries, however long the range is.

Recovering the values

To read the real values back, run a running total from left to right. The running total starts at 0. At each index, add that index's jump to the total. The total at each index is the value at that index.

Take the jumps from the table: 0, 4, 0, 0, -4, 0.

The running total gives 0 4 4 4 0 0, which matches the direct method. The running total is the same idea as the prefix sums in the earlier lesson on prefix sums and two pointers. The difference is what the array stores. A prefix sum array stores totals, and a difference array stores the changes that a total is built from.

The update rule

To add v to every value from index l to index r, where both ends are included, make two changes:

diff[l] += v
diff[r + 1] -= v

The first line starts the jump at l. The second line cancels it just after r. Position r + 1 is the first index that is no longer in the range. That is why the difference array needs one more entry than the value array. If r is the last index, r + 1 is one past the end of the value array, so the extra entry is what keeps the second line safe.

The difference array in code has n + 1 entries, where n is the number of values. The + 1 is the step that most learners forget, and the Common mistakes section shows what goes wrong without it.

A first program

The next program builds the jump row from one update and then prints both the jumps and the values. Type it exactly as shown.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n = 6;
    vector<long long> diff(n + 1, 0);
 
    // Add 4 to every value from index 1 to index 3.
    diff[1] += 4;
    diff[4] -= 4;
 
    cout << "diff:  ";
    for (long long x : diff) {
        cout << x << ' ';
    }
    cout << '\n';
 
    long long running = 0;
    cout << "value: ";
    for (int i = 0; i < n; i++) {
        running += diff[i];
        cout << running << ' ';
    }
    cout << '\n';
    return 0;
}

Its output is:

diff:  0 4 0 0 -4 0 0 
value: 0 4 4 4 0 0 

The jump row has seven entries because n is 6. The values row has six entries, one for each index. The final entry of the jump row, index 6, is never read in the value loop, but it is in the array, which is why the update diff[r + 1] is safe when r is 5.

The type is long long, a whole-number type that holds larger numbers than int. Totals can grow large when many updates overlap, and a long long makes overflow much less likely. Overflow means a number grows past the largest value its type can hold. For a signed type such as long long, the result is undefined, so the program may print a wrong number with no error message.

Worked example: several updates at once

The next example applies three updates to six values. Each update is a range, a starting index, an ending index, and an amount. The program applies all of them to the difference array first, then makes one running-total pass. It also applies them the slow way, one loop per update, so you can compare the two results.

#include <iostream>
#include <vector>
using namespace std;
 
struct Update {
    int l;
    int r;
    long long v;
};
 
vector<long long> applyWithDiff(int n, const vector<Update>& updates) {
    vector<long long> diff(n + 1, 0);
    for (const Update& u : updates) {
        diff[u.l] += u.v;
        diff[u.r + 1] -= u.v;
    }
    vector<long long> result(n);
    long long running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}
 
vector<long long> applyBrute(int n, const vector<Update>& updates) {
    vector<long long> a(n, 0);
    for (const Update& u : updates) {
        for (int i = u.l; i <= u.r; i++) {
            a[i] += u.v;
        }
    }
    return a;
}
 
void printVec(const vector<long long>& a) {
    for (long long x : a) {
        cout << x << ' ';
    }
    cout << '\n';
}
 
int main() {
    int n = 6;
    vector<Update> updates = {{1, 3, 4}, {0, 1, 2}, {3, 5, -1}};
 
    cout << "difference: ";
    printVec(applyWithDiff(n, updates));
    cout << "brute force: ";
    printVec(applyBrute(n, updates));
    return 0;
}

Its output is:

difference: 2 6 4 3 -1 -1 
brute force: 2 6 4 3 -1 -1 

The three updates are {1, 3, 4}, which adds 4 to indexes 1 to 3, then {0, 1, 2}, which adds 2 to indexes 0 and 1, and {3, 5, -1}, which subtracts 1 from indexes 3 to 5. Each update writes exactly two entries in the difference array, so the three updates write six entries in total. The running total then produces the six values.

Work out the first value by hand to see the structure. Index 0 is touched only by the update {0, 1, 2}, which adds 2 there. So the first value is 2. Index 1 is touched by {1, 3, 4} and by {0, 1, 2}, so it gets 4 + 2 = 6. Index 2 is touched only by {1, 3, 4}, so it is 4. The brute force loop does exactly these additions, which is why the two rows agree.

The struct Update groups the four fields of one job in one value. The braces {1, 3, 4} fill the fields in the order they are written: l is 1, r is 3, and v is 4. Grouping the fields keeps the three jobs in one list, so a function can take them all at once.

A second worked example: counting bookings

The most common use of a difference array is counting. Suppose a room has six time slots, numbered 0 to 5, and three bookings. Each booking covers a range of slots. The question is how many bookings cover each slot. Adding 1 for each booking's range answers the question.

#include <iostream>
#include <vector>
using namespace std;
 
struct Range {
    int l;
    int r;
};
 
int main() {
    int n = 6;
    vector<Range> ranges = {{0, 2}, {1, 4}, {4, 5}};
 
    vector<int> diff(n + 1, 0);
    for (const Range& range : ranges) {
        diff[range.l] += 1;
        diff[range.r + 1] -= 1;
    }
 
    int count = 0;
    for (int i = 0; i < n; i++) {
        count += diff[i];
        cout << "slot " << i << ": " << count << " booking(s)\n";
    }
    return 0;
}

Its output is:

slot 0: 1 booking(s)
slot 1: 2 booking(s)
slot 2: 2 booking(s)
slot 3: 1 booking(s)
slot 4: 2 booking(s)
slot 5: 1 booking(s)

Slot 4 has two bookings because two ranges cover it: {1, 4} still runs at slot 4, and {4, 5} starts there. The difference array needs no special case for this. The booking from slot 1 stops at slot 5, so its cancelling entry sits at position 5, and the running total carries its count through slot 4. The booking that starts at slot 4 adds one more at that position. The running total carries every active count forward, which is the whole point of the method.

A third example: many random updates

The third example checks the method on a larger input. It makes 2,000 random updates on 500 values and compares the difference method with the brute force method. The random numbers come from a simple generator with a fixed starting seed, so every run makes the same updates. A seed is the number the generator starts from, and a fixed seed makes a test repeatable. Real projects use the standard library's random tools for this job, but a fixed generator keeps this example short.

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
 
struct Update {
    int l;
    int r;
    long long v;
};
 
vector<long long> applyWithDiff(int n, const vector<Update>& updates) {
    vector<long long> diff(n + 1, 0);
    for (const Update& u : updates) {
        diff[u.l] += u.v;
        diff[u.r + 1] -= u.v;
    }
    vector<long long> result(n);
    long long running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}
 
vector<long long> applyBrute(int n, const vector<Update>& updates) {
    vector<long long> a(n, 0);
    for (const Update& u : updates) {
        for (int i = u.l; i <= u.r; i++) {
            a[i] += u.v;
        }
    }
    return a;
}
 
int main() {
    // A fixed generator gives the same numbers on every run.
    uint32_t seed = 12345;
    auto nextNumber = [&seed]() {
        seed = seed * 1103515245u + 12345u;
        return (seed >> 16) & 0x7fff;
    };
 
    int n = 500;
    vector<Update> updates;
    for (int i = 0; i < 2000; i++) {
        int a = static_cast<int>(nextNumber() % n);
        int b = static_cast<int>(nextNumber() % n);
        long long v = static_cast<long long>(nextNumber() % 201) - 100;
        updates.push_back({min(a, b), max(a, b), v});
    }
 
    vector<long long> fast = applyWithDiff(n, updates);
    vector<long long> slow = applyBrute(n, updates);
    cout << "2000 updates on 500 slots: " << (fast == slow ? "same" : "MISMATCH") << '\n';
    cout << "first five values:";
    for (int i = 0; i < 5; i++) {
        cout << ' ' << fast[i];
    }
    cout << '\n';
    return 0;
}

Its output is:

2000 updates on 500 slots: same
first five values: -82 -82 -18 13 86

The brute force method does up to 500 additions for each update, so this run does up to 1,000,000 additions. The difference method does two writes per update, so 4,000 writes, and then one pass of 500 steps. The printed result shows both methods agree on every value.

The lambda nextNumber is a small function written inside main. The [&seed] part lets it use and change the variable seed declared above it. The type uint32_t from <cstdint> holds an unsigned 32-bit whole number. Its values wrap around past the largest value, and the generator relies on that. The expression % n keeps each random index inside the array, and % 201 - 100 gives amounts from -100 to 100.

Common mistakes

Leaving out the extra entry

If you make the difference array with n entries instead of n + 1, an update that ends at the last index writes to position n, which does not exist. A plain diff[i] write does not check the index by default, so the program may silently write to memory it does not own. This g++ build can add a check that stops the program with a message instead. The safe habit is to make the array one larger than the value array, and to use .at() while you learn. The .at() function checks the index and throws an error when it is out of range.

The program below makes that exact mistake. It has four values, so the array has four entries, and it tries to write position 4.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n = 4;
    vector<long long> diff(n, 0);
    int l = 1;
    int r = 3;
    long long v = 5;
    diff.at(l) += v;
    cout << "before the bad write" << endl;
    diff.at(r + 1) -= v;
    cout << "after the bad write" << endl;
    return 0;
}

Its output on the g++ 15.2 build used for this lesson is:

before the bad write
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 4) >= this->size() (which is 4)

The line after the bad write never prints, because the error stopped the program first. Read the message as "I tried to use index 4, but the vector has only 4 entries". When you see __n (which is ...) >= this->size(), the index is too big by at least one. Here the cause is the r + 1 index, so the fix is to size the array as n + 1.

Forgetting the cancelling entry

An update needs both lines: diff[l] += v starts the change, and diff[r + 1] -= v stops it. If you leave out the second line, the running total keeps the change for every index from l to the end of the array. The values after r then change by mistake. A quick test is to apply one update to a small array and print the result. If the values after the range are not zero, the stopping line is missing or has the wrong index.

Using the wrong sign

The stopping entry must be subtracted, not added. Writing diff[r + 1] += v gives the change that goes on forever in the other direction. The easiest way to check the signs is the one-update test above: with one update of +4 on indexes 1 to 3, the values must be 0 4 4 4 0 0.

Running the total from the wrong place

The running total must start at 0 and read the jump row from index 0. Starting it at diff[1] or looping only from index 1 skips the first jump and gives every value a wrong offset. Check the first value by hand: it must equal the sum of all updates that cover index 0.

Expecting a single answer to be read in the middle

The method is built for many updates first and then reads. After the running pass, the values are final, and each new update needs a new pass to see the effect. If a program must read values between updates, the method needs a different structure, which the segment trees lesson in this phase covers.

Practice

Exercise 1: five values, three updates

Use six entries for the difference array, which means n = 5 values. Apply these updates in order: add 1 to indexes 0 to 4, add 10 to index 2 only, and subtract 2 from indexes 1 to 3. Write the five final values.

Show the answer

The final values are 1 -1 9 -1 1. Index 2 is the only index that gets the 10, so its value is 1 + 10 - 2 = 9. Indexes 1 and 3 each get the minus 2 from the third update, and index 0 and index 4 get only the first update.

Exercise 2: bookings in eight slots

A meeting room has eight slots, numbered 0 to 7. The bookings cover slots 2 to 5, slots 4 to 7, and slots 0 to 1. Use a difference array with one addition per booking to count the bookings in each slot. Write the eight counts.

Show the answer

The counts are 1 1 1 1 2 2 1 1. Slots 4 and 5 are covered by two bookings, one from 2 to 5 and one from 4 to 7. Every other slot is covered by exactly one booking.

Exercise 3: recover the jumps

The final values of an array are 3 3 1 -1 -1 1. Write the difference array for these values. Use the rule that position 0 holds the first value and every other position holds the value minus the value before it.

Show the answer

The difference array is 3 0 -2 -2 0 2. Position 0 is 3, and position 1 is 3 - 3 = 0. Position 2 is 1 - 3 = -2, position 3 is -1 - 1 = -2, position 4 is -1 - (-1) = 0, and position 5 is 1 - (-1) = 2. Running the total over these jumps gives back 3 3 1 -1 -1 1.

Exercise 4: why n + 1 entries

Explain in two or three sentences why a difference array for n values needs n + 1 entries, not n.

Show the answer

An update that covers the last index n - 1 must cancel itself at position n, which is the first index after the range. Position n does not exist in an array of n entries, so the cancelling write would fall outside the array. The extra entry is never read by the running total, but it is needed so the write is safe.

Summary

• A difference array stores the change at each position, so a range update writes only two entries.
• To add v to indexes l to r, do diff[l] += v and diff[r + 1] -= v.
• A running total over the difference array gives the final values in one pass.
• The array needs n + 1 entries so that the cancelling write at r + 1 stays inside the array.
• The method is best when many updates come before the reads. It does not answer a question between updates.