Привет!
Я сделал видео про disjoint sparse table. Это некоторое обобщение обычного sparse table'а, который расширяет возможности его применения.
Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями или идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!
Я собираюсь регулярно выпускать видео по алгоритмам в будущем. Как по основам (префиксные суммы, бинарный поиск, сортировки и тд), так и по провинутым темам (heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие). Так что если вам это интересно, подписывайтесь на канал, чтобы их не пропустить!
Реализации можете посмотреть по ссылкам:
Без дополнения до степени двойки
Спасибо за внимание!
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:
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.
There is the exact same problem you mentioned (namely, product on a subsegment online with composite modulo): https://www.codechef.com/NOV17/problems/SEGPROD
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
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.
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?
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.
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.
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.
Some of your links are not clickable because of
​character at the end, maybe retyping the last characters of the links would help.Oh, yeah, it worked. Thanks!
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.
Seems like different people know this idea but call it differently. Thanks for sharing! Maybe from this moment, the name will stick.
Awesome! Can you share your workflow to sync audio and video?
Hi! What do you mean by "sync audio and video"?
Like, how do you edit the video such that the right animation is played at the right time? What is your setup?
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.
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.
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.
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
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.
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.
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.
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)