Path and Ancestor Queries on Trees with Multidimensional Weight Vectors

We consider an ordinal tree $T$ on $n$ nodes, with each node assigned a $d$-dimensional weight vector $\text{pnt}w\in \{1,2,\dots ,n{\}}^d,$ where $d \in $\mathbb{N}$$ is a constant. We study path queries as generalizations of well-known {\textit{orthogonal range queries}}, with one of the dimensions being tree topology rather than a linear order. Since in our definitions $d$ only represents the number of dimensions of the weight vector without taking the tree topology into account, a path query in a tree with $d$-dimensional weight vectors generalize the corresponding $(d+1)$-dimensional orthogonal range query. We solve {$\mathit{\text{ancestor}}\mathit{\text{dominance}}\mathit{\text{reporting}}$} problem as a direct generalization of dominance reporting problem, %in time $\O((\lg^{d-1} n)/(\lg\lg n)^{d-2}+k)$intime$\O(\lg^{d-1}{n}+k)$$\O(n(\lg n)^{d-1}/(\lg \lg n)^{d-2})$words,andspaceof$\O(n\lg^{d-2}n)$words,where$k$isthesizeoftheoutput,for$d \geq 2.$Wealsoachieveatradeoffof$\O(n\lg^{d-2+\eps}{n})$ words of space, with query time of $\text{O}(({\lg }^{d-1}n)\mathrm{/}(\lg \lg n{)}^{d-2}+k),$ for the same problem, when $d\ge 3.$ We solve {$\mathit{\text{path}}\mathit{\text{successor}}\mathit{\text{problem}}$} in $\text{O}(n{\lg }^{d-1}n)$ words of space and time $\text{O}({\lg }^{d-1+\text{eps}}n)$ for $d\ge 1$ and an arbitrary constant $\text{eps}>0.$ We propose a solution to {$\mathit{\text{path}}\mathit{\text{counting}}\mathit{\text{problem}}$}, with $\text{O}(n(\lg n\mathrm{/}\lg \lg n{)}^{d-1})$ words of space and $\text{O}((\lg n\mathrm{/}\lg \lg n{)}^d)$ query time, for $d\ge 1.$ Finally, we solve {$\mathit{\text{path}}\mathit{\text{reporting}}\mathit{\text{problem}}$} in $\text{O}(n{\lg }^{d-1+\text{eps}}n)$ words of space and $\text{O}(({\lg }^{d-1}n)\mathrm{/}(\lg \lg n{)}^{d-2}+k)$ query time, for $d\ge 2.$ These results match or nearly match the best tradeoffs of the respective range queries. We are also the first to solve path successor even for $d=1$.