PrevNext
Not Frequent
 0/9

More on Prefix Sums

Authors: Darren Yao, Eric Wei, Neo Wang, Qi Wang

Max subarray sum, prefix sums in two dimensions, and a more complicated example.

Max Subarray Sum

Focus Problem – read through this problem before continuing!

This problem has a solution known as Kadane's Algorithm. Please don't use that solution; try to solve it with prefix sums.

Why are the two methods equivalent?

2D Prefix Sums

Focus Problem – read through this problem before continuing!

Now, what if we wanted to process QQ queries for the sum over a subrectangle of a 2D matrix with NN rows and MM columns? Let's assume both rows and columns are 1-indexed, and we use the following matrix as an example:

000000
0156118
0171194
046132
075423

Naively, each sum query would then take O(NM)\mathcal{O}(NM) time, for a total of O(QNM)\mathcal{O}(QNM). This is too slow.

Let's take the following example region, which we want to sum:

000000
0156118
0171194
046132
075423

Manually summing all the cells, we have a submatrix sum of 7+11+9+6+1+3=377+11+9+6+1+3 = 37.

The first logical optimization would be to do one-dimensional prefix sums of each row. Then, we'd have the following row-prefix sum matrix. The desired subarray sum of each row in our desired region is simply the green cell minus the red cell in that respective row. We do this for each row to get (281)+(144)=37(28-1) + (14-4) = 37.

000000
016122331
018192832
0410111416
0712161821

Now, if we wanted to find a submatrix sum, we could break up the submatrix into a subarray for each row, and then add their sums, which would be calculated using the prefix sums method described earlier. Since the matrix has NN rows, the time complexity of this is O(QN)\mathcal{O}(QN). This might be fast enough for Q=105Q=10^5 and N=103N=10^3, but we can do better.

In fact, we can do two-dimensional prefix sums. In our two dimensional prefix sum array, we have

prefix[a][b]=i=1aj=1barr[i][j].\texttt{prefix}[a][b]=\sum_{i=1}^{a} \sum_{j=1}^{b} \texttt{arr}[i][j].

This can be calculated as follows for row index 1in1 \leq i \leq n and column index 1jm1 \leq j \leq m:

prefix[i][j]=prefix[i1][j]+prefix[i][j1]prefix[i1][j1]+arr[i][j]\begin{aligned} \texttt{prefix}[i][j] =& \, \texttt{prefix}[i-1][j]+ \texttt{prefix}[i][j-1] \\ &- \texttt{prefix}[i-1][j-1]+ \texttt{arr}[i][j] \end{aligned}

Let's calculate prefix[2][3]\texttt{prefix}[2][3]. Try playing with the interactive widget below by clicking the buttons to see which numbers are added in each step. Notice how we overcount a subrectangle, and how we fix this by subtracting prefix[i1][j1]\texttt{prefix}[i-1][j-1].

add prefix[i-1][j]
add prefix[i][j-1]
subtract prefix[i-1][j-1]
add array[i][j]
to get prefix[i][j]
000000
0156118
0171194
046132
075423

The submatrix sum between rows aa and AA and columns bb and BB, can thus be expressed as follows:

i=aAj=bBarr[i][j]=prefix[A][B]prefix[a1][B]prefix[A][b1]+prefix[a1][b1]\begin{aligned} \sum_{i=a}^{A} \sum_{j=b}^{B} \texttt{arr}[i][j]=&\,\texttt{prefix}[A][B] - \texttt{prefix}[a-1][B] \\ &- \texttt{prefix}[A][b-1] + \texttt{prefix}[a-1][b-1] \end{aligned}

Summing the blue region from above using the 2D prefix sums method, we add the value of the green square, subtract the values of the red squares, and then add the value of the gray square. In this example, we have

65236+1=37,65-23-6+1 = 37,

as expected.

000000
016122331
0214315163
0624426579
013365883100

Try playing with the interactive widget below by clicking the buttons to see which numbers are added in each step.

add prefix[A][B]
subtract prefix[a-1][B]
subtract prefix[A][b-1]
add prefix[a-1][b-1]
to get our result
000000
0156118
0171194
046132
075423

Since no matter the size of the submatrix we are summing, we only need to access four values of the 2D prefix sum array, this runs in O(1)\mathcal{O}(1) per query after an O(NM)\mathcal{O}(NM) preprocessing.

Solution - Forest Queries

Warning!

We need to be cautious of off-by-one errors, as intervals can be inclusive, exclusive, 1-indexed, etc.

C++

#include <bits/stdc++.h>
using namespace std;
#define vt vector
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); i++)
#define trav(a, x) for (auto& a : x)

Java

import java.io.*;
import java.util.StringTokenizer;
public class ForestQueries {
static int N;
static int Q;
static int[][] pfx;
static int[][] arr;
public static void main(String[] args) {
Kattio io = new Kattio();

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
SilverEasy
Show Tags

2D Prefix Sums

SilverHard
Show Tags

2D Prefix Sums

External Sol
GoldHard
Show Tags

2D Prefix Sums, Max Subarray Sum

External Sol
PlatVery Hard
Show Tags

2D Prefix Sums

External Sol

A More Complicated Example

What if we want to quickly answer the following type of query?

Find 1al+2al+1+3al+2++(rl+1)ar1\cdot a_l+2\cdot a_{l+1}+3\cdot a_{l+2}+\cdots+(r-l+1)\cdot a_{r}.

In addition to taking prefix sums over aia_i, we'll also need to take prefix sums over iaii\cdot a_i.

First, define the following:

ps[i]=a1+a2+a3+a4++ai\texttt{ps}[i] = a_1+a_2+a_3+a_4+\cdots+a_i
ips[i]=1a1+2a2++iai\texttt{ips}[i] = 1\cdot a_1+2\cdot a_2+\cdots+i\cdot a_i

Then, we have:

lal+(l+1)al+1++rar=ips[r]ips[l1]l\cdot a_l + (l+1) \cdot a_{l+1} + \cdots + r \cdot a_r = \texttt{ips}[r]-\texttt{ips}[l-1]
(l1)al+(l1)al+1++(l1)ar=(l1)(ps[r]ps[l1])(l-1) \cdot a_l + (l-1) \cdot a_{l+1} + \cdot + (l-1) \cdot a_r = (l-1)(\texttt{ps}[r]-\texttt{ps}[l-1])

And so,

1al+2al+1++(rl+1)ar=ips[r]ips[l1](l1)(ps[r]ps[l1])1\cdot a_l + 2 \cdot a_{l+1} + \cdots + (r-l+1) \cdot a_r = \texttt{ips}[r]-\texttt{ips}[l-1]-(l-1)(\texttt{ps}[r]-\texttt{ps}[l-1])

Which is what we were looking for!

StatusSourceProblem NameDifficultyTagsSolutionURL
KSEasy
Show Tags

Prefix Sums

ACHard
Show Tags

Prefix Sums

Check AC
PlatInsane
Show Tags

Prefix Sums

External Sol

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