Skip to content

Difference Array

In one sentence

To add \(v\) to a whole range, change only two numbers in a helper array. When all updates are done, rebuild the real array once with a prefix sum.

1. What problem does it solve?

Example — CF 816B · Karen and Coffee

There are \(n\) coffee recipes. Recipe \(i\) says the temperature should be between \(l_i\) and \(r_i\) degrees. A temperature is admissible if at least \(k\) recipes recommend it.

Then \(q\) questions follow. Each gives \(a, b\): how many integer temperatures in \([a, b]\) are admissible?

Limits: \(1 \le k \le n \le 2 \cdot 10^5\), \(1 \le q \le 2 \cdot 10^5\), temperatures in \([1, 200000]\).

Input          Output
3 2 4
91 94
92 97
97 99
92 94          3
93 97          3
95 96          0
90 100         4

Step 1: count recipes per temperature. Each recipe says "add \(1\) to every temperature in \([l_i, r_i]\)". Doing that with a loop costs up to \(2 \cdot 10^5\) per recipe, so up to \(4 \cdot 10^{10}\) in total. Too slow.

Step 2: answer the questions. Once we know which temperatures are admissible, "how many admissible in \([a, b]\)" is a prefix sum query.

Step 1 is exactly what a difference array is for: many range additions, then read the result once.

Recount the sample by hand, marking each recipe's range with +1:

temperature 91 92 93 94 95 96 97 98 99
recipe 91 94 +1 +1 +1 +1
recipe 92 97 +1 +1 +1 +1 +1 +1
recipe 97 99 +1 +1 +1
count 1 2 2 2 1 1 2 1 1
admissible (\(\ge 2\)) ✅ ✅ ✅ ✅

So 92 94 → 3, 93 97 → 3 (93, 94, 97), 95 96 → 0, 90 100 → 4.

2. The math

All templates below use a 1-indexed array:

a = [0, ...]

So a[0] is not used.

1.1 The problem prefix sum cannot solve

Prefix sum answers many queries on a fixed array:

query(l, r) -> a[l] + a[l+1] + ... + a[r]

The difference array is the mirror image of that. It handles many range updates on an array, and you only look at the final result once:

update(l, r, v) -> add v to every one of a[l], a[l+1], ..., a[r]

Doing this naively costs \(O(r - l + 1)\) per update, so \(q\) updates cost \(O(nq)\). With \(n, q \le 2\cdot 10^5\) that is \(4\cdot 10^{10}\) operations — far too slow.

The difference array makes each update \(O(1)\), and pays a single \(O(n)\) cost at the very end to read the array back.

prefix sum difference array
fast operation range query range update
slow operation point update reading a value
built once, at the start once, at the end

1.2 Definition

For an array \(a_1, \dots, a_n\), its difference array \(d\) is

\[d_i = a_i - a_{i-1}, \qquad a_0 = 0 .\]

Each entry stores how much the array changed at that position, not the value itself.

i      1   2   3   4   5
a      3   3   7   7   2
d      3   0   4   0  -5
       ^       ^       ^
       |       |       +-- dropped by 5
       |       +---------- jumped up by 4
       +------------------ jumped up by 3 (from the imaginary a[0] = 0)

1.3 The inverse: prefix sum

The two operations are inverses of each other:

\[ \begin{aligned} \sum_{j=1}^{i} d_j &= (a_1 - a_0) + (a_2 - a_1) + \dots + (a_i - a_{i-1}) \\ &= a_i - a_0 \\ &= a_i . \end{aligned} \]

Everything in the middle cancels — this is a telescoping sum. So

\[\operatorname{prefix\_sum}(\operatorname{difference}(a)) = a .\]

Check it on the table above: \(3,\ 3+0,\ 3+0+4,\ 3+0+4+0,\ 3+0+4+0-5 = 3, 3, 7, 7, 2\). ✓

This is the single fact the whole technique rests on. The difference array is a compressed description of \(a\); a prefix sum decompresses it.

1.4 Why a range update touches only two positions

Now add \(v\) to every element in \([l, r]\) and ask which \(d_i = a_i - a_{i-1}\) change.

There are three kinds of index \(i\):

  • Both \(a_i\) and \(a_{i-1}\) are inside \([l, r]\) — both gained \(v\), so the difference \(a_i - a_{i-1}\) is unchanged.
  • Both are outside — neither gained anything, unchanged.
  • Exactly one is inside — the difference changes.

Only two indices have one endpoint inside and one outside:

\[ \begin{aligned} i = l:\quad & a_l \text{ gained } v,\ a_{l-1} \text{ did not} &&\Rightarrow d_l \mathrel{+}= v \\ i = r+1:\quad & a_{r+1} \text{ did not gain},\ a_r \text{ did} &&\Rightarrow d_{r+1} \mathrel{-}= v \end{aligned} \]

Picture it as a step function: adding \(v\) on \([l, r]\) builds a plateau. A plateau has exactly one rising edge (at \(l\)) and one falling edge (just after \(r\)). The difference array is the list of edges, so a plateau costs two entries — no matter how wide it is.

