Всем привет. В этой статье я расскажу про дерево отрезков. Очень мощной структуры данных, которая позволяет делать много разных операций над массивом чисел. Я постараюсь по полочкам разложить эту тему и объяснить возможности дерева отрезков. Также я разберу несколько нетривиальных задач на дерево отрезков. Помимо самого дерева отрезков я расскажу и про связанные темы: дерево Фенвика и разреженные таблицы. Читать далее
Накануне очередного запуска курса «Алгоритмы для разработчиков» мы провели открытый урок. На нём поговорили об известной идее дерева отрезков, обсудили, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Для закрепления материала решили олимпиадную задачу. Вебинар провёл опытный программист и преподаватель, а также руководитель курса «Алгоритмы для разработчиков» Евгений Волосатов. Читать дальше →
Всем привет! Изучив несколько статей по этой теме, у меня остались вопросы, и некоторые моменты по-прежнему были не понятны, поэтому я решил написать свою, которая, как мне кажется, была бы понятна тем, кто не силен в спортивном программировании. В ней я объясняю, как устроено дерево отрезков. Примеры с кодом будут приведены на языке C++, однако на объяснение это не влияет. Читать далее
Многие знакомы с алгоритмами дерева отрезков и корневой декомпозиции. Однако, не многие задаются вопросом о том, почему они устроены именно так, как они устроены :), и нельзя ли немного изменив их получить выигрыш во времени работы или затрачиваемой памяти. Одно из таких изменений я бы и хотел рассмотреть в этой статье, ведь я сам только недавно задумался об этом, хотя знаком с этими алгоритмами уже более 4 лет. Математика говорит, что это невозможно, но нам всё равно! Расширять сознание