Still Simpler Static Level Ancestors
share
A level-ancestor or LA query about a rooted tree T takes as arguments a node v in T, of depth d_v, say, and an integer d with 0< d< d_v and returns the ancestor of v in T of depth d. The static LA problem is to process a given rooted tree T so as to support efficient subsequent processing of LA queries about T. All previous efficient solutions to the static LA problem work by reducing a given instance of the problem to a smaller instance of the same or a related problem, solved with a less efficient data structure, and a collection of small micro-instances for which a different solution is provided. We indicate the first efficient solution to the static LA problem that works directly, without resorting to reductions or micro-instances.
READ FULL TEXT