add 5 to [2, 4]:

           +5  +5  +5
        .   ___________
        |  |           |
   -----+--+           +--------
   1    2  3   4   5   6
        ^               ^
      d[2] += 5      d[5] -= 5

That is the entire trick. An update of any width is two array writes.

1.5 Why r + 1, and why the array has size n + 2

The falling edge lives at index \(r+1\), so when \(r = n\) you write to d[n + 1]. That entry is never read back (the recovery loop stops at \(n\)), but it must exist or Python raises IndexError. Since we are also 1-indexed, allocate

d = [0] * (n + 2)

Off-by-one at exactly this spot is the most common bug in difference-array code.

Part 2 — Template

class DiffArray:
    def __init__(self, a):
        # a is 1-indexed: a = [0, a1, a2, ..., an]
        n = len(a) - 1
        self.n = n
        self.d = [0] * (n + 2)

        for i in range(1, n + 1):
            self.d[i] = a[i] - a[i - 1]

    def update(self, l, r, v):
        # add v to a[l], a[l+1], ..., a[r]
        self.d[l] += v
        self.d[r + 1] -= v

    def build(self):
        # recover the final array, 1-indexed
        a = [0] * (self.n + 1)
        for i in range(1, self.n + 1):
            a[i] = a[i - 1] + self.d[i]
        return a

Usage

a = [0, 3, 3, 7, 7, 2]

df = DiffArray(a)
df.update(2, 4, 5)     # a becomes [_, 3, 8, 12, 12, 2]
df.update(1, 5, -1)    # a becomes [_, 2, 7, 11, 11, 1]

print(df.build())      # [0, 2, 7, 11, 11, 1]

Rules of use

  1. All updates first, build() last. Never call update after you have started relying on build()'s output — the whole point is that intermediate values do not exist.
  2. If the starting array is all zeros (very common), skip the constructor loop: the difference array of an all-zero array is all zeros.
  3. Everything works with negative \(v\), with overlapping ranges, and in any order. The updates simply add up, because both difference and prefix_sum are linear.

Complexity

naive difference array
one update \(O(n)\) \(O(1)\)
\(q\) updates + one read-out \(O(nq)\) \(O(n + q)\)

3. Worked solution — Karen and Coffee

  1. Use a DiffArray over temperatures \(1..200000\), starting from all zeros. Each recipe is one update(l, r, 1).
  2. build() gives cnt[t], the number of recipes that recommend temperature \(t\).
  3. Make a 0/1 array good[t] = 1 if cnt[t] >= k.
  4. Use a PrefixSum over good. Each question is query(a, b).
import sys

input = sys.stdin.readline

MAXT = 200000


class DiffArray:
    def __init__(self, a):
        # a is 1-indexed: a = [0, a1, a2, ..., an]
        n = len(a) - 1
        self.n = n
        self.d = [0] * (n + 2)

        for i in range(1, n + 1):
            self.d[i] = a[i] - a[i - 1]

    def update(self, l, r, v):
        # add v to a[l], a[l+1], ..., a[r]
        self.d[l] += v
        self.d[r + 1] -= v

    def build(self):
        # recover the final array, 1-indexed
        a = [0] * (self.n + 1)
        for i in range(1, self.n + 1):
            a[i] = a[i - 1] + self.d[i]
        return a


class PrefixSum:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        for i in range(1, n):
            self.pre[i] = self.pre[i - 1] + a[i]

    def query(self, l, r):
        return self.pre[r] - self.pre[l - 1]


def solve():
    n, k, q = map(int, input().split())

    df = DiffArray([0] * (MAXT + 1))
    for _ in range(n):
        l, r = map(int, input().split())
        df.update(l, r, 1)

    cnt = df.build()
    good = [0] + [1 if cnt[t] >= k else 0 for t in range(1, MAXT + 1)]

    ps = PrefixSum(good)

    for _ in range(q):
        a, b = map(int, input().split())
        print(ps.query(a, b))


solve()

Here is the difference array for the sample, showing only temperatures \(91..100\):

\(t\) 91 92 93 94 95 96 97 98 99 100
update(91, 94, 1) +1 −1
update(92, 97, 1) +1 −1
update(97, 99, 1) +1 −1
d[t] 1 1 0 0 −1 0 1 −1 0 −1
cnt[t] = running sum 1 2 2 2 1 1 2 1 1 0

Three recipes touched only six cells of d, no matter how wide the ranges were.

Cost: \(O(n)\) updates at \(O(1)\) each, one \(O(T)\) build, one \(O(T)\) prefix build, then \(O(1)\) per question. That is \(O(n + q + T)\) with \(T = 200000\).

4. Lesson of 4 and 11 Oct — Robert Hood and Mrs Hood

2014D · Robert Hood and Mrs Hood (12 · F, rating 1400)

Days are numbered \(1..n\). There are \(k\) jobs, and job \(i\) covers the days \(l_i..r_i\). A visit lasts \(d\) days in a row and must fit inside \(1..n\). Robin's brother wants his visit to overlap as many jobs as possible, his mother as few as possible. Print the two start days, the earliest one in case of a tie.

