Module 09 · DSA · Four patterns the ladders lean on

The running total (prefix sums and difference arrays)

Before you start. Foundations #03: Arrays, Do-Pointer & Sliding Window (written in Hinglish) showed the running-total trick once: keep a list of totals so far, put a fake 0 at the front, and any stretch of the array becomes one subtraction. Hashing gave you the hash map: ask for a key and get its value back in one step, no searching. The ladders in The Practice Ladders lean on both. This lesson teaches the trick properly, then bends it three ways.

Lesson 67 of 74 in DSA

The rest of this lesson is part of a plan.

A plan opens every lesson, board, video, lab and paper on chalk. Yearly is $39/year, or $19.50 for your first year with LAUNCH50, ends 1 Nov, 18:30 UTC.

See plans Already a member? Sign in

Or start free: a free account opens lessons 2 and 3 of every track.

In this lesson

1984: a tilted floor, and a rectangle of pixels to average
The prefix sum: a trip meter with a reading at every stop
The range query: how far between two stops is two readings and one subtraction
The subarray sum: counting stretches that add up to k
Why negatives break the window and leave the prefix sum alone
The difference array: write down only where the road changes
The 2D prefix sum: Crow’s table, with the overlap taken back
Build the prefix sum, ask three ranges
Count subarrays that add to k, and why the map starts at {0: 1}
Where the sliding window gives the wrong answer
The difference array: many updates, one sweep
The 2D prefix sum, with inclusion-exclusion
Free problems that drill it

Terms it explains: prefix sum, range query, subarray, subarray sum, difference array, 2D prefix sum, inclusion-exclusion.

Review DSA

Connects to

The Practice Ladders Who is in my group? (union-find)

Index

Open everything on chalk.

The running total (prefix sums and difference arrays)

In this lesson