CodeWithYash

Intermediate · Module 8 · Lesson 1

1D prefix sums

Answer range sums with two cumulative values.

15–25 min readLesson 42 of 123 Interactive Lab
Jump to interactive visualizer

Lesson 42 of 123

1d streak

Interactive Visualization

Trace the algorithm state by state

Change the inputs, run an operation, and connect each visible state change to the explanation below.

Precomputation pattern

Prefix Sum

values
3
-2
5
1
-4
6
prefix
0
3
?
?
?
?
?

Invariant

prefix[i] stores the sum of values before index i. Subtracting two prefixes cancels everything outside the requested range.

Step 1 / 7

Theory lesson · Step-by-step

Understand 1D prefix sums

Answer range sums with two cumulative values.

Worked approach

Trace the reasoning step by step

  1. 1Define the cumulative or best-ending state required by 1D prefix sums.
  2. 2Initialize the identity or first-element base case explicitly.
  3. 3Update the current state from the previous state and current value.
  4. 4Combine directional states or subtract boundaries using matching index conventions.
  5. 5Test all-negative values, empty prefixes, single cells, and boundary queries.

Concrete example

Query sum indexes 1…3 in [2,4,1,5].

  1. 1Build prefix [0,2,6,7,12].
  2. 2Compute prefix[4] − prefix[1].

The range sum is 12 − 2 = 10.

What must remain true (Loop Invariant)

Each stored prefix, suffix, or ending-state value in 1D prefix sums summarizes exactly its declared contiguous range.

Cost Model

Complexity & Trade-offs

Build / range query
O(n) / O(1)
O(n)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Range queries, range updates, directional products, and best contiguous scores.
  • Replacing repeated range scans with cumulative state.
  • Combining left and right summaries.

Common mistakes

  • Mixing inclusive and exclusive prefix conventions.
  • Using zero as Kadane’s base when a non-empty all-negative answer is required.
  • Subtracting the wrong boundary or forgetting a neutral prefix.

Practice prompts

  • Reproduce the worked 1D prefix sums example without looking at the trace.
  • Change one input condition and explain whether the 1D prefix sums invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.