peltorator's blog

By peltorator, 3 months ago, translation, In English

Hi!

I made a video on the disjoint sparse table. It's a generalization of a sparse table that expands the possibilities of its application.

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 gonna make more videos in the future. Both on basic algorithms such as prefix sums, binary search, sorting, etc., and also some advanced topics such as heavy-light decomposition, link-cut tree, lambda optimization, FFT, and so on. If you're interested, consider subscribing to my channel!

My disjoint sparse table realizations:

Easy one

Easy to use with templates

Without extending to the power of two

Codeforces group with contest

Good luck!

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

»
3 months ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

Nice video! I'm glad that someone has finally told the wide audience about disjoint sparse tree (which I always called "non-idempotent sparse tree"). I have a couple of comments to add:

  1. I was initially told about this ds without a concept of segment tree. Instead, one can enumerate the (imaginary) bars between positions:
0 1 2 3 4 5 6 7 8 9 ...
|3|1|4|1|5|9|2|6|5|3...

Now it's easy to see that on each (nonempty) subsegment there is the only bar with the greatest power of two in its factorization (basically, the greater this power is, the higher is the level in your segment tree where you store it). This approach gives another way to think of a bit formula of access index.

  1. There is the exact same problem you mentioned (namely, product on a subsegment online with composite modulo): https://www.codechef.com/NOV17/problems/SEGPROD

  2. The manim creator you mentioned is Grant Sanderson, not Grant Sanders

P.S.: it was not intentional that the numeration in this comment is broken

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +34 Vote: I do not like it

    Thank you for your comment! Yeah, your approach is really nice. It's always interesting to watch something from different perspectives.

    And thank you for the name correction :) I fixed it now. Probably I should eat less often at KFC.

»
3 months ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

At around minute 16 your (English) CC switch to Russian.

Otherwise, great video! Never thought about this idea. By the way, how long did it take you to animate everything?

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it +43 Vote: I do not like it

    Oh wow! Thank you for noticing it. English subtitles were autogenerated from Russians. I'll investigate this problem.

    I don't know how long it took specifically to animate it but I spent around 80 hours overall on this video including learning how to use manim library.

    Thank you so much for your comment!

    UPD: I fixed English subtitles.

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

In the future, will you consider making videos in english? I know that there are english subtitles, but I prefer to be focusing on the diagrams and animations instead of the subtitles and what they say. Well, I guess that this also depends on your viewer base.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    Yeah, I understand that it's hard to watch a Russian video with English subtitles especially if they are autogenerated. But it's better than nothing I suppose.

    I'm definitely considering this opportunity. Maybe someday in the future, I'll do it. Thank you for your suggestion! Stay tuned.

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Some of your links are not clickable because of ​ character at the end, maybe retyping the last characters of the links would help.

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

USACO Guide also has a blog that describes a similar idea (its pretty much the same, but they implement it differently): link

The video was very well made btw.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    Seems like different people know this idea but call it differently. Thanks for sharing! Maybe from this moment, the name will stick.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome! Can you share your workflow to sync audio and video?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hi! What do you mean by "sync audio and video"?

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

      Like, how do you edit the video such that the right animation is played at the right time? What is your setup?

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it +21 Vote: I do not like it

        I use manim python library for animation. Then I record audio and after that, I can manage timings in my code so that they synchronize.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think he would let the animation play and voice-over it.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice tutorial.... learned a lot of new stuff.... One request. Can anyone provide the code for the last two problems showed in the video? Thank You.