[EP 1] Prefix sums.md

Prefix sums

Given an array $a$ of $n$ elements, prefix sums allow you to calculate the sum of any range of elements $[l, r]$ $1 \leq l \leq r \leq n$ in $\mathcal{O}(1)$ constant time (with $\mathcal{O}(n)$ pre-processing).

The trick is to pre-calculate (to calculate once beforehand for multiple usages later) an array $\mathrm{prefix}$, of cumulative sums. For each $i$ from $1$ to $n$, $\mathrm{prefix}_i$ stores the sum $a_1 + a_2 + \ldots + a_i$. Then, the sum of elements in the range $[l, r]$ can be easily found out as $\mathrm{prefix}r - \mathrm{prefix}{l-1}$.

Reading material:

• Peltorator [V] (Use english subtitles)
• USACO [B]
• 2D prefix sums - USACO [B]
• Range updates using prefix sums - Codeforces [B]

Problems

• Spoj CSUMQ
• Codechef SHIVIGOD
• CF 433 B
• CF 276 C
• CF 1363 B
• CF 1253 C
• CF 1265 C
• CF 1118 B
• CF 1200 D
• AtCoder ABC 260 G

This page uses math latex formatting. Download the extension to render it.