Префиксные суммы, разностные массивы и сила полуинтервалов

The English version is below.

Привет! Я Егор. В этом видео я рассказываю про префиксные суммы и разностный массив. Это очень простые концепции, которые помогают легко решать задачи, в которых на первый взгляд нужны сложные структуры данных. Надеюсь, это видео вам покажется полезным. На этом канале я собираюсь делать анимированные видео, объясняющие разные алгоритмы и структуры данных. Я собираюсь затронуть как самые базовые темы: бинарный поиск, сортировки; так и продвинутые: disjoint sparse table, segment tree beats, heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие. Если вам это интересно, подписывайтесь на канал :) Можете предлагать темы, на которые вы хотели бы увидеть видео, в комментариях к этому видео или лично мне в телеграме. Также можете писать мне, если чего-то не поняли или у вас есть какие-то вопросы. С радостью отвечу! Успехов на контестах!

Контест на codeforces:

Мои реализации алгоритмов из видео:

Поиск двумерных префиксных сумм двумя методами:

Статья the_algorithmic_eye:

Канал the_algorithmic_eye на youtube:

Хочу выразить огромную благодарность Гранту Сандерсону — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео:

Содержание:

00:00 - Вступление
00:25 - Определение префиксных сумм, и почему мы используем полуинтервалы
02:18 - Построение одномерных префиксных сумм
04:10 - Пара слов про префиксные суммы на отрезках
05:15 - Поиск суммы на отрезке за O(1)
07:24 - Что насчет префиксных минимумов?
08:35 - Что насчет префиксных ксоров?
10:10 - Задача: подотрезок нулевой суммы
11:28 - Определение двумерных префиксных сумм
12:40 - Построение двумерных префиксных сумм
14:03 - Рекуррентная формула для поиска двумерных префиксных сумм
15:28 - Поиск суммы на подпрямоугольнике за O(1)
17:46 - Трехмерный случай и обобщение на большие размерности
20:34 - Разностный массив
22:04 - Прибавление константы на отрезке за O(1)
24:48 - Прибавление арифметической прогрессии на отрезке за O(1)
27:32 - Прибавление на подпрямоугольнике за O(1)
29:30 - Заключение

Мои контакты:

telegram:

codeforces:

instagram:

The English version:

Codeforces contest:

My implementations of algorithms from this video:
Finding 1D prefix sums:

Struct-based prefix sums for finding sum on segments:

2 methods for finding 2D prefix sums:

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:

the_algorithmic_eye's article:

the_algorithmic_eye's youtube channel:

Hi! My name is Egor. In this video, I'm talking about prefix sums and difference arrays. They are super simple but they can easily help in some sorts of situations where it seems like you need some complex data structures. I hope you find this video helpful. I'm gonna make more videos in the future. Both on basic algorithms such as binary search, sorting, etc., and also some advanced topics such as disjoint sparse table, segment tree beats, 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.

Reach me out on:
telegram:

codeforces:

instagram:

Or peltorator at any platform

[peltorator]

18:42 первое синее слагаемое должно быть b[rx][ly][lz], а не b[rZ][ly][lz], конечно. Спасибо Еркебулану Адильхану за то, что он это заметил!

[ИльяЛомоносов-юм]

Я думал, что это перевод 3blue1brown. Был даже на момент возмущён -- как так, перевёл, а ссылку не даёшь. А когда обнаружил, что твоя работа, то проникся большим уважением -- качественный контент, респект.

[rentbest]

Ты просто лучший, я два дня не мог решить задачу, после твоих объяснений снес свой код с костылями на 60+ строк и написал решение за час на 20 строк чистого кода

[justmarfix]

Спасибо за объяснение материала, всё очень качественно и понятно!

[minhazulislam]

Not a Russian speaker, but I must say this.
The way you used manim is really neat!

[TheAlgorithmicEye]

It feels so nice to see the users of manim grow and put it to good use across various subjects. Good one @peltorator and the practice CF contest is icing on the cake :)

[ilyasqalandarzoda]

Nice, ждем более углубленное изучение ДП, графы и все такое.
Спасибо за прекрасный контент.

[Mellivora-uf]

Объяснение довольно редких тем просто шикарное! Будет круто, если продолжишь делать такие видео

[ayubkosimov]

Егор, реально круто объясняешь. Удачи тебе! Ждем новых видосов

[Artem-krpb]

Офигеееть! Ты так классно объясняешь, всё понятно и слушать приятно. Спасибо большое за труд :)

[НиколайАсландуков]

Прекрасная подача материала! Большое спасибо!

[belov_dev]

Браво! Спасибо большое, сейчас активно готовлюсь к собесам и подтягиваю спортивную прогу. Отлично тему раскрыл!

[himanshuverkiya]

Thank you a lot, sir. It'll be very beneficial for beginners like me >_<

[DmitriyBlokhin]

Большое уважение за такой контент, и спасибо!

[HelloWorld-syyc]

well done, don't give up. So much appreciated! Hope, that this amount of help u'll get as a doubled!

[AT_geometr]

Спасибо! Очень хорошее видео, будут ли ещё уроки?

[dimss]

У вас будут выходить только подобные уроки, или ещё что-то будет? Будут например разборы задач с олимпиад, контестов?

[myxail]

(спойлер) В первом домашнем задании можно для даного значения префиксной суммы держать индекс первого ее выступления в одной хэш таблице и индекс последнего. Тогда в конце можно посчитать максимум из разниц значений в этих таблицах. Касательно второго задания, то по моему можно для каждого индекса посчитать разницы префиксных сумм двух массивов на данной позиции и проверить, есть ли повторения

[MohamedElsayed-pboj]

I dont speak Russian and immediately saw the depth of explanation (just by the images). Is there any chance for this to be in English?

[ПауверТзен]

Разбор домашнего задания будет? Хотел спросить просто с нахождением макс отрезка нужно делать цикл находить в нем макс число (если не найдется отрезок больше), дальше для каждого элемента делать цикл и находить префикс с последнего элемента и уменьшать на 1 и опять каждый результат сравнивать через if или max? Если я мыслю как то не так дайте подсказку пожалуйста.