Dynamic weighted ancestors
Tsvi Kopelowitz, Moshe Lewenstein · Symposium on Discrete Algorithms · 2007
In the weighted ancestor problem one preprocesses a weighted tree (the weights are on the nodes and increase with tree depth) to support predecessor queries, which are called weighted ancestors queries, on the paths from the query node to the root.Since, the weighted ancestor problem appears in numerous applications, the problem has been studied and solutions for static trees are well known. However, it has been an open question whether this can be solved optimally for the dynamic version of the problem, where node insertions are supported. Node insertions are leaf insertions or edge splittings.In this paper we present a solution for the dynamic weighted ancestors problem which supports queries and update operations in the same time bounds as those for dynamic predecessor structures.