Где применяется
1. Задача
HR-система хранит компанию как дерево: сотрудник i подчиняется сотруднику parent[i], а у гендиректора родитель равен -1. Системе снова и снова нужно отвечать на один вопрос: кто ближайший общий руководитель двух сотрудников, то есть первый человек, до которого доходят обе цепочки подчинения? И на соседний вопрос: находится ли сотрудник X где-то под руководителем M?
На один такой вопрос можно ответить, поднимаясь по обеим цепочкам родителей, пока они не встретятся. Это O(глубина) на вопрос. В глубоком дереве с тысячами вопросов это долго.
Прошлый урок заранее считал блоки длины степени двойки в массиве, чтобы вопрос про отрезок не требовал прохода по нему. Та же идея работает на дереве. Для каждого узла заранее посчитаем предка на 1 шаг вверх, на 2 шага, на 4, на 8 и так далее. Тогда любой подъём по дереву это несколько больших прыжков вместо шагов по одному.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на деревья, где снова и снова спрашивают про предков или пути, например k-й предок или наименьший общий предок двух узлов. Таблица прыжков на 2^k предков отвечает на каждый вопрос за O(log n) после построения за O(n log n).
Возьми таблицу урока и прыгай по каждому единичному биту k, а если k больше глубины узла, верни минус 1.
Здесь один вопрос на одно дерево, так что хватит рекурсии из урока 78. Бинарный подъём даёт тот же ответ и окупается, только когда вопросы повторяются.
Храни для каждого узла счётчики 26 весов рёбер на пути от корня. У пути от u до v счётчики равны counts(u) + counts(v) минус два раза counts(LCA), а ответ это длина пути минус наибольший счётчик.
Каждый игрок пасует одному получателю, так что построй таблицу прыжков по receiver вместе с суммой номеров на каждом прыжке и поднимайся на k шагов из каждого старта.