Difference Arrays

Quick Revisit
USE WHEN: Multiple range-update queries (add v to all elements in [l,r]) on a static array
INVARIANT: d[l] += v and d[r+1] -= v encodes a range update; prefix sum of d recovers the array
TIME: O(1) per update, O(n) to reconstruct | SPACE: O(n)
CLASSIC BUG: Off-by-one on the cancellation index—d[r+1] not d[r] (and check r+1 is in bounds)
PRACTICE: Practice Ladder

Difficulty: Beginner | CF Rating: 1200–1500 | Prerequisites: Prefix Sums, Arrays

Intuition
C++ STL Reference
Implementation
Operations Reference
Problem Patterns & Tricks
Contest Cheat Sheet
Gotchas & Debugging
Self-Test
Practice Problems
Further Reading

Intuition

You are given an array of $n$ integers and $Q$ range-update queries of the form "add $v$ to every element in $[l, r]$ ."

text

a = [2, 3, 1, 5, 4, 2]        (0-indexed, n = 6)

Query: add +3 to indices [1, 4]

Naive approach -- touch every element in the range:

  a[1] += 3  ->  [2, 6, 1, 5, 4, 2]
  a[2] += 3  ->  [2, 6, 4, 5, 4, 2]
  a[3] += 3  ->  [2, 6, 4, 8, 4, 2]
  a[4] += 3  ->  [2, 6, 4, 8, 7, 2]

Each query touches up to $n$ elements. With $Q = 100 000$ queries on $n = 200 000$ elements, the naive approach performs $O (n \cdot Q) = 2 \times 10^{10}$ operations—far too slow for a 2-second time limit.

Instead of updating every element in the range, record only the change at the start (+v) and the cancellation at end+1 (-v), then run a prefix sum to reconstruct the final array.

The core idea is dual to prefix sums: prefix sums compress queries on a static range into $O (1)$ ; difference arrays compress updates on a range into $O (1)$ .

Visual Walkthrough

Start with the original array and build its difference array $d$ :

text

Index:       0    1    2    3    4    5
a       = [  2,   3,   1,   5,   4,   2 ]
d       = [  2,   1,  -2,   4,  -1,  -2 ]
            ^    ^    ^    ^    ^    ^
           a[0] a[1]  a[2] a[3] a[4] a[5]
                -a[0] -a[1]-a[2]-a[3]-a[4]

Step 1—Apply "add +3 to [1, 4]" on the diff array:

text

d[1] += 3,  d[5] -= 3     (end+1 = 5)

d       = [  2,   4,  -2,   4,  -1,  -5 ]
                  ^                    ^
                 +3                   -3

Step 2—Apply "add -1 to [0, 2]" on the diff array:

text

d[0] -= 1,  d[3] += 1     (end+1 = 3)

d       = [  1,   4,  -2,   5,  -1,  -5 ]
             ^              ^
            -1             +1

Step 3—Apply "add +2 to [3, 5]" on the diff array:

text

d[3] += 2,  d[6] -= 2     (end+1 = 6, out of bounds -- ignore)

d       = [  1,   4,  -2,   7,  -1,  -5 ]
                             ^
                            +2

Step 4—Reconstruct the final array via prefix sum of d:

text

a'[0] = 1
a'[1] = 1 + 4  = 5
a'[2] = 5 - 2  = 3
a'[3] = 3 + 7  = 10
a'[4] = 10 - 1 = 9
a'[5] = 9 - 5  = 4

Final a' = [ 1, 5, 3, 10, 9, 4 ]

Verify by applying all three queries naively on the original array:

text

Start:          [2, 3, 1, 5, 4, 2]
+3 on [1,4]:    [2, 6, 4, 8, 7, 2]
-1 on [0,2]:    [1, 5, 3, 8, 7, 2]
+2 on [3,5]:    [1, 5, 3, 10, 9, 4]   OK matches

The Invariant

text

+------------------------------------------------------------------+
|  d[i] = a[i] - a[i-1]   (with a[-1] = 0)                       |
|                                                                  |
|  A range update [l, r] += v  changes ONLY d[l] and d[r+1]:      |
|      d[l]   += v                                                 |
|      d[r+1] -= v   (if r+1 < n)                                 |
|                                                                  |
|  Reconstruction:  a[i] = prefix_sum(d, 0..i)                    |
+------------------------------------------------------------------+

What the Code Won't Teach You

