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

The English version is below. Привет! Я Егор. В этом видео я рассказываю про префиксные суммы и разностный массив. Это очень простые концепции, которые помогают легко решать задачи, в которых на первый взгляд нужны сложные структуры данных. Надеюсь, это видео вам покажется полезным. На этом канале я собираюсь делать анимированные видео, объясняющие разные алгоритмы и структуры данных. Я собираюсь затронуть как самые базовые темы: бинарный поиск, сортировки; так и продвинутые: disjoint sparse table, segment tree beats, heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие. Если вам это интересно, подписывайтесь на канал :) Можете предлагать темы, на которые вы хотели бы увидеть видео, в комментариях к этому видео или лично мне в телеграме. Также можете писать мне, если чего-то не поняли или у вас есть какие-то вопросы. С радостью отвечу! Успехов на контестах! Контест на codeforces: https://codeforces.com/group/1rv4rhCsHp/contests Мои реализации алгоритмов из видео: Поиск одномерных префиксных сумм: https://pastebin.com/MjxG7y43 Префиксные суммы на структурах для поиска суммы на отрезке: https://pastebin.com/062t332c Поиск двумерных префиксных сумм двумя методами: https://pastebin.com/a09xCDGw https://pastebin.com/Yezy0Lkb Поиск одномерного разностного массива: https://pastebin.com/fXpwTRiK Разностный массив на структурах для прибавления на отрезке: https://pastebin.com/fbmveX6Q Статья the_algorithmic_eye: https://codeforces.com/blog/entry/86420 Канал the_algorithmic_eye на youtube: https://www.youtube.com/channel/UCvNmvZRPkkmkAtAF_mo53tw Хочу выразить огромную благодарность Гранту Сандерсону — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео: https://github.com/3b1b/manim https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw Содержание: 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: https://t.me/peltorator codeforces: https://codeforces.com/profile/peltorator instagram: https://www.instagram.com/peltorator/ The English version: Codeforces contest: https://codeforces.com/group/1rv4rhCsHp/contests My implementations of algorithms from this video: Finding 1D prefix sums: https://pastebin.com/MjxG7y43 Struct-based prefix sums for finding sum on segments: https://pastebin.com/062t332c 2 methods for finding 2D prefix sums: https://pastebin.com/a09xCDGw https://pastebin.com/Yezy0Lkb Finding 1D difference array: https://pastebin.com/fXpwTRiK Struct-based difference array for adding on segment: https://pastebin.com/fbmveX6Q 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 https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw the_algorithmic_eye's article: https://codeforces.com/blog/entry/86420 the_algorithmic_eye's youtube channel: https://www.youtube.com/channel/UCvNmvZRPkkmkAtAF_mo53tw 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: https://t.me/peltorator codeforces: https://codeforces.com/profile/peltorator instagram: https://www.instagram.com/peltorator/ Or peltorator at any platform