peltorator's blog

Video about prefix sums, difference array and the power of half-closed intervals
By peltorator, 3 years ago, translation, In English

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

  • Vote: I like it
  • +365
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
3 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Roses are red, violets are blue, the blog is in English, then why not the video in English too?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +38 Vote: I do not like it

    I'm sorry :)

    This blog is in Russian too. English videos are coming.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      will you plan any gym contests in English ?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I may translate problems into English if you want. But they have pretty obvious statements, so you can just use google translator.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, I can use translator for cause

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Tried to watch with English subtitles but didn't understand a thing. waiting for english video

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    Roses are red, violets are blue, the video may be in Russian, but there are English subtitles too.

    → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

3b1b vibes.

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Love to watch your English channel.

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

If you can make a video in English then it would be more helpful for a larger audience.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Wow! Manim in action. Are you using manim community version? Mind sharing the code?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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 :)

      → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

thank you so much. I have solved Forest Queries problem using 2D prefix sum after watching your video. thank you again!!

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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_5

or

l_1 l_2 l_3 l_4 l_5 r_1 r_2 r_3 r_4 r_5

if first one is the correct form, then how the answer for the second query is 32?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Yeah, you're right. The second one is correct. I'm sorry, I'll change it.

    UPD: fixed

    → Reply