Data Structures19 sections · 729 units
Open in Course

Vocabulary - Prefix Sum

Cumulative totals

A prefix sum array stores cumulative sums. For array arrarr, the prefix sum prefix[i]prefix[i] equals the sum of all elements from index 00 to i1i-1.

prefix[i]=arr[0]+arr[1]++arr[i1]prefix[i] = arr[0] + arr[1] + \cdots + arr[i-1] We set prefix[0]=0prefix[0] = 0 by convention. So prefixprefix has length n+1n+1 when arrarr has length nn. Why store cumulative sums?

Because any range sum you can compute from two prefix values. That's the core idea.