LAUSR

In the path reporting problem, we preprocess a tree on n nodes each of which is assigned a weight, such that given an arbitrary path and a weight range, we can report the nodes whose weights are within the range. We consider this problem in dynamic settings, and propose the first non-trivial linear-space solution that supports path reporting in $$O((\lg n{/}\lg \lg n)^2 + occ \lg n{/}\lg \lg n)$$O((lgn/lglgn)2+occlgn/lglgn) time, where occ is the output size, and the insertion and deletion of a node of an arbitrary degree in $$O(\lg ^{2+\epsilon } n)$$O(lg2+ϵn) amortized time, for any constant $$\epsilon \in (0, 1)$$ϵ∈(0,1). Obvious solutions based on directly dynamizing solutions to the static version of this problem all require $$\Omega ((\lg n{/}\lg \lg n)^2)$$Ω((lgn/lglgn)2) time for each node reported, and thus our query time is much faster. We also design data structures that support path counting and path reporting queries in $$O((\lg n{/}\lg \lg n)^2)$$O((lgn/lglgn)2) time, and insertions and deletions in $$O((\lg n{/}\lg \lg n)^2)$$O((lgn/lglgn)2) amortized time. This matches the best known results for dynamic two-dimensional range counting (He and Munro in Comput Geom 47(2):268–281, 2014) and range selection (He et al., in: Proceedings of the 22nd international symposium on algorithms and computation, ISAAC, Yokohama, Japan, 2011), which can be viewed as special cases of path counting and path selection.