Trees are fundamental structures in computer science, being widely used in modeling and representing different types of data in numerous computer applications. In many cases, properties of objects being modeled are stored as weights or labels on the nodes of trees. Thus researchers have studied the preprocessing of weighted trees in which each node is assigned a weight, in order to support various path queries, for which a certain function over the weights of the nodes along a given query path in the tree is computed [3, 14, 22, 26]. In this thesis, we consider the problem of supporting several various path queries over a tree on n weighted nodes, where the weights are drawn from a set of σ distinct values. One query we support is the path median query, which asks for the median weight on a path between two given nodes. For this and the more general path selection query, we present a linear space data structure that answers queries in O(lg σ) time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space data structures require O(n^ε) time to answer a query for any positive constant ε [26]. We also consider the path counting query and the path reporting query, where a path counting query asks for the number of nodes on a query path whose weights are in a query range, and a path reporting query requires to report these nodes. Our linear space data structure supports path counting queries with O(lg σ) query time. This matches the result of Chazelle [14] when σ is close to n, and has better performance when σ is significantly smaller than n. The same data structure can also support path reporting queries in O(lg σ + occ lg σ) time, where occ is the size of output. In addition, we present a data structure that answers path reporting queries in O(lg σ + occ lg lg σ) time, using O(n lg lg σ) words of space. These are the first data structures that answer path reporting queries.

Trees are fundamental structures in computer science, being widely used in modeling and representing different types of data in numerous computer applications. In many cases, properties of objects being modeled are stored as weights or labels on the nodes of trees. Thus researchers have studied the preprocessing of weighted trees in which each node is assigned a weight, in order to support various path queries, for which a certain function over the weights of the nodes along a given query path in the tree is computed [3, 14, 22, 26]. In this thesis, we consider the problem of supporting several various path queries over a tree on n weighted nodes, where the weights are drawn from a set of σ distinct values. One query we support is the path median query, which asks for the median weight on a path between two given nodes. For this and the more general path selection query, we present a linear space data structure that answers queries in O(lg σ) time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space data structures require O(n^ε) time to answer a query for any positive constant ε [26]. We also consider the path counting query and the path reporting query, where a path counting query asks for the number of nodes on a query path whose weights are in a query range, and a path reporting query requires to report these nodes. Our linear space data structure supports path counting queries with O(lg σ) query time. This matches the result of Chazelle [14] when σ is close to n, and has better performance when σ is significantly smaller than n. The same data structure can also support path reporting queries in O(lg σ + occ lg σ) time, where occ is the size of output. In addition, we present a data structure that answers path reporting queries in O(lg σ + occ lg lg σ) time, using O(n lg lg σ) words of space. These are the first data structures that answer path reporting queries.

We consider the problem of testing whether r (>=2) samples are drawn from the same continuous distribution F(x). The test statistic we will study in some detail is defined as the maximum of the circular differences of the empirical distribution functions, a generalization of the classical 2-sample Kolmogorov-Smirnov test to r (>=2) independent samples. For the case of equal sample sizes we derive the exact null distribution by counting lattice paths confined to stay in the scaled alcove $\mathcal{A}_r$ of the affine Weyl group $A_{r-1}$. This is done using a generalization of the classical reflection principle. By a standard diffusion scaling we derive also the asymptotic distribution of the test statistic in terms of a multivariate Dirichlet series. When the sample sizes are not equal the reflection principle no longer works, but we are able to establish a weak convergence result even in this case showing that by a proper rescaling a test statistic based on a linear transformation of the circular differences of the empirical distribution functions has the same asymptotic distribution as the test statistic in the case of equal sample sizes. / Series: Research Report Series / Department of Statistics and Mathematics