Difference arrays are the "batch offline" pattern incarnate. The template makes the mechanics obvious—d[l] += v; d[r+1] -= v;—but the deeper lesson is strategic: you are trading interactivity for speed. Whenever all modifications arrive before any reads, ask whether you can defer the work and reconstruct at the end. Difference arrays, offline BIT updates, and lazy segment-tree pushdowns all share this philosophy.

The real mental model is start/stop events on a number line. Each range update [l, r] += v is just two events: "start adding v at position l" and "stop at position r+1." Once you internalize this, difference arrays stop being an isolated technique and become a special case of the sweep-line paradigm—one that generalizes to 2D, tree paths, and time-based processing.

text

  EVENT VIEW OF DIFFERENCE ARRAYS
  ================================

  Range update: add +5 to [2, 6]

  Position:  0   1   2   3   4   5   6   7   8
             .   .   ▲   .   .   .   .   ▼   .
                    +5                   -5
                  (start)              (stop)

  Prefix-sum sweep accumulates events left to right:

  Value:     0   0   5   5   5   5   5   0   0
                     <-── effect zone ──->

Know the decision boundary. The hardest judgment call is not how to use a difference array but whether to use one at all:

text

  WHICH RANGE-UPDATE TOOL DO I NEED?
  ===================================

  All updates arrive before any queries?
       │
       ├── YES ──->  Difference Array         O(n + Q)
       │
       └── NO ──->  Interleaved updates & queries?
                     │
                     ├── Point queries only ──->  BIT on diff array  O(Q log n)
                     │
                     └── Range queries too  ──->  Segment tree + lazy O(Q log n)

The decision tree above does the heavy lifting; here is the vocabulary that signals "difference array" in a problem statement.

When to Reach for This

Trigger phrases in problem statements:

"Apply Q range additions/increments then answer queries on the final array."
"Increase all elements between l and r by v"—offline, no intermediate reads.
"How many intervals cover each point?"—classic sweep / difference array.

Good fit:

All updates arrive before any queries—you can batch everything offline.
Updates are additive range operations; answers are point reads.
The problem reduces to counting overlapping intervals (classic sweep variant).

Bad fit—reach for something else:

Interleaved updates and queries → segment tree with lazy propagation.
Range set (assign) rather than range add → segment tree or sqrt decomposition.
Range sum queries needed after each update → BIT / Fenwick tree.

C++ STL Reference

The <numeric> header maps directly onto the difference-array/prefix-sum duality—one function for each direction:

Function	Signature (simplified)	What it does
`std::adjacent_difference`	`adjacent_difference(first, last, d_first)`	Builds the difference array: `d[i] = a[i] - a[i-1]`
`std::partial_sum`	`partial_sum(first, last, d_first)`	Reconstructs from differences: `a[i] = d[0] + ... + d[i]`
`std::inclusive_scan`	`inclusive_scan(first, last, d_first, op)`	Parallel-friendly generalized prefix sum (C++17)

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {2, 3, 1, 5, 4, 2};
    vector<int> d(a.size());

    // Build difference array
    adjacent_difference(a.begin(), a.end(), d.begin());
    // d = {2, 1, -2, 4, -1, -2}

    // Reconstruct original from differences
    vector<int> reconstructed(d.size());
    partial_sum(d.begin(), d.end(), reconstructed.begin());
    // reconstructed = {2, 3, 1, 5, 4, 2}

    assert(a == reconstructed);
}

Contest note: You rarely call these STL functions directly. The two-line inline version—d[l] += v; d[r+1] -= v; then partial_sum—is faster to type and easier to debug.

Implementation

Contest Template (1D)

Copy-paste-ready. Handles 0-indexed arrays with $Q$ offline range-add queries.

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    // d[i] = a[i] - a[i-1], with a[-1] = 0
    vector<long long> d(n + 1, 0);
    for (int i = 0; i < n; i++)
        d[i] = a[i] - (i ? a[i - 1] : 0);

    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;  // 0-indexed, inclusive [l, r]
        d[l] += v;
        if (r + 1 <= n - 1) d[r + 1] -= v;
    }

    // Reconstruct
    for (int i = 0; i < n; i++) {
        a[i] = d[i] + (i ? a[i - 1] : 0);
        cout << a[i] << " \n"[i == n - 1];
    }
}

