Skip to content
UPEEC

Prefix Sums

Precompute running totals so any range sum is one subtraction.

Easy
Comments 0

P[i] = a[0] + … + a[i-1]; sum of a[l..r] = P[r+1] - P[l]. 2-D prefix sums handle rectangles.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)

Sign in or join free to ask questions and discuss this topic.