Range Updates + Point Queries, in depth: difference arrays, Fenwick trees and range sums

The difference array

Define the difference array of a as d[0] = a[0] and d[i] = a[i] - a[i-1]. Then a[i] = d[0] + d[1] + ... + d[i]: the original array is the prefix sum of its differences. Adding v to every element of a[l..r] changes exactly two differences. The step into the range at l grows by v, the step out of it at r+1 shrinks by v, and every difference strictly inside the range is unchanged because both neighbours moved together.

Worked example: eight zeros, then three updates: add 3 to [2, 5], add 2 to [4, 7], subtract 1 from [0, 3]. The difference array becomes [-1, 0, 3, 0, 3, 0, -3, 0, -2], nine entries because the update ending at index 7 writes to index 8. One prefix sum recovers [-1, -1, 2, 2, 5, 5, 2, 2]. Check index 4 by hand: it lies in [2, 5] and [4, 7] but not [0, 3], so it should be 3 + 2 = 5, which matches. Checking one or two indices like this is the fastest way to catch a misplaced boundary.

def apply_offline(n, updates):
    d = [0] * (n + 1)                 # n + 1: r + 1 may equal n
    for l, r, v in updates:           # inclusive [l, r]
        d[l] += v
        d[r + 1] -= v
    out, running = [], 0
    for i in range(n):
        running += d[i]
        out.append(running)
    return out

print(apply_offline(8, [(2, 5, 3), (4, 7, 2), (0, 3, -1)]))
# [-1, -1, 2, 2, 5, 5, 2, 2]

This is O(1) per update and O(n) once at the end. It is the right tool whenever all updates arrive before any query, which is more common than it sounds: nightly batch jobs, log replays, and any problem that reads the final state once.

Interval coverage and peak occupancy

Counting how many intervals cover each point is the same trick with v = 1. Hotel occupancy is the classic case. Bookings are naturally half-open, [check_in, check_out), because a guest leaving on day 4 frees the room for a guest arriving on day 4. With half-open intervals the second mark goes at check_out, not check_out + 1.

bookings = [(1, 4), (2, 6), (3, 5), (5, 9), (8, 10)]   # [in, out), days 0..9
d = [0] * 11
for start, end in bookings:
    d[start] += 1
    d[end] -= 1
occupancy, running = [], 0
for day in range(10):
    running += d[day]
    occupancy.append(running)
print(occupancy)        # [0, 1, 2, 3, 2, 2, 1, 1, 2, 1]
print(max(occupancy))   # 3 rooms needed at peak, on day 3

The peak, three rooms on day 3, is the minimum number of rooms that can host every booking, which is also the answer to the meeting-rooms problem and to capacity planning for overlapping jobs. Decide on inclusive or half-open once, write it in the function's docstring, and convert at the boundary of your system; mixing conventions is the single most common bug in interval code. For merging and scheduling intervals rather than counting them, see interval merging and scheduling.

Online: a Fenwick tree over the differences

The offline method breaks when queries arrive between updates, because each point query would need an O(n) prefix sum. The fix is to keep the difference array inside a structure that answers prefix sums quickly. A Fenwick tree supports point add and prefix sum in O(log n), and that is precisely the pair of operations needed: a range update is two point adds on the difference array, and a point query is one prefix sum of it.

class RangeAddPointQuery:
    """0-indexed; add(l, r, v) adds v to a[l..r] inclusive; get(i) returns a[i]."""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)          # 1-indexed Fenwick array

    def _add(self, i, v):                  # point add on the difference array
        i += 1
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def add(self, l, r, v):
        self._add(l, v)
        if r + 1 < self.n:                 # past-the-end mark is never queried
            self._add(r + 1, -v)

    def get(self, i):                      # prefix sum of differences = a[i]
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

Here the Fenwick tree has exactly n slots because a mark at r + 1 = n would only affect positions beyond the array and can be dropped. Both operations walk at most log₂(n) + 1 nodes, about 21 for a million positions. The class above was tested against a brute-force list over hundreds of random update sequences, which is the test every such structure should ship with.

Range updates with range sums: two trees

What if you need the sum over a range after range updates? The prefix sum of a up to i is a double sum over the differences: sum_{k<=i} a[k] = sum_{j<=i} d[j] * (i + 1 - j), because difference d[j] contributes to every a[k] with j <= k <= i. Split the factor: (i + 1) * sum d[j] - sum d[j] * j. Keep two Fenwick trees, one over d[j] and one over d[j] * j, and the prefix sum is a combination of two queries. Fenwick below is a plain point-add, prefix-sum tree like the one above.