Explained Version (1D)

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    // --- BUILD DIFFERENCE ARRAY ---
    // We use size n+1 so that d[r+1] never goes out of bounds
    // when r = n-1 (we just write to d[n] which acts as a sentinel).
    vector<long long> d(n + 1, 0);
    d[0] = a[0];
    for (int i = 1; i < n; i++)
        d[i] = a[i] - a[i - 1];

    // --- PROCESS RANGE-ADD QUERIES ---
    // Each query "add v to [l, r]" becomes two point updates on d.
    //   d[l] += v    -- the increase starts at index l
    //   d[r+1] -= v  -- the increase stops after index r
    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;
        d[r + 1] -= v;  // safe because d has size n+1
    }

    // --- RECONSTRUCT via prefix sum ---
    // a[i] = d[0] + d[1] + ... + d[i]
    a[0] = d[0];
    for (int i = 1; i < n; i++)
        a[i] = a[i - 1] + d[i];

    for (int i = 0; i < n; i++)
        cout << a[i] << " \n"[i == n - 1];
}

2D Difference Array

For a 2D grid where each query adds $v$ to a sub-rectangle $[r_{1}, r_{2}] \times [c_{1}, c_{2}]$ , we use four point updates per query (inclusion-exclusion on the 2D prefix sum):

text

d[r1][c1]     += v
d[r1][c2+1]   -= v
d[r2+1][c1]   -= v
d[r2+1][c2+1] += v

Reconstruct by running 2D prefix sums (row-wise then column-wise).

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C, q;
    cin >> R >> C >> q;

    // Original grid
    vector<vector<long long>> a(R, vector<long long>(C));
    for (auto& row : a)
        for (auto& x : row)
            cin >> x;

    // 2D difference array with sentinel borders
    vector<vector<long long>> d(R + 1, vector<long long>(C + 1, 0));

    // Build 2D diff from the original grid
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            d[i][j] += a[i][j];
            if (i + 1 <= R) d[i + 1][j] -= a[i][j];
            if (j + 1 <= C) d[i][j + 1] -= a[i][j];
            if (i + 1 <= R && j + 1 <= C) d[i + 1][j + 1] += a[i][j];
        }

    // Process rectangle-add queries
    while (q--) {
        int r1, c1, r2, c2;
        long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;  // 0-indexed inclusive
        d[r1][c1] += v;
        d[r2 + 1][c1] -= v;
        d[r1][c2 + 1] -= v;
        d[r2 + 1][c2 + 1] += v;
    }

    // Reconstruct via 2D prefix sum
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (i > 0) d[i][j] += d[i - 1][j];
            if (j > 0) d[i][j] += d[i][j - 1];
            if (i > 0 && j > 0) d[i][j] -= d[i - 1][j - 1];
        }

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cout << d[i][j] << " \n"[j == C - 1];
}

Operations Reference

Operation	Naive	Difference Array
Build diff array from $a$	--	$O (n)$
Single range update $[l, r] + = v$	$O (n)$	$O (1)$
$Q$ range updates (batch)	$O (n \cdot Q)$	$O (Q)$
Reconstruct $a$ from diff	--	$O (n)$
Total: $Q$ updates then read all	$O (n \cdot Q)$	$O (n + Q)$
Point query (single element, no rebuild)	$O (1)$	$O (n)$ per query*
2D rectangle update	$O (R \cdot C)$	$O (1)$
2D reconstruction	--	$O (R \cdot C)$
Space	$O (n)$	$O (n)$ (or $O (n + 1)$ with sentinel)

* If you need interleaved point queries and range updates, pair the difference array with a BIT/Fenwick tree to get $O (\log n)$ per operation.

Problem Patterns & Tricks

Offline Range Increment Queries

The bread-and-butter usage. All $Q$ "add $v$ to $[l, r]$ " queries arrive before any reads. Process all updates in $O (Q)$ , reconstruct once in $O (n)$ .

cpp

// After all updates:
partial_sum(d.begin(), d.end(), a.begin());

2D Difference Arrays for Rectangle Updates

Grid problems where you stamp a value onto axis-aligned rectangles (e.g., "paint a sub-matrix"). Use the 4-corner inclusion-exclusion update shown in the implementation section. Common in image-processing-style problems.

Tip: If the grid is sparse but coordinates are large, compress coordinates first, then apply the 2D difference array on the compressed grid.

Difference Array + Sorting for Interval Scheduling

Given $n$ intervals $[l_{i}, r_{i}]$ , find the maximum number of overlapping intervals at any point:

