Prefix sums, difference array and the power of half-closed intervals

[@peltorator]

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

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

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

[@peltorator]

Спасибо :) Ну хоть это не перевод, но ссылка все такие есть!

[@rentbest]

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

[@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 :)

[@peltorator]

Thanks! I really like your content.

[@minhazulislam4682]

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

[@ayubkosimov199]

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

[@peltorator]

Спасибо!

[@justmarfix]

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

[@Artem-kr6pb]

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

[@peltorator]

Спасибо! Очень рад слышать.

[@redice8928]

Нихуя не понятно.

[@ilyasqalandarzoda7966]

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

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

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

[@peltorator]

Спасибо!

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

@@peltorator Есть ли шансы пройти тематический контест на CF с кодом на Python?

[@Mellivora-u3f]

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

[@sjdjjsjsjs3991]

Ну если алгоритмы изучать только видосикам да, а так база, которую изучают ещё на первом курсе

[@belov_dev]

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

[@DmitriyBlokhin]

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

[@ferume-oh3]

Топовый контент, большое спасибо!

[@himanshuverkiya]

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

[@chum_gum]

Канал супер! Мое увожение

[@Бытьили-е6д]

легенда, жалко что не снимает больше

[@HelloWorld-sy4yc]

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

[@peltorator]

Thanks!

[@fdshdsfdsqq]

кайф получил, эти анимации еще 😋😋😋

[@sovulken]

segment tree beats? мощно

[@peltorator]

Где? Будет! Но это очень большая тема, так что мне нужно много времени.

[@sei1ampo]

люблю тебя

[@AT_geometr]

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

[@peltorator]

Спасибо. Конечно, будут!

[@nihalk9069]

Thank you so much ❤️. It was useful

[@myxail0]

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

[@peltorator]

Да! Все правильно!

[@ГалинаКулакова-н8с]

