Бро, давай вторую часть. Сейчас в последнее время забил на алгоритмическую прогу, но благодаря твоему видео, появилось неумолимое желание изучить, узнать ещё больше подобного материала. Спасибо!
Огромное спасибо, очень полезное видео! 30:50 - если я правильно понял Ф+ = QlogN, а написано N + QlogN(Ф0 + Ф+), передаю привет из параллели А тинькофф.
когда срабатывает tagCondition мы обновляем значение суммы в вершине дерева отрезков, но после этого когда будет запрос о сумме, если отрезок этого запроса будет пересекать отрезок в котором мы ранее сделали присвоение, то он выдаст неправильную сумму же, разве нет? вроде это тут говорится что эти данные потом pushатся, но чтобы их запушить нужно линейное время чтобы пропушить его во всех его детей или я чего то не понимаю
Мы проталкиваем информацию только в непосредственных детей. Это занимает константное время. Когда понадобится, они протолкнут эту информацию еще дальше. Советую прочитать что-нибудь про деревья отрезков с массовыми обновлениями. К примеру: e-maxx.ru/algo/segment_tree
@@peltorator я кажется понял, изменения в детях произойдут только когда нужно будет в них спуститься в последующих вызовах дерева отрезков. Спасибо мужик твои видосы топовые
Если ты считаешь какую-то функцию, которую называешь потенциалом, как можно сказать что-то про ассимптотику? Например, когда ты делаешь %= на отрезке, как связана сумма логорифмов элементов по всем вершинам связана с количеством операций? Можно вообще считать любую функцию и если она мало меняется, то и ассимптотика маленькая?
Мы следим за неким потенциалом. Мы знаем, что за все время он может увеличиться максимум на X. При этом каждый раз, когда мы делаем лишнюю операцию какую-то, мы уменьшаем потенциал на единицу. Значит, мы сделаем максимум X лишних операций. Так что асимптотику можно оценить как O(X).
А если задачку с %= модифицировать до просто нахождение суммы на отрезке, образно говоря, мы сначала применяем первую операцию потом 3, а потом возвращаем массив в исходное положение, то как такую модификацию можно решить с помощью этого дерева?
Я не совсем понял, что значит возвращать массив в исходное положение. Каким образом? Если просто убрать операцию присвоения в точке, то решение никак не поменяется.
Бро, давай вторую часть. Сейчас в последнее время забил на алгоритмическую прогу, но благодаря твоему видео, появилось неумолимое желание изучить, узнать ещё больше подобного материала. Спасибо!
Егор, это очень круто! И очень доступно. С большим удовольствием посмотрел
Огромное спасибо, очень полезное видео! 30:50 - если я правильно понял Ф+ = QlogN, а написано N + QlogN(Ф0 + Ф+), передаю привет из параллели А тинькофф.
Действительно, да. Это Ф0 + Ф+. Спасибо.
Спасибо большое, ты крутой!
Я не совсем понял формулу потенциала вершины, откуда log(C)?
когда срабатывает tagCondition мы обновляем значение суммы в вершине дерева отрезков, но после этого когда будет запрос о сумме, если отрезок этого запроса будет пересекать отрезок в котором мы ранее сделали присвоение, то он выдаст неправильную сумму же, разве нет?
вроде это тут говорится что эти данные потом pushатся, но чтобы их запушить нужно линейное время чтобы пропушить его во всех его детей или я чего то не понимаю
Мы проталкиваем информацию только в непосредственных детей. Это занимает константное время. Когда понадобится, они протолкнут эту информацию еще дальше. Советую прочитать что-нибудь про деревья отрезков с массовыми обновлениями. К примеру: e-maxx.ru/algo/segment_tree
@@peltorator я кажется понял, изменения в детях произойдут только когда нужно будет в них спуститься в последующих вызовах дерева отрезков. Спасибо мужик твои видосы топовые
@@dauletbiakhmet312 👍
@@peltorator хотел спросить, можешь ли открыть тесты для дорешивания, а то на задаче с НОДом на отрезке падает на втором тесте не знаю почему
@@dauletbiakhmet312 Привет! Тесты я не открою, потому что мне кажется это неинтересным, но помочь в телеграме могу.
Если ты считаешь какую-то функцию, которую называешь потенциалом, как можно сказать что-то про ассимптотику? Например, когда ты делаешь %= на отрезке, как связана сумма логорифмов элементов по всем вершинам связана с количеством операций? Можно вообще считать любую функцию и если она мало меняется, то и ассимптотика маленькая?
Мы следим за неким потенциалом. Мы знаем, что за все время он может увеличиться максимум на X. При этом каждый раз, когда мы делаем лишнюю операцию какую-то, мы уменьшаем потенциал на единицу. Значит, мы сделаем максимум X лишних операций. Так что асимптотику можно оценить как O(X).
А если задачку с %= модифицировать до просто нахождение суммы на отрезке, образно говоря, мы сначала применяем первую операцию потом 3, а потом возвращаем массив в исходное положение, то как такую модификацию можно решить с помощью этого дерева?
Я не совсем понял, что значит возвращать массив в исходное положение. Каким образом? Если просто убрать операцию присвоения в точке, то решение никак не поменяется.
Привет, на каком факультете ты учишься?
мкн
ничего не понял, но очень интересно
смотри внимательнее, пересматривай
6 лет занимался олимпиадами, умер после трети видео. Душнила