### peltorator's blog

By peltorator, 5 weeks ago, translation,

Hi!

I continue to make videos on algorithms. This time the topic is more basic. In this video, I talk about prefix sums and how they can help you to find sum on segments. You can also learn from this video how to easily generalize prefix sums for 2D, 3D, 4D, etc. cases. In addition, we'll also talk about a simple concept named difference array, which can easily help in some sorts of situations where it seems like you need some complex data structures. And in the end, we'll learn how to add constants, arithmetic progressions, and even quadratic functions to a segment of an array.

Link to the video

The video is in Russian but English subtitles are available. I'd be glad if you watch the video and leave a comment below with your impressions, thoughts, and ideas for future videos. You may also want to text me on telegram if you didn't understand something or you have any questions. I'll be glad to answer!

I'm sorry you need to watch it with subtitles but I'm gonna make an English channel soon. So stay tuned!

If you didn't see it already, I also have a video on disjoint sparse table: here.

Codeforces group with a contest

My realizations:

1D prefix sums

1D prefix sums with structures

2 methods for finding 2D prefix sums: one, two

1D difference array

1D difference array with structures

• +365

 » 5 weeks ago, # |   +98 Roses are red, violets are blue, the blog is in English, then why not the video in English too?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +38 I'm sorry :)This blog is in Russian too. English videos are coming.
•  » » » 5 weeks ago, # ^ |   0 will you plan any gym contests in English ?
•  » » » » 5 weeks ago, # ^ |   0 I may translate problems into English if you want. But they have pretty obvious statements, so you can just use google translator.
•  » » » » » 5 weeks ago, # ^ |   0 Yeah, I can use translator for cause
•  » » » 5 weeks ago, # ^ |   0 Tried to watch with English subtitles but didn't understand a thing. waiting for english video
•  » » 5 weeks ago, # ^ |   +75 Roses are red, violets are blue, the video may be in Russian, but there are English subtitles too.
 » 5 weeks ago, # |   +24 3b1b vibes.
•  » » 5 weeks ago, # ^ |   +22 I use his library!
 » 5 weeks ago, # |   +13 Love to watch your English channel.
•  » » 5 weeks ago, # ^ |   +21 Thanks. I'm gonna make an English channel soon.
 » 5 weeks ago, # |   +16 If you can make a video in English then it would be more helpful for a larger audience.
•  » » 5 weeks ago, # ^ |   +22 Coming soon!
 » 5 weeks ago, # | ← Rev. 2 →   +19 I rarely see such a well written code on this platform. Good job! Also great job for the tutorial, and please continue to make these in English because they are so good. And of course you will attract larger audience.
•  » » 5 weeks ago, # ^ |   0 Thanks!
 » 5 weeks ago, # |   +10 Wow! Manim in action. Are you using manim community version? Mind sharing the code?
•  » » 5 weeks ago, # ^ |   0 No. I use vanilla manim. I saw that there are some cool features in the community version, but I didn't dive deep into it yet.
 » 5 weeks ago, # | ← Rev. 2 →   +11 Wow! I skimmed through parts of the video and this looks pure gold. I have linked this blog in one of the blogs I wrote on the same topic (albeit with some easier concepts) and one of the manim video editorials of a problem using this concept of difference array. Keep creating!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, I used your blog post when I was preparing for this video. I also mentioned you at the end of my video and in the video description :)Thank you very much for your work!
•  » » » 5 weeks ago, # ^ |   +10 Oh, that's very nice to know when someone else builds upon your work. And thanks for the video mention, I just took a look :)
 » 5 weeks ago, # |   +10 Wow, this is something I have been longing for unknowingly (Half closed Intervals mainly, I have seen pros use it and neal used it to solve problems in his streams of contest too).
 » 5 weeks ago, # | ← Rev. 2 →   0 thank you so much. I have solved Forest Queries problem using 2D prefix sum after watching your video. thank you again!!
•  » » 5 weeks ago, # ^ |   0 I'm glad it helped you!
 » 5 weeks ago, # |   +10 In problem C, what's the form of the query?l_1 r_1 l_2 r_2 l_3 r_3 l_4 r_4 l_5 r_5orl_1 l_2 l_3 l_4 l_5 r_1 r_2 r_3 r_4 r_5if first one is the correct form, then how the answer for the second query is 32?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 Yeah, you're right. The second one is correct. I'm sorry, I'll change it.UPD: fixed
 » 4 weeks ago, # |   0 This wiki gives a clear explanation in details.