Trees in an n node forest are to be merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of O(n) instructions can be processed “on line” in O(n log n) steps on a random access computer.
No takes yet. Share an insight, caveat, or question.
Aho et al. (1973) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: