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. 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.

5. 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.

6. 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
295A · Greg and Array — 1400 difference array twice, once over operations and once over the array
Credits & licenses