cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 32 of 218
Ideas this builds on
Arrays, search & sorting32 / 218

Difference arrays: store changes

Picture

Add 3 to positions 1 through 3. Instead of touching three cells, record +3 where the effect begins.

Predict

Does a difference array answer arbitrary online point queries immediately?

Walk through the small example

No. A constant range addition changes only where its effect begins and ends.

Mental model and complete Python solution

Store the derivative of the array: a range update has one upward jump and one downward jump. Prefix summing integrates those changes back into final values.

What the function promises: Apply inclusive zero-based range additions to a length-n zero array. Invalid ranges raise ValueError.

def range_additions(n, updates):
    difference = [0] * (n + 1)
    for left, right, amount in updates:
        if not 0 <= left <= right < n:
            raise ValueError("Invalid range")
        difference[left] += amount
        difference[right + 1] -= amount
    answer, running = [], 0
    for i in range(n):
        running += difference[i]
        answer.append(running)
    return answer

assert range_additions(5, [(1,3,3),(2,4,2)]) == [0,3,5,5,2]
assert range_additions(0, []) == []

Work and storage: O(u + n) time and O(n) space for u updates.

When to recognize it: A constant range addition changes only where its effect begins and ends.

Check before applying it: Online intermixed updates and queries need another structure such as Fenwick or segment tree.

Change one rule

Updates and sum queries arrive online.

See what changes

Use a Fenwick tree or segment tree, choosing based on the update and query operations.

Connect

prefix sums: A prefix sum integrates boundary changes into values.

Fenwick tree: prefix sums with updates: Support online prefix aggregates with logarithmic updates.