PrevNext
Somewhat Frequent
 0/14

Introduction to Prefix Sums

Authors: Darren Yao, Eric Wei

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

Focus Problem – read through 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 arr\texttt{arr} of size NN and we want to compute the value of

arr[a]+arr[a+1]++arr[b]\texttt{arr}[a]+\texttt{arr}[a+1]+\cdots+\texttt{arr}[b]

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

Index ii123456
arr[i]\texttt{arr}[i]164253

Naively, for every query, we can iterate through all entries from index aa to index bb to add them up. Since we have QQ queries and each query requires a maximum of O(N)\mathcal{O}(N) operations to calculate the sum, our total time complexity is O(NQ)\mathcal{O}(NQ). For most problems of this nature, the constraints will be N,Q105N, Q \leq 10^5, so NQNQ is on the order of 101010^{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 prefix\texttt{prefix}. First, because we're 1-indexing the array, set prefix[0]=0\texttt{prefix}[0]=0, then for indices kk such that 1kn1 \leq k \leq n, define the prefix sum array as follows:

prefix[k]=i=1karr[i]\texttt{prefix}[k]=\sum_{i=1}^{k} \texttt{arr}[i]

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

prefix[k]=prefix[k1]+arr[k]\texttt{prefix}[k]=\texttt{prefix}[k-1]+\texttt{arr}[k]

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

Index ii0123456
prefix[i]\texttt{prefix}[i]01711131821

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

i=LRarr[i]=i=1Rarr[i]i=1L1arr[i]\sum_{i=L}^{R} \texttt{arr}[i] = \sum_{i=1}^{R} \texttt{arr}[i] - \sum_{i=1}^{L-1} \texttt{arr}[i]

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

i=LRarr[i]=prefix[R]prefix[L1]\sum_{i=L}^{R} \texttt{arr}[i]= \texttt{prefix}[R]-\texttt{prefix}[L-1]

Since we are only querying two elements in the prefix sum array, we can calculate subarray sums in O(1)\mathcal{O}(1) per query, which is much better than the O(N)\mathcal{O}(N) per query that we had before. Now, after an O(N)\mathcal{O}(N) preprocessing to calculate the prefix sum array, each of the QQ queries takes O(1)\mathcal{O}(1) time. Thus, our total time complexity is O(N+Q)\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=2a = 2 and b=5b = 5, inclusive, in the 1-indexed arr\texttt{arr}. From looking at the original array, we see that this is

i=25arr[i]=6+4+2+5=17.\sum_{i=2}^{5} \texttt{arr}[i] = 6 + 4 + 2 + 5 = 17.
Index ii 1 2 3 4 5 6
arr[i]\texttt{arr}[i] 1 6 4 2 5 3

Using prefix sums:

prefix[5]prefix[1]=181=17.\texttt{prefix}[5] - \texttt{prefix}[1] = 18 - 1 = 17.
Index ii 0 1 2 3 4 5 6
prefix[i]\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.util.*;
import java.io.*;
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());
N = Integer.parseInt(st.nextToken());

Python

def psum(a):
psum=[0]
for i in a:
psum.append(psum[-1]+i) # psum[-1] is the last element in the list
return psum
N, 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

StatusSourceProblem NameDifficultyTags
LCVery Easy
Show TagsPrefix Sums
SilverVery Easy
Show TagsPrefix Sums
SilverEasy
Show TagsPrefix Sums
SilverEasy
Show TagsPrefix Sums
CSESEasy
Show TagsPrefix Sums
CSESEasy
Show TagsPrefix Sums
SilverEasy
Show TagsPrefix Sums
CSESEasy
Show TagsPrefix Sums
Old BronzeNormal
Show TagsPrefix Sums
CFNormal
Show TagsMath, Prefix Sums
KSHard
Show TagsPrefix Sums
ACHard
Show TagsPrefix Sums
PlatHard
Show TagsPrefix Sums, Sliding Window

XOR

Check Intro to Bitwise Operators if you're not familiar with XOR.

Warning!

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

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!

PrevNext