Здравствуйте. Дайте пожалуйста подсказку по прибавлению квадратичной функции. Что-то не получается у меня(((

[@alexandersmirnov4274]

сделайте по дерево отрезков классно

[@learpcss9569]

10:53 почему с хэш-таблицей асимптотика будет O(n)? Ведь от коллизий в хэш-таблице никуда не деться и значит асимптотика с хэш-таблицей будет O(n^2) (на каждый n обращений к хэш-таблице, элемент придется искать линейное время). Или же я неправильно понимаю?

[@peltorator]

Хеш-таблица -- это структура данных, которая умеет сохранять и обращаться к элементам за ожидаемое время O(1). Я не совсем понял ваш комментарий. Коллизии могут быть, но они же не портят асимптотику, если размер хеш-таблицы будет достаточно большой (к примеру, 3 * n).

[@learpcss9569]

@@peltorator представим, что я составил хэш-функцию которая очень плохо распределяет различные ключи. Пусть на любой ключ она будет возвращать ноль. То бишь: m[10] и m[0] будут обращаться в одну и ту же нулевую ячейку. Ну и разрешаем коллизии с помощью открытой адресации. и получается так что с каждым поиском мне приходится перебирать с начала каждый элемент, пока не найду элемент с нужным ключом. итого каждый поиск в худшем случае будет O(n). Но в действительности хэш-функции не тупые же и стараются это делать равномерно. Итого в среднем действительно будет О(1) (что вы и назвали ожидаемым временем). Но на деле зачастую асимптотика подразумевает худший случай? На моем опыте многие образовательные сайты при использовании хэш-таблицы говорят, что асимптотика такая словно O(1) всегда гарантированно. И мне не понятно почему.

[@learpcss9569]

ну все же я к тому что коллизии могут портить асимптотику. ну в общем это и не сильно важно. спасибо большое за видео, у вас очень хорошая подача материала. (буквально полчаса назад увидел, что ваши видеоролики на codeforces висят на edu)

[@peltorator]

​@@learpcss9569 ​ Все таки стоит понимать разницу между "в худшем случае" и "есть вероятность, что работает долго". Мы можем так подобрать размер хеш-мапа и выбрать такую хеш-функцию, чтобы на ЛЮБОМ тесте наше решение работало за линейное время с вероятностью "1 - 1/2^100". То есть вероятеность того, что наше решение будет работать за квадрат, меньше, чем вероятность того, что во время выполнения нашей программы на компьютер упадет метеорит. Кажется, нас устраивает такой вариант. В нашем случае вне зависимости от данного нам теста наше решение работает с очень большой вероятностью за линейное время. Другое дело - это "тест худшего случая". К примеру, иногда сортировка пузырьком рабоает за линейное время, однако есть КОНКРЕТНЫЙ ТЕСТ, на котором достигается худшее время работы: O(n^2). И с этим ничего не поделаешь, оно будет O(n^2). В нашем же случае ситуация обстоит абсолютно не так. У нас решение работает всегда, но не детерминированно. Обычно именно это подразумевают, когда говорят, что рандомизированное решение работает за какую-то асимптотику: на любом тесте матожидание времени работы такое-то (а следовательно, по неравенству Маркова, вероятность того, что асимптотика будет очень большой, очень мала).

[@yashugarg9235]

Could you please explain the part :-> adding arithmetic progression to a segment of an array? Thanks

[@peltorator]

What do you want me to explain? You didn't understand some specific part of the video? If you take difference array of a difference array, then adding arithmetic progression to a segment is just changing 3 values.

[@yashugarg9235]

@@peltorator I find difficulty in this part only 24:48- Addition of an arithmetic progression for the segment O (1). But now I got it. Thanks for the video.

[@arzul5051]

годный контент

[@RudraSingh-pb5ls]

Are you going to release an English dubbed vudeo for this as well ?

[@peltorator]

Yes

[@RudraSingh-pb5ls]

@@peltorator thank you very much

[@shriramr8695]

@@peltorator When will you put the english video?Because I want to learn these topics now.

[@tommorfin3499]

​@@shriramr8695 this video already has english subtitles

[@MohamedElsayed-pb3oj]

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?

[@peltorator]

I wanted to translate it for a long time but I sadly didn't have a chance. I definitely will do it one day, but just not sure when! But right now you may check out subtitles. They should be good enough quality.

[@dimss4213]

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

[@peltorator]

Пока в планах не было, но это возможно.

[@abiwka]

20:19 в сумме написано b[rz][ly][lz], разве не b[rx][ly][lz]?

[@peltorator]

Ого, точно, да, спасибо! Не заметил ((

[@oleghools4177]

Еркебулан Адильхан

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

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

[@peltorator]

перебираем правую границу отрезка, тогда надо выбрать левую с минимальным значением префиксной суммы до правой. Можно перебирать правую границу слева направо и поддерживать одновременно самую маленькую префиксную сумму, которую мы уже видели.

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

@@peltorator #include #include using namespace std; int main() { int n; cin>>n; long a[n]; for(int i=0;i>a[i]; } long pref[n]; int m=-101000; int p2,i2; for(int i=0;i

[@tharunchowdary14]

Is this video available in english somewhere?

[@peltorator]

No, not yet.

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

Есть ли шансы пройти тематический контест на CF с кодом на Python?

[@peltorator]

Можно попытаться! Но чаще всего нет(

[@rizmo9125]

Откуда видос? Оригинал

[@peltorator]

Это оригинал.

[@mikhailivanovorz7270]

А можно автор канала ни лайк моему комментарию не поставит, ни комментировать этот комментарий не станет? Видео интересное, качественное, поучительное и красивое.

[@peltorator]

Нет, нельзя! Когда новые летсплеи?

[@iancu_de_hunedoara]

Umer?

[@Окорочок-н2в]

Леденящая лазурь, это правда ты?

[@peltorator]

Yes

[@Buttiya]

привет из 2025! я не могу пройти на пайтоне вторую задачу с контеста from sys import stdin def main(): n, m = map(int, stdin.readline().split()) a = [list(map(int, input().split())) for i in range(n)] q = int(stdin.readline()) a_new = [[0] * (m + 1) for _ in range(n + 1)] for x in range(n): for y in range(m): a_new[x + 1][y + 1] = a_new[x + 1][y] + a_new[x][y + 1] - a_new[x][y] + a[x][y] for _ in range(q): lxi, lyi, rxi, ryi = map(int, stdin.readline().split()) print(a_new[rxi][ryi] - a_new[lxi-1][ryi] - a_new[rxi][lyi-1] + a_new[lxi-1][lyi-1]) main() подскажите, как можно ускорить?

[@EugeneTheFirst]

Вот одна из причин почему современные программы жрут память как не в себя - потому что программеры не экономят память, а гонятся за скоростью, при этом ещё к тому же использую монструозные готовые библиотеки и занимая память ещё больше, работая на своем компе с большим количеством памяти не испытывают проблем, а обычным пользователям не хватает памяти, система свопится и программа безбожно тормозит

[@КириллБессонов-щ7щ]

Согласен👍👍👍 Некоторые программисты просто забывают подумать об обычных людях

[@semninrussia]

Это олимпиадное программирование как бы + обычно всё таки лучше улучшать скорость, а не память

[@EugeneTheFirst]

@@semninrussia если памяти у пользователя не хватает, то о скорости не может идти и речи

[@nx8wh]

я боюсь

[@redice8928]

Объяснения очень скучные и муторные. Не хватает музыкального фона

[@rizmo9125]

Лол, это было на ЕГЭ)

[@nx8wh]

e$aть