peltorator's blog

Video about Disjoint Sparse Table or how to answer all queries in constant time
By peltorator, 4 years 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

Comments Comments (20)
| Write comment?
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

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

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

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

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

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

Amazing tutorial! You should make more. I loved the way you explained with the visuals. Really great work there. Also thanks for preparing the contest.

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

I've somewhat simplified the implementation here, albeit making it a bit less readable by using shorter names :) Sharing in case it helps future readers.

A few more things to note about this technique. Although it's a cool trick, it's also pretty much useless practically speaking. Because we can still use the regular sparse table to answer queries in O (log n) without partial overlaps, and that is pretty fast. I was able to pass all 4 problems in the contest this way, without using disjoint sparse tables.

The only valid use case I can think of is when there is going to be a large number of queries, like SEGPROD or also the first problem from the contest where Q=3*107. And even then, I believe most of the time we can use the regular sparse table as opposed to the discrete version.

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

    By that argument regular sparse tables are useless too, because you can just use segment trees (which is a good point). I personally think that disjoint sparse tables are kind of useless practically because

    1. Regular sparse table precalculation runs faster than the disjoint version
    2. Regular sparse table implementation is simpler
    3. In practice very few problems require the disjoint version. Sparse table is simply good enough for a lot of applications.

    However I still find the disjoint sparse table to be very interesting. I wonder if it is possible to make an implementation of disjoint sparse table that rivals the simplicity and speed of the regular sparse table.

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

      Yes, those are good points too. As for segment trees vs sparse tables, sparse tables have significant advantages over segment trees. They are simpler, faster, and queries are O(1) if overlaps are not an issue that is.

      And like you said, for most problems overlaps are fine. For queries on a static array, where overlapping is undesirable, most of the time we can just use a prefix array instead of the disjoint sparse table. Think sum, xor, polynomial hash, etc.

      TLDR, I don't think disjoint sparse tables are overall very useful because I have seen only a handful of problems requiring them. And I can't think of a valid use case unless the problem setter makes the time limit unnecessarily strict with the sole intent of disallowing regular sparse tables. Apart from that, the only valid use case I can think of is when squeezing a sub-optimal solution to pass in the rare scenario where overlapping ranges may be problematic, and we cannot use a prefix array too.

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

      Disjoint sparse tables are not that slow though. The implementation and simplicity do not differ significantly when compared with the normal one. Although, the non-disjoint version is very easy to understand and intuitive.

      I didn't do a thorough benchmark, but roughly my disjoint sparse table implementation is 1.5x slower than the normal one. Building the sparse table that is, queries should have the same performance.

      I think it can be improved but it won't add much value because if we need to use the disjoint version, usually building the table won't be the bottleneck.

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

        The way I think of it is that with segment trees, you do the majority of the work during queries. And for sparse tables you do a majority of the work at the precalculation.

        One big reason why sparse tables are so nice is because their precalculations can be done in a very fast and cache friendly way. (Unlike queries in a segment trees)

        → Reply