DSA Visualizer
DSAViz
HomeSortingArraysSearchStackQueueLinked ListsTreesGraphsDynamic ProgrammingGreedy AlgorithmsBacktrackingString AlgorithmsLeetCode PatternsContact

© 2024 DSA Visualization

LeetCode pattern lab · cumulative state

One pass.Infinite answers.

Turn repeated addition into a reusable ledger. Every cell remembers the past, so ranges, targets, and balance checks collapse into constant-time arithmetic.

Mission controls

Configure the ledger

Boundary subtraction

Current mission

Range Sum Query — Immutable

Precompute once, then answer inclusive range sums in O(1).

Easy
Steps9
Checkpoints5
Ledger7

Playback console

Move through the math

1 / 9

Choose a mission, inspect the empty boundary, then build the ledger.

Calculation observatory

Create an n + 1 ledger

The leading zero represents the sum before the array begins and makes every range use the same formula.

Values6
Ledger cells7
Queries1

Source array

Values live between prefix boundaries.

active boundary p[0]
2nums[0]
-1nums[1]
3nums[2]
5nums[3]
-2nums[4]
4nums[5]
0prefix[0]
·prefix[1]
·prefix[2]
·prefix[3]
·prefix[4]
·prefix[5]
·prefix[6]
Active boundary
Decision boundary
Uncomputed

Live decision inspector

Why does the prefix ledger start with zero?

Empty prefix anchored
prefix[0] = 0
›

Next action

Accumulate each array value

The extra boundary removes the special case for ranges beginning at index 0.

Invariant

prefix[i] always means the sum of exactly the first i values.

Execution trace

Code in motion

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for value in nums:
            self.prefix.append(self.prefix[-1] + value)
    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

Why does this work?

Proof laboratory

Predict the boundary arithmetic first, then reveal why the cancellation is exact.

Local mastery

Your pattern record

Range Sum Query — Immutable0 runs0%
Subarray Sum Equals K0 runs0%
Find Pivot Index0 runs0%

Completion and best checkpoint accuracy remain in this browser.

Calculation in progress

The ledger is still remembering.

Complete the mission to record it. Prediction mastery requires at least 70% accuracy.

Recognize the pattern

When should you carry the past forward?

Look for repeated range totals, contiguous sums, balance points, or any question where many states differ only by a boundary. Prefix Sum replaces repeated traversal with a cumulative state that can be subtracted, compared, or indexed.

◇Are range sums queried repeatedly?
◇Can two boundaries define an answer?
◇Do negative values break a sliding window?
◇Can cumulative state remove rescanning?

Boundary recipe

  1. 01Choose whether prefix[i] includes or excludes index i.
  2. 02Seed the empty prefix explicitly.
  3. 03Express the target as a relationship between boundaries.
  4. 04Store counts when multiple earlier boundaries matter.