# Introduction to Prefix Sums

Authors: Darren Yao, Dustin Miao

Computing range sum queries in constant time over a fixed 1D array.

Focus Problem – try your best to solve this problem before continuing!

## Resources

Resources: Additional | ||||
---|---|---|---|---|

IUSACO | module is based off this | |||

CPH | rather brief | |||

PAPS | also rather brief |

## 1D Prefix Sums

Let's say we have a one-indexed integer array $\texttt{arr}$ of size $N$ and we want to compute the value of

for $Q$ different pairs $(a,b)$ satisfying $1\le a\le b\le N$. We'll use the following example with $N = 6$:

Index $i$ | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|

$\texttt{arr}[i]$ | 1 | 6 | 4 | 2 | 5 | 3 |

Naively, for every query, we can iterate through all entries from index $a$ to
index $b$ to add them up. Since we have $Q$ queries and each query requires a
maximum of $\mathcal{O}(N)$ operations to calculate the sum, our total time
complexity is $\mathcal{O}(NQ)$. For most problems of this nature, the
constraints will be $N, Q \leq 10^5$, so $NQ$ is on the order of $10^{10}$. This
is **not** acceptable; it will almost certainly exceed the time limit.

Instead, we can use prefix sums to process these array sum queries. We designate a prefix sum array $\texttt{prefix}$. First, because we're 1-indexing the array, set $\texttt{prefix}[0]=0$, then for indices $k$ such that $1 \leq k \leq N$, define the prefix sum array as follows:

Basically, what this means is that the element at index $k$ of the prefix sum array stores the sum of all the elements in the original array from index $1$ up to $k$. This can be calculated easily in $\mathcal{O}(N)$ by the following formula for each $1\le k\le N$:

For the example case, our prefix sum array looks like this:

Index $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|

$\texttt{prefix}[i]$ | 0 | 1 | 7 | 11 | 13 | 18 | 21 |

Now, when we want to query for the sum of the elements of $\texttt{arr}$ between (1-indexed) indices $a$ and $b$ inclusive, we can use the following formula:

Using our definition of the elements in the prefix sum array, we have

Since we are only querying two elements in the prefix sum array, we can calculate subarray sums in $\mathcal{O}(1)$ per query, which is much better than the $\mathcal{O}(N)$ per query that we had before. Now, after an $\mathcal{O}(N)$ preprocessing to calculate the prefix sum array, each of the $Q$ queries takes $\mathcal{O}(1)$ time. Thus, our total time complexity is $\mathcal{O}(N+Q)$, which should now pass the time limit.

Let's do an example query and find the subarray sum between indices $a = 2$ and $b = 5$, inclusive, in the 1-indexed $\texttt{arr}$. From looking at the original array, we see that this is

Index $i$ | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|

$\texttt{arr}[i]$ | 1 | 6 | 4 | 2 | 5 | 3 |

Using prefix sums:

Index $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|

$\texttt{prefix}[i]$ | 0 | 1 | 7 | 11 | 13 | 18 | 21 |

These are also known as partial sums.

## Solution - Static Range Sum

C++

In C++ we can use
`std::partial_sum`

,
although it doesn't shorten the code by much.

#include <bits/stdc++.h>using namespace std;#define sz(x) (int)size(x)using ll = long long;using vl = vector<ll>;vl psum(const vl &a) {vl psum(sz(a) + 1);

Java

import java.io.*;import java.util.*;public class Main {static int N, Q;public static void main(String[] args) throws IOException {BufferedReader reader =new BufferedReader(new InputStreamReader(System.in));PrintWriter writer = new PrintWriter(System.out);StringTokenizer st = new StringTokenizer(reader.readLine());

Python

def psum(a):psum = [0]for i in a:psum.append(psum[-1] + i) # psum[-1] is the last element in the listreturn psumN, Q = map(int, input().split())a = list(map(int, input().split()))p = psum(a)for i in range(Q):l, r = map(int, input().split())print(p[r] - p[l])

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Silver | Very Easy | ## Show TagsPrefix Sums | |||

Silver | Easy | ## Show TagsPrefix Sums | |||

Silver | Easy | ## Show TagsPrefix Sums | |||

CSES | Easy | ## Show TagsPrefix Sums | |||

CSES | Easy | ## Show TagsPrefix Sums | |||

Silver | Easy | ## Show TagsPrefix Sums | |||

Old Bronze | Normal | ## Show TagsPrefix Sums | |||

CF | Normal | ## Show TagsMath, Prefix Sums | |||

AC | Normal | ## Show TagsPrefix Sums | |||

CF | Normal | ## Show TagsPrefix Sums | |||

CF | Normal | ## Show TagsPrefix Sums | |||

AC | Hard | ## Show TagsPrefix Sums |

### Warning!

"Haybale Stacking" isn't submittable on the USACO website. Use this link to submit.

## Quiz

What is the optimal time complexity of calculating the prefix sum array of some array of length $n$?

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!