class RangeAddRangeSum:
    def __init__(self, n):
        self.n = n
        self.b1 = Fenwick(n)               # stores d[j]
        self.b2 = Fenwick(n)               # stores d[j] * j

    def _mark(self, j, v):
        if j < self.n:
            self.b1.add(j, v)
            self.b2.add(j, v * j)

    def add(self, l, r, v):
        self._mark(l, v)
        self._mark(r + 1, -v)

    def prefix(self, i):                   # a[0] + ... + a[i]
        return self.b1.prefix(i) * (i + 1) - self.b2.prefix(i)

    def range_sum(self, l, r):
        return self.prefix(r) - (self.prefix(l - 1) if l > 0 else 0)

Textbook versions of this formula differ in sign and in whether the multiplier is i or i + 1, depending on 0- or 1-indexing and on whether the second tree stores v * (l - 1) or v * l. Each is correct with its own convention and wrong with any other, so derive it once for your indexing and test against brute force.

Choosing a structure

The difference trick depends on the update being invertible: you can cancel +v with -v at the right end. Range assignment (set every element to 7) and range max-with are not invertible, so they need a segment tree with lazy propagation. Likewise, queries for range minimum or maximum after range additions need a segment tree, because prefix sums cannot answer them.

Operational concerns

In production code the algorithms are rarely the hard part; the boundaries are.

• Huge or sparse coordinates. Timestamps in milliseconds or IDs up to 10¹² cannot index an array. Collect every l and r + 1, sort and deduplicate them, and map them to compact indices (coordinate compression). Values then describe whole segments between consecutive event points, which is the sweep-line view of the same idea.
• Overflow. A Fenwick node stores the sum of many updates, and the range-sum variant multiplies by i + 1. With 10⁶ updates of 10⁹ over 10⁶ positions the products reach 10²¹, which overflows 64-bit integers. Bound the worst case before choosing a type, or use 128-bit or arbitrary precision.
• Floating point. Adding and later cancelling floats leaves residue: a range that should read 0 reads 1e-12. Use integers in fixed-point units (cents, microseconds) where you can.
• Concurrency. A Fenwick tree is not safe for concurrent writers. Shard by key range, batch updates through a single writer, or rebuild snapshots offline and swap them atomically.
• Validation. Reject l > r and out-of-range indices at the API boundary; a silent r + 1 write past the end corrupts a neighbour in languages without bounds checks.

Failure modes

• Array sized n instead of n + 1 in the offline method, so an update ending at the last element writes out of bounds or is silently dropped.
• Mixed conventions: inclusive in one module, half-open in another, giving off-by-one errors only at range ends.
• Using a difference array online: rebuilding prefix sums per query turns O(log n) into O(n) and passes small tests while timing out at scale.
• Copying a two-tree formula from a source with different indexing, which yields plausible but wrong sums.
• Applying the trick to non-invertible updates such as assignment, which cannot be cancelled at r + 1.

Trade-offs

Offline versus online. If you can buffer updates and answer queries in a batch, the difference array wins on every axis: one array, no logarithms, and cache-friendly sequential passes. Reach for a Fenwick tree only when a query genuinely must see every update made before it.

Fenwick versus segment tree. A Fenwick tree uses n integers and a dozen lines of code, and its loops are tight enough to be several times faster than a recursive lazy segment tree in practice. A segment tree uses roughly two to four times the memory and far more code, but it supports operations a Fenwick tree cannot express. Start with the simplest structure that answers your queries and move up only when an operation forces you to.

Exactness versus memory. Coordinate compression keeps memory proportional to the number of distinct endpoints rather than the coordinate range, at the cost of a sort and a binary search per operation, and it requires knowing the endpoints in advance or rebuilding when new ones arrive.

What to do next

1. Implement the offline difference array and verify it by hand on the eight-element example above.
2. Write the Fenwick range-add point-query class and a randomised test against a brute-force list.
3. Derive the two-tree range-sum formula for your own indexing before coding it, then test it the same way.
4. Solve the meeting-rooms problem with half-open intervals and coordinate compression for timestamps.
5. Pick a case where updates are assignments or queries are minimums and implement a lazy segment tree instead.
6. Read sqrt decomposition for a simpler fallback when an operation fits neither structure.