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

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: Finding 1D difference array: Struct-based difference array for adding on segment: 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