cpp

vector<int> d(max_coord + 2, 0);
for (auto& [l, r] : intervals) {
    d[l] += 1;
    d[r + 1] -= 1;
}
int max_overlap = 0, cur = 0;
for (int i = 0; i <= max_coord; i++) {
    cur += d[i];
    max_overlap = max(max_overlap, cur);
}

This is the sweep-line technique—and a difference array is the sweep line when all events are purely additive.

Prefix XOR Difference

Replace addition with XOR. The "difference" is d[i] = a[i] ^ a[i-1], and reconstruction uses prefix XOR. Useful when queries flip (toggle) ranges.

cpp

d[l] ^= v;
if (r + 1 < n) d[r + 1] ^= v;
// Reconstruct: a[i] = d[0] ^ d[1] ^ ... ^ d[i]

Difference on Trees (Euler Tour / DFS Order)

To add $v$ to every node on the path from $u$ to $v$ in a tree, use the Euler tour to flatten the tree into an array, then apply difference-array updates on the flattened array. Combined with LCA:

text

d[u] += v;  d[v] += v;  d[lca(u,v)] -= v;  d[parent[lca(u,v)]] -= v;

Then a DFS aggregation (bottom-up sum) reconstructs the node values.

Polynomial / Higher-Order Differences

To add an arithmetic progression $v, v + k, v + 2 k, \dots$ to $[l, r]$ , layer a second-order difference array: d1 accumulates the running value, and d2 drives the per-step increment of d1:

cpp

// Add v, v+k, v+2k, ... to [l, r]
d1[l] += v;
d1[r + 1] -= v + (long long)(r - l) * k;
d2[l] += k;
d2[r + 1] -= k;
// Reconstruct: prefix-sum d2 into d1, then prefix-sum d1 into a

Difference Array on Sorted Events

When coordinates span a huge range but the number of events is small, skip the dense array and use a map<int,long long> as a sparse difference array—iterate its keys in order to sweep:

cpp

map<int, long long> d;
for (auto& [l, r, v] : queries) {
    d[l] += v;
    d[r + 1] -= v;
}
long long cur = 0;
for (auto& [pos, delta] : d) {
    cur += delta;
    // cur is the value at position pos
}

Contest Cheat Sheet

text

DIFFERENCE ARRAYS -- QUICK REFERENCE
=====================================

BUILD:   d[0] = a[0];
         for i in [1, n): d[i] = a[i] - a[i-1];

UPDATE:  [l, r] += v  =>  d[l] += v;  d[r+1] -= v;

REBUILD: for i in [1, n): d[i] += d[i-1];
         (d is now the updated a)

2D UPDATE (rectangle [r1,c1]->[r2,c2] += v):
         d[r1][c1]     += v;
         d[r1][c2+1]   -= v;
         d[r2+1][c1]   -= v;
         d[r2+1][c2+1] += v;

2D REBUILD:
         row-wise partial_sum, then column-wise partial_sum.

XOR VARIANT:
         d[l] ^= v;  d[r+1] ^= v;
         Reconstruct with prefix XOR.

SPARSE (big coords):
         map<int,ll> d;  d[l] += v;  d[r+1] -= v;
         Iterate in key order, accumulate.

COMPLEXITY:
         Q updates + 1 rebuild = O(n + Q)

Rating Progression

CF 1200: Batch range increments, output the final array—one direct application of d[l] += v; d[r+1] -= v;.
CF 1500: Nested difference arrays (operations on operations); combine with greedy sorting for optimal interval assignment.
CF 1800: 2D difference arrays for rectangle updates; difference arrays stacked on segment trees for persistent range updates.
CF 2100: Higher-order difference arrays for polynomial range updates; difference constraints embedded in optimization problems.

Before You Code

[ ] Confirmed the problem applies all updates before any queries (offline)—otherwise need a BIT or segment tree.
[ ] Checked the r+1 cancellation index: does it stay within bounds, or do I need to allocate n+1 slots?
[ ] Verified whether the problem uses 0-indexed or 1-indexed ranges and adjusted d[l] and d[r+1] accordingly.
[ ] For 2D difference arrays, wrote out the four-corner update formula and verified signs with a small example.
[ ] Ensured the final prefix sum reconstruction uses long long if accumulated values can overflow 32-bit integers.

Gotchas & Debugging

