Привет!
Я продолжаю делать видео по алгоритмам, на этот раз тема более базовая. В этом видео я рассказываю про префиксные суммы и то, как с их помощью можно искать сумму на отрезке. Также вы сможете узнать, как легко обобщать префиксные суммы для двумерного, трехмерного, четырехмерного и т.д. случаев. Кроме этого, мы еще поговорим про такую простую концепцию как разностный массив, которая помогает очень легко решать задачи, в которых с первого взгляда хочется использовать всякие сложные структуры данных типа дерева отрезков. И в конце научимся прибавлять на отрезке в массива константы, арифметические прогрессии и даже квадратичные функции.
Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями или идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!
Если вы еще не видели, можете также посмотреть мое видео про disjoint sparse table тут.
Реализации можно посмотреть по ссылкам:
Поиск одномерных префиксных сумм
Префиксные суммы на структурах для поиска суммы на отрезке
Поиск двумерных префиксных сумм двумя методами: раз, два
Для построения одномерных префиксных сумм/ксоров можно также использовать
std::partial_sum: https://ideone.com/JttzK4Да, точно, это классный C++ хак. Спасибо! Еще с ним всяких прикольных эффектов можно добиться, если использовать некоммутативную операцию.
Roses are red, violets are blue, the blog is in English, then why not the video in English too?
I'm sorry :)
This blog is in Russian too. English videos are coming.
will you plan any gym contests in English ?
I may translate problems into English if you want. But they have pretty obvious statements, so you can just use google translator.
Yeah, I can use translator for cause
Tried to watch with English subtitles but didn't understand a thing. waiting for english video
Roses are red, violets are blue, the video may be in Russian, but there are English subtitles too.
3b1b vibes.
I use his library!
Love to watch your English channel.
Love to watch your English channel.
Thanks. I'm gonna make an English channel soon.
If you can make a video in English then it would be more helpful for a larger audience.
Coming soon!
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.
Thanks!
Wow! Manim in action. Are you using manim community version? Mind sharing the code?
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.
Большое спасибо за качественный материал,мне как начинающему было очень интересно и самое главное полезно,надеюсь вы будете продолжать свою образовательную деятельность.С нетерпением жду следуйщего урока)
Очень рад слышать
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!
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!
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 :)
Как же Сергей Орбитаев пиарится
Но с другой стороны заслужено
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).
thank you so much. I have solved Forest Queries problem using 2D prefix sum after watching your video. thank you again!!
I'm glad it helped you!
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_5or
l_1 l_2 l_3 l_4 l_5 r_1 r_2 r_3 r_4 r_5if first one is the correct form, then how the answer for the second query is 32?
Yeah, you're right. The second one is correct. I'm sorry, I'll change it.
UPD: fixed