Segment Tree Beats: Segment Tree на стероидах. Часть 1

Hi! My name is Egor. I study at Saint Petersburg State University in Russia. In this video, i talk about a data structure called Segment Tree Beats. It helps to solve a lot of different problems that casual segment tree can't handle. We'll take a look at a few interesting problems such as taking all numbers on a segment modulo some number, Ji Driver Segment Tree and its variations with adding on a segment, and taking GCD on a segment. I hope you find this video helpful. 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 disjoint sparse table, heavy-light decomposition, link-cut tree, lambda optimisation, FFT, and so on. If you're interested, consider subscribing to my channel! If you have any questions you can contact me on telegram. Good luck with your contests. Codeforces contest: https://codeforces.com/group/1rv4rhCs... If you speak Russian here is the Russian version of this video:    • Segment Tree Beats: Дерево Отрезков На Сте...   Original article in English: https://codeforces.com/blog/entry/57319 Original article in Chinese: http://www.doc88.com/p-6744902151779.... Realisations of algorithms from this video: %= on a segment, = in a point, sum on a segment: https://pastebin.com/wabDfjKi Ji Driver Segment Tree (min= on a segment, sum on a segment): https://pastebin.com/bEEQsDr7 min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment: https://pastebin.com/UJhuFA3a Everything from the previous realisation but also GCD on a segment: https://pastebin.com/jDMC5R2T I want to thank Grant Sanderson (the author of the 3blue1brown youtube channel) for inspiration and the brilliant manim library, this video was made with: https://github.com/3b1b/manim    / @3blue1brown   Chapters: 00:00 - Intro 01:43 - General idea of Segment Tree Beats 05:19 - tagCondition and breakCondition 10:06 - %= on a segment 14:13 - Common, additional and dead-end vertices 19:40 - Ji Driver Segment Tree (min= on a segment) 24:27 - Extended Ji Driver Segment Tree (min=, += on a segment) 30:25 - += on a segment, GCD on a segment 35:33 - += and min= on a segment, GCD on a segment 39:25 - Outro Reach me out on: telegram: https://t.me/peltorator codeforces: https://codeforces.com/profile/peltor... instagram:   / peltorator   Or peltorator at any platform