Prefix Sum

01 / The shared mechanism

Pay O(N) once to build a cumulative table — every range query that follows reduces to a constant-time subtraction. Flip the trick inside-out and you get cheap range updates instead.

Pick a sub-pattern above. Each is independently linkable — start where the problem statement points.

↑ choose one

— / When to use which

1-D linear

Use when you have many range-sum queries on a fixed array.

range-sum · running-total · LC 303

2-D grid

Use for rectangle queries on a matrix — inclusion-exclusion on the corners.

matrix-region · block-sum · LC 304

difference

Flip the direction: many range updates, then a single read of every cell.

range-add · car-pooling · flight-bookings

hash map

Count subarrays whose sum hits a target — prefix + map of seen prefixes.

subarray-sum-k · divisible-by-k · LC 560