this blog will talk about prefix sums in general , how to use them , nice tricks , etc ...↵
↵
this blog was made to summarize HCPC-2025 training for prefix sums in Homs university / Syria.↵
↵
overview↵
==================↵
###1. what is prefix sum?↵
###2. get range sum in $O(1)$↵
###3. find number of sub arrays with sum equal to $x$ (map trick)↵
###4. even more prefix sums↵
↵
lets start:↵
↵
###1. what is prefix sum?↵
↵
prefix sum of an array a of size $n$ is another array of size $n+1$ as follows:↵
↵
```↵
a(1) a(2) a(3) ... a(n)↵
p(0)=0 p(1)=a(1) p(2)=a(1)+a(2) p(3)=a(1)+a(2)+a(3) ... p(n)=a(1)+a(2)+...+a(n)↵
```↵
↵
so in general $p(i)$ contains the sum of all elements up to $i$↵
↵
and we introduce another element at the front representing the empty prefix↵
↵
we can build prefix sum array in simple one line of code↵
↵
```↵
for(int i=1;i<=n;i++)p[i]=p[i-1]+a[i];↵
```↵
↵
this is the only info we care about (for now).↵
↵
↵
###2.get range sum in $O(1)$↵
↵
as we want the sum in range $[L,R]$ ↵
↵
we realize that it is the same as $p(R)-p(L-1)$↵
↵
```↵
a(L)+a(L+1)+...+a(R)=(a(1)+a(2)+...+a(L-1)+a(L)...+a(R))-(a(1)+a(2)+...+a(L-1)) = p(R)-p(L-1)↵
```↵
↵
###3. find the number of sub arrays with sum equal to $x$↵
↵
given the array $a$ of size $n$↵
↵
every sub array sum is represented by two prefix sums $p(L-1),p(R)$↵
↵
first we initialize a map↵
↵
```↵
map<int,int> cnt;↵
```↵
↵
and loop through the array↵
↵
lets say we are considering index $i$↵
↵
at this point every prefix sum $p(j)$ such that $j<i$ is considered in the map↵
↵
it is necessary to consider the empty prefix at first↵
↵
```↵
cnt[0]=1;↵
```↵
↵
and then at each index $i$↵
↵
we do *something to get all sub arrays ending at index $i$ and have the sum equal to $x$ count and add it to the final answer↵
↵
and then do↵
↵
```↵
cnt[p[i]]++;↵
```↵
↵
what to *do each time?↵
↵
well we want the following equation $ p(i)-V=x $ when V is the value that we are searching↵
↵
then $V=p(i)-x$ ↵
↵
so we simply add $cnt[p[i]-x]$ to the final answer each time↵
↵
note that $V=p(L-1)$ that's why we considered the empty prefix at the first place↵
↵
there is a [problem](https://cses.fi/problemset/task/1661) at CSES mentioning this trick ↵
↵
###4. even more prefix sums↵
↵
here i will mention other prefix stuff that might be useful to use later,↵
↵
####1.prefix xor↵
↵
we can create an array containing the xor of each prefix, this way we can get the xor of any range↵
↵
```↵
for(int i=1;i<=n;i++)p[i]=p[i-1]^a[i];↵
//xor of a range [L,R] is p[R]^p[L-1]↵
```↵
↵
this is possible because ↵
↵
```↵
X^X=0 , A^B=B^A , X^0=X↵
```↵
↵
####2.prefix $mul$,$and$ , $or$ , $max$ , $min$ , $gcd$ and rarely $lcm$↵
↵
these queries are sadly not usual to get in a range as we will need advanced data structures (aka sparse table) to get them in $O(1)$ (or $log(n)$ in case of gcd,lcm)↵
↵
but you can get them in $log(n)$ complexity by using segment trees (out of topic but worth mentioning)↵
↵
if we want $mul$ in range we wouldd need to make sure a lot of things are satisfied , like there should not be zero (as it will make all prefixes ahead zeros and we cant cancel them),and overflow cannot happen (which could mean a lot of things), in our case we will focus on $mul$ in range with $mod$ so we can get inverse mod in $O(log(n))$,or even $O(1)$ if the mod is small enough↵
↵
it is also important to mention that we can get $(and,or)$ queries in range using simple prefix sum ↵
↵
by applying prefix sum on each bit as follows:↵
↵
```↵
for(int j=0;j<30;j++){↵
for(int i=1;i<=n;i++){↵
p[j][i]=p[j][i-1]+((a[i]>>j)&1);↵
}↵
}↵
```↵
↵
and then we can get $or$ or $and$ queries in a range $[L,R]$ as follows:↵
↵
```↵
int AND(int L,int R){↵
int res=0;↵
for(int j=0;j<30;j++){↵
if(p[j][R]-p[j][L-1]==R-L+1)res+=1<<j;↵
}↵
return res;↵
}↵
↵
int OR(int L,int R){↵
int res=0;↵
for(int j=0;j<30;j++){↵
if(p[j][R]-p[j][L-1]>0)res+=1<<j;↵
}↵
return res;↵
}↵
```↵
↵
but in certain problems it is enough to get them in a prefix (or a suffix maybe?)↵
↵
####3. 2D prefix sum↵
↵
the idea is we want to get sum in a rectangle in $O(1)$↵
↵
given the 2D array $a$ of $n$ rows and $m$ columns ↵
↵
```↵
a(1,1) a(1,2) ... a(1,m)↵
a(2,1) a(2,2) ... a(2,m)↵
...↵
a(n,1) a(n,2) ... a(n,m)↵
```↵
↵
we do a prefix sum on each row of $a$ first↵
so that↵
↵
```↵
p(i,j)=a(i,1)+a(i,2)+...+a(i,j)↵
```↵
↵
and then we do another prefix sum on columns of $p$↵
so that↵
↵
```↵
s(i,j)=p(1,j)+p(2,j)+...+p(i,j)↵
```↵
↵
actually we don't need two more arrays for that, we can simply apply these operations on the same array twice,↵
or one more array just to keep the original array.↵
↵
the code is as follows:↵
↵
```↵
for(int i=1;i<=n;i++)↵
for(int j=1;j<=m;j++)p[i][j]=a[i][j]+p[i][j-1];↵
↵
for(int j=1;j<=m;j++)↵
for(int i=1;i<=n;i++)p[i][j]+=p[i-1][j];↵
``` ↵
↵
we can get sum of elements in a rectangle with upper left corner at $(i,j)$ and with $x$ rows and $y$ columns like this↵
↵
```↵
p[i+x-1][j+y-1]-p[i+x-1][j-1]-p[i-1][j+y-1]+p[i-1][j-1]↵
```↵
↵
using inclusion exclusion principle (which is out of topic right now)↵
↵
but i can explain why this is true↵
↵
let the array $f$ represent how may times we added an element from the array $a$↵
↵
first each $f(i,j)=0$↵
↵
i will add each component to see how the frequency of elements change↵
↵
notice that adding $p(i,j)$ represents increasing the value of $f(i1,j1)$ $i1<=i&&j1<=j$ by one ↵
↵
```↵
i=2,j=2,x=4,y=3↵
+p[i+x-1][j+y-1] -p[i+x-1][j-1] -p[i-1][j+y-1] +p[i-1][j-1]↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 -1 0 0 0 0 0 0 0 0 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
↵
```↵
↵
####4.sweep lineoffline range addition↵
↵
the idea is simple↵
↵
given an array of zeros $a$↵
↵
```↵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0↵
``` ↵
↵
you can add $V$ to a range $[L,R]$ by adding $V$ to $a(L)$ and subtracting $V$ from $a(R+1)$↵
↵
```↵
0 0 0 V 0 0 0 0 0 -V 0 0 0 0 0↵
```↵
↵
and then applying prefix sum on the array↵
↵
```↵
0 0 0 V V V V V V 0 0 0 0 0 0 0↵
```↵
↵
well that is not useful when talking about one query , the thing is you can add multiple values to multiple ranges and then apply prefix sum , this is considered offline approach in multiple cases.↵
↵
####5.sweep line on a 2D arrayoffline 2D range addition↵
↵
adding V to rectangle with upper left corner at $(i,j)$ and with $x$ rows and $y$ columns↵
↵
add V to both $(i,j)$ $(i+x,j+y)$ ↵
↵
subtract V from both $(i+x,j)$ $(i,j+y)$↵
↵
and then apply prefix sum 2D like we learned↵
↵
```↵
i=2,j=2,x=2,y=3↵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0↵
0 0 0 0 0 0 V 0 0 -V 0 V V V 0↵
0 0 0 0 0 0 0 0 0 0 0 V V V 0↵
0 0 0 0 0 0 -V 0 0 V 0 0 0 0 0 ↵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0↵
```↵
↵
you can actually extend this to 3D array (worth mentioning).↵
↵
↵
problem solving↵
==================↵
↵
[CSES-1662](https://cses.fi/problemset/task/1662)↵
↵
[spoj-CSUMQ](https://www.spoj.com/problems/CSUMQ/)↵
↵
[CF-835C](https://codeforces.me/problemset/problem/835/C)↵
↵
[CF-1398C](https://codeforces.me/problemset/problem/1398/C)↵
↵
[CF-1291D](https://codeforces.me/problemset/problem/1291/D)↵
↵
[AC-abc164D](https://atcoder.jp/contests/abc164/tasks/abc164_d)↵
↵
[CF-2072D](https://codeforces.me/contest/2072/problem/D)↵
↵
[CF-1501B](https://codeforces.me/problemset/problem/1501/B)↵
↵
[CF-433B](https://codeforces.me/contest/433/problem/B)↵
↵
[CF-296C](https://codeforces.me/contest/296/problem/C)↵
↵
[CF-816B](https://codeforces.me/contest/816/problem/B)↵
↵
[CF-1722E](https://codeforces.me/problemset/problem/1722/E)↵
↵
[CF-1837D](https://codeforces.me/problemset/problem/1837/D)
↵
this blog was made to summarize HCPC-2025 training for prefix sums in Homs university / Syria.↵
↵
overview↵
==================↵
###1. what is prefix sum?↵
###2. get range sum in $O(1)$↵
###3. find number of sub arrays with sum equal to $x$ (map trick)↵
###4. even more prefix sums↵
↵
lets start:↵
↵
###1. what is prefix sum?↵
↵
prefix sum of an array a of size $n$ is another array of size $n+1$ as follows:↵
↵
```↵
a(1) a(2) a(3) ... a(n)↵
p(0)=0 p(1)=a(1) p(2)=a(1)+a(2) p(3)=a(1)+a(2)+a(3) ... p(n)=a(1)+a(2)+...+a(n)↵
```↵
↵
so in general $p(i)$ contains the sum of all elements up to $i$↵
↵
and we introduce another element at the front representing the empty prefix↵
↵
we can build prefix sum array in simple one line of code↵
↵
```↵
for(int i=1;i<=n;i++)p[i]=p[i-1]+a[i];↵
```↵
↵
this is the only info we care about (for now).↵
↵
↵
###2.get range sum in $O(1)$↵
↵
as we want the sum in range $[L,R]$ ↵
↵
we realize that it is the same as $p(R)-p(L-1)$↵
↵
```↵
a(L)+a(L+1)+...+a(R)=(a(1)+a(2)+...+a(L-1)+a(L)...+a(R))-(a(1)+a(2)+...+a(L-1)) = p(R)-p(L-1)↵
```↵
↵
###3. find the number of sub arrays with sum equal to $x$↵
↵
given the array $a$ of size $n$↵
↵
every sub array sum is represented by two prefix sums $p(L-1),p(R)$↵
↵
first we initialize a map↵
↵
```↵
map<int,int> cnt;↵
```↵
↵
and loop through the array↵
↵
lets say we are considering index $i$↵
↵
at this point every prefix sum $p(j)$ such that $j<i$ is considered in the map↵
↵
it is necessary to consider the empty prefix at first↵
↵
```↵
cnt[0]=1;↵
```↵
↵
and then at each index $i$↵
↵
we do *something to get all sub arrays ending at index $i$ and have the sum equal to $x$ count and add it to the final answer↵
↵
and then do↵
↵
```↵
cnt[p[i]]++;↵
```↵
↵
what to *do each time?↵
↵
well we want the following equation $ p(i)-V=x $ when V is the value that we are searching↵
↵
then $V=p(i)-x$ ↵
↵
so we simply add $cnt[p[i]-x]$ to the final answer each time↵
↵
note that $V=p(L-1)$ that's why we considered the empty prefix at the first place↵
↵
there is a [problem](https://cses.fi/problemset/task/1661) at CSES mentioning this trick ↵
↵
###4. even more prefix sums↵
↵
here i will mention other prefix stuff that might be useful to use later,↵
↵
####1.prefix xor↵
↵
we can create an array containing the xor of each prefix, this way we can get the xor of any range↵
↵
```↵
for(int i=1;i<=n;i++)p[i]=p[i-1]^a[i];↵
//xor of a range [L,R] is p[R]^p[L-1]↵
```↵
↵
this is possible because ↵
↵
```↵
X^X=0 , A^B=B^A , X^0=X↵
```↵
↵
####2.prefix $mul$,$and$ , $or$ , $max$ , $min$ , $gcd$ and rarely $lcm$↵
↵
these queries are sadly not usual to get in a range as we will need advanced data structures (aka sparse table) to get them in $O(1)$ (or $log(n)$ in case of gcd,lcm)↵
↵
but you can get them in $log(n)$ complexity by using segment trees (out of topic but worth mentioning)↵
↵
if we want $mul$ in range we wouldd need to make sure a lot of things are satisfied , like there should not be zero (as it will make all prefixes ahead zeros and we cant cancel them),and overflow cannot happen (which could mean a lot of things), in our case we will focus on $mul$ in range with $mod$ so we can get inverse mod in $O(log(n))$,or even $O(1)$ if the mod is small enough↵
↵
it is also important to mention that we can get $(and,or)$ queries in range using simple prefix sum ↵
↵
by applying prefix sum on each bit as follows:↵
↵
```↵
for(int j=0;j<30;j++){↵
for(int i=1;i<=n;i++){↵
p[j][i]=p[j][i-1]+((a[i]>>j)&1);↵
}↵
}↵
```↵
↵
and then we can get $or$ or $and$ queries in a range $[L,R]$ as follows:↵
↵
```↵
int AND(int L,int R){↵
int res=0;↵
for(int j=0;j<30;j++){↵
if(p[j][R]-p[j][L-1]==R-L+1)res+=1<<j;↵
}↵
return res;↵
}↵
↵
int OR(int L,int R){↵
int res=0;↵
for(int j=0;j<30;j++){↵
if(p[j][R]-p[j][L-1]>0)res+=1<<j;↵
}↵
return res;↵
}↵
```↵
↵
but in certain problems it is enough to get them in a prefix (or a suffix maybe?)↵
↵
####3. 2D prefix sum↵
↵
the idea is we want to get sum in a rectangle in $O(1)$↵
↵
given the 2D array $a$ of $n$ rows and $m$ columns ↵
↵
```↵
a(1,1) a(1,2) ... a(1,m)↵
a(2,1) a(2,2) ... a(2,m)↵
...↵
a(n,1) a(n,2) ... a(n,m)↵
```↵
↵
we do a prefix sum on each row of $a$ first↵
so that↵
↵
```↵
p(i,j)=a(i,1)+a(i,2)+...+a(i,j)↵
```↵
↵
and then we do another prefix sum on columns of $p$↵
so that↵
↵
```↵
s(i,j)=p(1,j)+p(2,j)+...+p(i,j)↵
```↵
↵
actually we don't need two more arrays for that, we can simply apply these operations on the same array twice,↵
or one more array just to keep the original array.↵
↵
the code is as follows:↵
↵
```↵
for(int i=1;i<=n;i++)↵
for(int j=1;j<=m;j++)p[i][j]=a[i][j]+p[i][j-1];↵
↵
for(int j=1;j<=m;j++)↵
for(int i=1;i<=n;i++)p[i][j]+=p[i-1][j];↵
``` ↵
↵
we can get sum of elements in a rectangle with upper left corner at $(i,j)$ and with $x$ rows and $y$ columns like this↵
↵
```↵
p[i+x-1][j+y-1]-p[i+x-1][j-1]-p[i-1][j+y-1]+p[i-1][j-1]↵
```↵
↵
using inclusion exclusion principle (which is out of topic right now)↵
↵
but i can explain why this is true↵
↵
let the array $f$ represent how may times we added an element from the array $a$↵
↵
first each $f(i,j)=0$↵
↵
i will add each component to see how the frequency of elements change↵
↵
notice that adding $p(i,j)$ represents increasing the value of $f(i1,j1)$ $i1<=i&&j1<=j$ by one ↵
↵
```↵
i=2,j=2,x=4,y=3↵
+p[i+x-1][j+y-1] -p[i+x-1][j-1] -p[i-1][j+y-1] +p[i-1][j-1]↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 -1 0 0 0 0 0 0 0 0 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0↵
↵
```↵
↵
####4.
↵
the idea is simple↵
↵
given an array of zeros $a$↵
↵
```↵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0↵
``` ↵
↵
you can add $V$ to a range $[L,R]$ by adding $V$ to $a(L)$ and subtracting $V$ from $a(R+1)$↵
↵
```↵
0 0 0 V 0 0 0 0 0 -V 0 0 0 0 0↵
```↵
↵
and then applying prefix sum on the array↵
↵
```↵
0 0 0 V V V V V V 0 0 0 0 0 0 0↵
```↵
↵
well that is not useful when talking about one query , the thing is you can add multiple values to multiple ranges and then apply prefix sum , this is considered offline approach in multiple cases.↵
↵
####5.
↵
adding V to rectangle with upper left corner at $(i,j)$ and with $x$ rows and $y$ columns↵
↵
add V to both $(i,j)$ $(i+x,j+y)$ ↵
↵
subtract V from both $(i+x,j)$ $(i,j+y)$↵
↵
and then apply prefix sum 2D like we learned↵
↵
```↵
i=2,j=2,x=2,y=3↵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0↵
0 0 0 0 0 0 V 0 0 -V 0 V V V 0↵
0 0 0 0 0 0 0 0 0 0 0 V V V 0↵
0 0 0 0 0 0 -V 0 0 V 0 0 0 0 0 ↵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0↵
```↵
↵
you can actually extend this to 3D array (worth mentioning).↵
↵
↵
problem solving↵
==================↵
↵
[CSES-1662](https://cses.fi/problemset/task/1662)↵
↵
[spoj-CSUMQ](https://www.spoj.com/problems/CSUMQ/)↵
↵
[CF-835C](https://codeforces.me/problemset/problem/835/C)↵
↵
[CF-1398C](https://codeforces.me/problemset/problem/1398/C)↵
↵
[CF-1291D](https://codeforces.me/problemset/problem/1291/D)↵
↵
[AC-abc164D](https://atcoder.jp/contests/abc164/tasks/abc164_d)↵
↵
[CF-2072D](https://codeforces.me/contest/2072/problem/D)↵
↵
[CF-1501B](https://codeforces.me/problemset/problem/1501/B)↵
↵
[CF-433B](https://codeforces.me/contest/433/problem/B)↵
↵
[CF-296C](https://codeforces.me/contest/296/problem/C)↵
↵
[CF-816B](https://codeforces.me/contest/816/problem/B)↵
↵
[CF-1722E](https://codeforces.me/problemset/problem/1722/E)↵
↵
[CF-1837D](https://codeforces.me/problemset/problem/1837/D)
