A More Complicated Example of Prefix Sums

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

Find 1⋅al+2⋅al+1+3⋅al+2+⋯+(r−l+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 i⋅aii\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]=1⋅a1+2⋅a2+⋯+i⋅ai\texttt{ips}[i] = 1\cdot a_1+2\cdot a_2+\cdots+i\cdot a_i

Then, we have:

l⋅al+(l+1)⋅al+1+⋯+r⋅ar=ips[r]−ips[l−1]l\cdot a_l + (l+1) \cdot a_{l+1} + \cdots + r \cdot a_r = \texttt{ips}[r]-\texttt{ips}[l-1]
(l−1)⋅al+(l−1)⋅al+1+⋅+(l−1)⋅ar=(l−1)(ps[r]−ps[l−1])(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,

1⋅al+2⋅al+1+⋯+(r−l+1)⋅ar=ips[r]−ips[l−1]−(l−1)(ps[r]−ps[l−1])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!

Problem Solution

This problem requires slight extensions of the above approach. See the Official Analysis for more information.

#include <bits/stdc++.h>


using namespace std;


const int maxN = 2e5 + 5;


int n, q;
int ar[maxN];
vector<long long> ipsEven(maxN), ipsOdd(maxN), psEven(maxN), psOdd(maxN);

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!

Join Forum