Turns out the details of this tree are kinda skipped over completely, but also the only important part is that we store \(\Theta(k)\) information for at most \(O(n/k)\) nodes, and that we can walk up from any node and find such a node in at most \(O(k)\) steps. This is a simpler (more elementary/classical) approach that has \(O(n)\) memory, \(O(n)\) construction time, and \(O(\log n)\) query time (as opposed to the \(O(\log n)\) or \(O(\log n/\log \log n)\) time of Theorem 19/20). This takes \(O(\log n)\) time for walking up the HLD-components, and \(O(\log n)\) time to binary search inside that component, for \(O(\log n)\) total query time.