Оптимизируем дерево отрезков, делаем из него куст o_O

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