Off-by-one on the right boundary. The cancellation goes at $r + 1$ , not $r$ . If $r$ is the last valid index ( $n - 1$ ), then $r + 1 = n$ —make sure your diff array has size $n + 1$ (or guard the write).
1-indexed vs 0-indexed. Many CF problems use 1-indexed input. If your diff array is 0-indexed, subtract 1 from $l$ and $r$ immediately after reading. Pick one convention and stick with it throughout the contest.
Integer overflow. Each diff element can be as large as the sum of all $v$ values. Use long long whenever $n \cdot v_{max} > 2 \times 10^{9}$ .
Forgetting to initialize from the original array. If the array starts non-zero, you must build the diff array from $a$ before processing queries. A common bug is starting with d all-zero and losing the initial values.
Multiple reconstructions. The prefix-sum step overwrites $d$ in place—afterward, $d$ holds the values of $a$ , not the differences. If you need to apply more updates later, rebuild the diff array from scratch or keep a separate copy before reconstructing.
2D boundary conditions. In the 2D case, the sentinel row and column (index $R$ and $C$ ) must exist. Allocate the grid as $(R + 1) \times (C + 1)$ .
Negative values. Difference arrays work with any ring (integers, modular arithmetic, XOR). Make sure your reconstruction uses the matching inverse operation.
Confusing difference arrays with Fenwick trees. A difference array is a batch tool, not an online data structure. If the problem interleaves updates and queries, you need a Fenwick tree (BIT) over the difference array, or a segment tree with lazy propagation.

Mental Traps

Trap 1: "This is just prefix sums in reverse." Difference arrays and prefix sums are mathematical inverses, but they solve opposite problems. Prefix sums enable fast range queries on a static array. Difference arrays enable fast range updates to produce a final array. Confusing the direction leads to applying the wrong tool entirely.

text

  PREFIX SUM vs DIFFERENCE ARRAY -- OPPOSITE DIRECTIONS
  =====================================================

  ┌─────────────────┐         ┌─────────────────┐
  │   PREFIX SUM     │         │ DIFFERENCE ARRAY │
  │                  │         │                  │
  │  Static array    │         │  Many updates    │
  │  + many range    │  DUAL   │  + read final    │
  │    QUERIES       │ ◄─────► │    VALUES        │
  │                  │         │                  │
  │  Build: O(n)     │         │  Build: O(n)     │
  │  Query: O(1)     │         │  Update: O(1)    │
  │  Update: REBUILD │         │  Query: REBUILD  │
  └─────────────────┘         └─────────────────┘

  They are NOT interchangeable. Pick the one that
  matches your problem's read/write pattern.

Trap 2: "I can interleave updates and range queries." A bare difference array supports batch $O (1)$ range updates followed by one $O (n)$ reconstruction—that's the entire contract. If you need a range sum query after each update, you need a BIT or segment tree. Trying to "just take a prefix sum" after every update degrades to $O (n \cdot Q)$ —no better than brute force.

The Mistake That Teaches

A contestant allocated a difference array of size $n$ and wrote d[r+1] -= v where $r = n - 1$ , sending d[n] one past the end. The code passed small tests—lucky memory layout—then crashed or silently corrupted output on the judge. The fix is a single character: allocate size $n + 2$ (or at minimum $n + 1$ ) so the sentinel slot always exists. One extra slot costs nothing; one out-of-bounds write costs the problem.

Debug This

Bug 1:

cpp

// Range update: add v to [l, r], 0-indexed
vector<int> d(n);
d[l] += v;
d[r] -= v;  // Bug here
// Reconstruct
for (int i = 1; i < n; i++) d[i] += d[i-1];

Answer

Should be d[r+1] -= v, not d[r] -= v. The cancellation must happen after position r, not at r itself—otherwise element a[r] doesn't receive the update.

Bug 2:

cpp

// Multiple updates then reconstruct
vector<long long> d(n + 2, 0);
for (auto& [l, r, v] : updates) {
    d[l] += v;
    d[r + 1] -= v;
}
// Print original + updates
for (int i = 0; i < n; i++) {
    d[i] += d[i - 1];  // Bug when i == 0
    cout << a[i] + d[i] << " ";
}

Answer

When i == 0, d[i-1] accesses d[-1], which is undefined behavior. The prefix sum loop should start at i = 1: for (int i = 1; i < n; i++) d[i] += d[i-1];.

Bug 3:

cpp