The problem never says "add to a range", so the first step is to find the range yourself.

Look at one job. A visit that starts on day \(s\) covers \([s,\ s + d - 1]\). It overlaps the job \([l, r]\) when it starts no later than \(r\) and ends no earlier than \(l\):

\[ s \le r \quad\text{and}\quad s + d - 1 \ge l \iff l - d + 1 \le s \le r . \]

So one job adds 1 to every start day in \([\max(1,\ l - d + 1),\ r]\). That is a range update, and after all jobs we only need to read the values once: exactly the job of a difference array.

The slow version first. For every job, loop over its start days and add 1. That is \(O(n \cdot k)\), far too slow for \(n, k \le 10^5\), but it makes clear what the array means. The difference array replaces that inner loop by two assignments.

def solve():
    n, d, k = map(int, input().split())

    diff = [0] * (n + 2)
    for _ in range(k):
        l, r = map(int, input().split())
        left = max(1, l - d + 1)
        diff[left] += 1
        diff[r + 1] -= 1

    # a[s] = number of jobs a visit starting on day s overlaps
    a = [0] * (n + 1)
    for s in range(1, n + 1):
        a[s] = a[s - 1] + diff[s]

    robin = mom = 1
    for s in range(2, n - d + 2):        # start days 1 .. n - d + 1
        if a[s] > a[robin]:
            robin = s
        if a[s] < a[mom]:
            mom = s

    print(robin, mom)

Three things went wrong on the way, and all three are worth remembering:

  • diff[r + 1] -= 1, not diff[r]. Go back to the definition diff[i] = a[i] - a[i - 1]. Adding 1 to \(a_l..a_r\) changes two differences: diff[l] (because \(a_l\) grew and \(a_{l-1}\) did not) and diff[r + 1] (because \(a_{r+1}\) did not grow and \(a_r\) did). See §1.5.
  • diff is not the answer. a[5] = 4 means "a visit starting on day 5 overlaps 4 jobs". diff[5] only says how a[5] differs from a[4]. You must run the prefix sum before reading anything.
  • The last start day is \(n - d + 1\), not \(n\) and not \(n - d\): the visit \([s,\ s + d - 1]\) has to end by day \(n\). You found this one yourself.

And read the output line again before submitting: the answer is the two days, not the two counts. With strict > and < the earliest day wins ties.

5. Extension — 2D difference array

To add \(v\) to every cell of the rectangle with rows \(x_1..x_2\) and columns \(y_1..y_2\), change four corners:

\[ \begin{aligned} D_{x_1,\,y_1} &\mathrel{+}= v, &\qquad D_{x_1,\,y_2+1} &\mathrel{-}= v, \\ D_{x_2+1,\,y_1} &\mathrel{-}= v, &\qquad D_{x_2+1,\,y_2+1} &\mathrel{+}= v. \end{aligned} \]

After all updates, one 2D prefix sum over \(D\) gives the final grid.

Why four corners: the \(+v\) at \((x_1, y_1)\) spreads to everything below and to the right of it. The two \(-v\) cancel it past the right edge and past the bottom edge. The bottom-right region got cancelled twice, so the last \(+v\) puts it back.

add v to rows 2..3, cols 2..3 of a 4x4 grid

D (the four corners)        after 2D prefix sum
.   .   .   .   .           0   0   0   0
.  +v   .  -v   .           0   v   v   0
.   .   .   .   .           0   v   v   0
.  -v   .  +v   .           0   0   0   0

The 2D version is not part of our templates yet. Use it once the 1D version feels easy.

6. Common mistakes

d too short

update(l, n, v) writes d[n + 1]. The template allocates n + 2 for this reason. If you write your own array, allocate the same.

Reading values in the middle of updates

d is not the array. The real values only exist after build(). If the problem mixes updates and queries, a difference array is the wrong tool; that needs a Fenwick tree or segment tree.

Temperatures or coordinates are huge

If ranges go up to \(10^9\) you cannot allocate d of that size. Sort the endpoints and use events (+v at \(l\), -v at \(r+1\)) instead. This is the idea behind 1000C · Covered Points Count.

Forgetting the second prefix sum

Karen and Coffee needs two passes: difference array → counts, then prefix sum → range answers. Mixing them up is the classic WA.

7. Practice

Problem Set Rating Idea
816B · Karen and Coffee 7-Intervals · A, 10-prefixsum · I 1400 difference array + prefix sum (this page)
276C · Little Girl and Maximum Sum 10-prefixsum · F/G 1500 count how often each index is queried, then sort
1132C · Painting the Fence 7-Intervals · C 1700 coverage counts + prefix counts of "covered exactly once"
1000C · Covered Points Count 7-Intervals · B 1700 difference events on sorted coordinates
2014D · Robert Hood and Mrs Hood 12 · F 1400 find the range of start days each job touches (§4)
295A · Greg and Array — 1400 difference array twice, once over operations and once over the array
Credits & licenses