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 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.offline 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. offline 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

spoj-CSUMQ

CF-835C

CF-1398C

CF-1291D

AC-abc164D

CF-2072D

CF-1501B

CF-433B

CF-296C

CF-816B

CF-1722E

CF-1837D

hello codeforces

yesterday i noticed that someone from my friends solved problem D in 8 minutes.

well this friend is known in our telegram training group to be a cheater.

i refused that fact cuz there is no direct proof.

while i was looking at his code i noticed that some code was copied and pasted 3 times in different functions doing nothing.

i knew that was not normal , so i needed a proof now.

so i decided to look at problem D solves and was suprised that so many solutions are alike in a way, but different only in variable names, and some of them were in a straight one line of code , but the same idea over and over.

you can check some examples

308151686 308117651 308160744 308153550 308165846 308152360 308142455 308171609 308166500 308167550 308158553 308146140 308144552 308158580 308144531 308170236 308171447 308138274 and best for last 308165802

you can notice the large similarity between them,,

most of them were submitted at the near end of the contest,

these acts are not acceptable in this community, so many coders leave CP because others are cheating and he is getting negative delta over and over while not cheating.

i would like to notice MikeMirzayanov to these acts.

update:

the same person cheated today

i invastigated more and found a code on a telegram group

further more

here is his submission 308347774

here is the code on the telegram group

D1?#include <bits/stdc++.h>
using namespace std;
 
int f(long long m, long long n, int B, const vector<int>& p) {
    if (m <= n) return p[(int)m];
    return (m & 1LL) ? B : B ^ f(m / 2, n, B, p);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long l, r;
        int n;
        cin >> n >> l >> r;
        
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
 
        if (l <= n) {
            cout << a[(int)l] << "\n";
            continue;
        }
 
        vector<int> p(n + 1);
        p[0] = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] ^ a[i];
        }
 
        int fn = p[n];
        int B = (n & 1) ? fn : fn ^ p[n / 2];
        long long m = l / 2;
        
        cout << f(m, n, B, p) << "\n";
    }
    
    return 0;
}

you don't need to be smart to know whats happening , these codes are being distributed through youtube and telegram channels, too bad we can't stop them , but at least cheaters don't deserve to get to expert by cheating and get away with it.

note: i will share the same codes that were shared for B C

i don't care about A if you cheat A just get a life man.

Hello codeforces

I am burnet out and can't actually have fun solving problems,

The first motivation for me was that there are plenty of fun problems out there to solve

Furthermore i feel like i am not learning much ,

I know i know you will say (solve more) so get better by time and whatever ,

I have no problem in that

But somehow i think it is more fun to focus on some topic and burn it to the ground,

Is there any good topic to learn that has a lot of new helpfull tricks?