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