// 2D difference array: add v to rectangle (r1,c1)-(r2,c2)
d[r1][c1] += v;
d[r1][c2+1] -= v;
d[r2+1][c1] -= v;
d[r2+1][c2+1] -= v;  // Bug here

Answer

The bottom-right corner should be += v, not -= v. The 2D inclusion-exclusion requires adding back the doubly-subtracted corner: d[r2+1][c2+1] += v.

Self-Test

Cover these from memory. If any one trips you up, re-read the relevant section before moving on.

[ ] Write the difference-array range update (d[l] += v; d[r+1] -= v;) and explain why the cancellation goes at r+1, not r.
[ ] Explain why the difference array needs size n+1 (not n) to avoid out-of-bounds writes.
[ ] State the use-case boundary: when do you reach for a difference array vs. a prefix sum vs. a segment tree?
[ ] Write the four point-updates for a 2D difference-array rectangle update and verify on a 3x3 example.
[ ] Solve by hand: starting from zeros, apply "add 4 to [2, 5]" and "add 2 to [1, 3]," then reconstruct via prefix sum.

Stretch Questions

You need to add a linear function $v \cdot (i - l)$ over a range $[l, r]$ instead of a constant—how would you extend the difference array?
After applying range updates, you also need to answer range sum queries—what's the minimal data structure you'd combine with the difference array?
The problem requires both range updates and individual point updates interleaved with queries—when does the offline difference array approach break?

Practice Problems

#	Problem	Source	Key Idea	Approx. Rating
1	B - Greg and Array	CF 296B	Nested difference arrays (ops on ops)	CF 1400
2	C - Little Girl and Maximum Sum	CF 276C	Difference array + greedy sort	CF 1500
3	Range Update Queries	CSES	Direct 1D diff array + point queries	~CF 1300
4	Forest Queries	CSES	2D prefix sums (dual problem)	~CF 1400
5	C - Addition to Segment	CF Edu	Segment tree on difference array	CF 1500
6	D - Summer Dichotomy	CF 538D	Difference constraints + 2-SAT flavor	CF 2100
7	B - Karen and Coffee	CF 816B	Difference array + prefix sums	CF 1400
8	C - Flowers	CF 474C	Counting with prefix sums / DP	CF 1300
9	B - Queries on a String	CF 598B	Circular shift via difference-like idea	CF 1300
10	Static Range Sum Queries	CSES	Prefix sums (warmup / prerequisite)	~CF 1200

What to Solve Next

Next topic: Coordinate Compression—shrink massive value ranges so difference arrays (and other techniques) fit in memory.
Practice: Ladder 1100–1400—solidify difference arrays and prefix sums with curated contest problems.

Difference Arrays ​

Contents ​

Intuition ​

Visual Walkthrough ​

The Invariant ​

What the Code Won't Teach You ​

When to Reach for This ​

C++ STL Reference ​

Implementation ​

Contest Template (1D) ​

Explained Version (1D) ​

2D Difference Array ​

Operations Reference ​

Problem Patterns & Tricks ​

Offline Range Increment Queries ​

2D Difference Arrays for Rectangle Updates ​

Difference Array + Sorting for Interval Scheduling ​

Prefix XOR Difference ​

Difference on Trees (Euler Tour / DFS Order) ​

Polynomial / Higher-Order Differences ​

Difference Array on Sorted Events ​

Contest Cheat Sheet ​

Rating Progression ​

Before You Code ​

Gotchas & Debugging ​

Mental Traps ​

The Mistake That Teaches ​

Debug This ​

Self-Test ​

Stretch Questions ​

Practice Problems ​

Further Reading ​

What to Solve Next ​

Difference Arrays

Contents

Intuition

Visual Walkthrough

The Invariant

What the Code Won't Teach You

When to Reach for This

C++ STL Reference

Implementation

Contest Template (1D)

Explained Version (1D)

2D Difference Array

Operations Reference

Problem Patterns & Tricks

Offline Range Increment Queries

2D Difference Arrays for Rectangle Updates

Difference Array + Sorting for Interval Scheduling

Prefix XOR Difference

Difference on Trees (Euler Tour / DFS Order)

Polynomial / Higher-Order Differences

Difference Array on Sorted Events

Contest Cheat Sheet

Rating Progression

Before You Code

Gotchas & Debugging

Mental Traps

The Mistake That Teaches

Debug This

Self-Test

Stretch Questions

Practice Problems

Further Reading

What to Solve Next