Дерево отрезков | Структуры данных и алгоритмы | Изучение алгоритмов

[@vladimir_balun_programming]

В этом видео рассказал про дерево отрезков, но какую структуру данных рассмотреть в следующем видео?

[@broken_beyond_belief]

Дерево Фенвика

[@DotaPsihopat]

@@broken_beyond_belief Или бор

[@broken_beyond_belief]

чекнул твой канал, увидел у тебя рофловидос про гуля, я его буквально сегодня видел утром. вот это рандом, конечно, круглая планета

[@vladimir_balun_programming]

@@broken_beyond_belief что такое гуля?

[@vladimir_balun_programming]

@@DotaPsihopat бор скоро будет)

[@korst1k]

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

[@vladimir_balun_programming]

Спасибо!

[@ФедорАлексеевичМалашин]

Владимир, ставлю лайк. Я C++ программер, в последнее время что-то мотивация пропадает, но такие видосы поднимают её) Желаю успехов, делай еще видосы на разные темы!

[@vladimir_balun_programming]

Спасибо!

[@pavlobondarenko4503]

Спасибо за обучающий контент!

[@vladimir_balun_programming]

Не за что!

[@alexandersmirnov4274]

класс спасибо еще бы показать код как его эффективно строить а следующим можно было бы рассмотреть суффиксное дерево по строкам

[@АйратГиззатуллин-ъ9ч]

Возник вопрос. Если данные большие, массив увеличивается очень сильно. В этом случае можно ли построить в виде дерева с указателями?

[@alexandroppolus]

В дереве отрезков за O(ln N) можно обновить не только один элемент, но и целый отрезок массива! Такое изменение, разумеется, не сразу доезжает до самого массива, а "застревает" где-то в промежуточных уровнях и далее проталкивается "с оказией" - когда дело дойдет до того или иного подотрезка. Вообще тема жирная, здесь только поверхностно.

[@phonkabuser3985]

а его можно использовать чтобы получать уникальные элементы на отрезке? это будет ~n-1 мерджей двух сетов, которые же делаются тоже небыстро, а как можно мерджить множества(set) быстро, еще и в худшем случае по памяти не очень, потому что на каждом уровне будет храниться n значений, т.е по памяти будет n*log2(n). Может эту задачу можно эффективнее решать?

[@ДмитрийЩукин-у4э]

вы бы еще примеры кода добавили, а то если честно не до конца понятно

[@Evg2002]

Спасибо

[@vladimir_balun_programming]

Не за что!

[@OOOJohnJ]

1:30 что-то не понял чем подход рабочий? в выделенном отрезке сумма = 7, а по суммам в нижнем массиве имеем 3 в начале и 8 в конце, то есть 8-3 = 5. Или я не понял что из чего вычитать?

[@pigsel2509]

сумма элементов на отрезке [l;r] (включительно) равна pref[r] - pref[l - 1], где pref - массив сумм (нижний). Здесь будет не 8-3, а 8-1

[@Max-wn2gd]

а в каких реальных задачах эта сд может применяться ? у вас встречалась ?

[@vladimir_balun_programming]

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

[@sq.froggy2107]

сразу же выключил на моменте когда этот человек сказал про "хэширование" и преффиксный массив, который ТОЧНО ТАКОЙ ЖЕ ДЛИНЫ

[@ЕвгенийК-ц9с]

я не совсем понял, в чем выигрыш построения таких деревьев или префиксных сумм. Что мы просто перебором сумму отрезка за линейное время найдем. Что мы дерево построим за линейное время и потом сумму найдем. В любом случае линейное время будет

[@Кирилл-ж3м2н]

Ну смысл в том, что дерево можно построить один раз и потом обратиться к нему миллион раз. А перебором ты миллион раз будешь его перебирать.

[@andreypoltev]

ВОТ ЭТА ОТ ВОТ ЭТАВА ВЫЧИТАЕМ Спасибо, помогло. (нет)