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… Click to show full abstract
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.
               
Click one of the above tabs to view related content.