Всем привет! Изучив несколько статей по этой теме, у меня остались вопросы, и некоторые моменты по-прежнему были не понятны, поэтому я решил написать свою, которая, как мне кажется, была бы понятна тем, кто не силен в спортивном программировании. В ней я объясняю, как устроено дерево отрезков. Примеры с кодом будут приведены на языке C++, однако на объяснение это не влияет.
Рубрика «дерево отрезков»
Понимаем обычное дерево отрезков
2023-03-07 в 22:42, admin, рубрики: c++, Алгоритмы, дерево отрезков, логарифмическое время, объяснение, первая статья на хабре, решение задач, Спортивное программирование, турникОптимизируем дерево отрезков, делаем из него куст o_O
2022-11-05 в 22:13, admin, рубрики: c++, python, Алгоритмы, дерево отрезков, мемы, оптимизация, оптимизация программ, Спортивное программированиеВведение
Многие знакомы с алгоритмами дерева отрезков и корневой декомпозицией. Однако, не многие задаются вопросом о том, почему они устроены именно так, как они устроенны, и нельзя ли немного изменив их получить выигрыш во времени работы или памяти. Одно из таких изменений я бы и хотел рассмотреть в этой статье.
Предыстория
Данная история мало конструктивна, нужна скорее для понимания того, откуда возникла идея для оптимизации. Подробно о самом алгоритме и написано ниже.
Дерево отрезков: просто и быстро
2020-01-23 в 11:48, admin, рубрики: Алгоритмы, Блог компании OTUS. Онлайн-образование, дерево отрезковНакануне очередного запуска курса «Алгоритмы для разработчиков» мы провели открытый урок. На нём поговорили об известной идее дерева отрезков, обсудили, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Для закрепления материала решили олимпиадную задачу.
Вебинар провёл опытный программист и преподаватель, а также руководитель курса «Алгоритмы для разработчиков» Евгений Волосатов. Читать полностью »