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

The English version is below.

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

Контест на codeforces:
https://codeforces.com/group/1rv4rhCs...

Мои реализации алгоритмов из видео:
Поиск одномерных префиксных сумм: 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:
   / @thealgorithmiceye  

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

https://github.com/3b1b/manim
   / @3blue1brown  

Содержание:

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/peltor...

instagram:
  / peltorator  


The English version:

Codeforces contest:
https://codeforces.com/group/1rv4rhCs...

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

   / @3blue1brown  

the_algorithmic_eye's article:
https://codeforces.com/blog/entry/86420

the_algorithmic_eye's youtube channel:
   / @thealgorithmiceye  

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/peltor...

instagram:
  / peltorator  

Or peltorator at any platform