More on Prefix Sums

Max Subarray Sum

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

2D Prefix Sums

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

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

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

Manually summing all the cells, we have a submatrix sum of $7+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 $(28-1) + (14-4) = 37$.

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 $N$ rows, the time complexity of this is $\mathcal{O}(QN)$. This might be fast enough for $Q=10^5$ and $N=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

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

Let's calculate $\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 $\texttt{prefix}[i-1][j-1]$.

The submatrix sum between rows $a$ and $A$ and columns $b$ and $B$, can thus be expressed as follows:

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

as expected.

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

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 $\mathcal{O}(1)$ per query after an $\mathcal{O}(NM)$ preprocessing.

Solution - Forest Queries

#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)

Problems

A More Complicated Example

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

Find $1\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 $a_i$, we'll also need to take prefix sums over $i\cdot a_i$.

First, define the following:

Then, we have:

And so,

Which is what we were looking for!