Please give some online judge problems in which prefix sum( also known as cumulative sum) technique is useful.

Thanks in advance.

# | User | Rating |
---|---|---|

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 206 |

2 | Monogon | 193 |

3 | SecondThread | 191 |

4 | pikmike | 188 |

5 | antontrygubO_o | 187 |

6 | vovuh | 185 |

7 | Ashishgup | 182 |

8 | Um_nik | 180 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

Please give some online judge problems in which prefix sum( also known as cumulative sum) technique is useful.

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2020 21:25:52 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Edit:Edit 2:thanks so much mr. Shinadul

He is Shahidul, not Shinadul lmao

How ignorant you are, if you can't even copy the name correctly

hush relaxxx it is just a name

do not take it to an argument, it's just a mistake, not smth that crushes the world. Take it easy!

A quite simple one: 816B — Karen and coffe

Easy problem of prefix sum https://codeforces.com/contest/1355/problem/C

Good One

This might help you while implementing`std::partial_sum( )`

296C Greg and Array

Also see this to practice range change in array per queries best solve through prefix sumhttps://www.hackerrank.com/contests/algoholic-contest-1/challenges/street-lights/problem

Constraints too large to use Prefix sum

Constraint for Ai1 ≤ Ai ≤ 10^9

Some DP + prefix sum : 479E - Riding in a Lift

PS : Sorry , but wasn't knowing that it's very old blog

Hey bro Old is GOLD ;)

;)

Problems sorted by difficulty.

Kuriyama Mirai's Stones

Vika and Squares

Balanced Tunnel

Karen and Coffee

Greg and Array

Valid Sets

Star Sky

Train Hard, Win Easy

Thank you for the difficulty order

Here is another easy one.

CF 363B — Fence

How can I solve "Vika and Squares" using prefix sum? I solved this problem using a constructive algorithm — 90242000

But want to solve it using prefix sum in order to learn it. Thank you.

Here are a couple of USACO problems:

http://www.usaco.org/index.php?page=viewproblem2&cpid=595

http://www.usaco.org/index.php?page=viewproblem2&cpid=104