AlgoScope

Prefix Sum

Store running totals once, and any range sum becomes two lookups and a subtraction.

Array algorithms and techniques, algorithm, beginner
Index 0 keeps its value 3 as the first running total.3011421354952667i
Index 0 keeps its value 3 as the first running total.3011421354952667i

Prefix Sum and Kadane: Range sum from prefix totals

Step, step 2 of 11

Index 0 is its own total, 3.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

O(1) per query after O(n) build.

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

Prefix Sum and Kadane covers these too, in the same run.