We present $$O(n)$$ O ( n ) -space data structures to support various range frequency queries on a given array $$A[0:n-1]$$ A [ 0 : n - 1 ] or tree $$T$$ T with $$n$$ n nodes. Given a query consisting of an arbitrary pair of pre-order rank indices $$(i,j)$$ ( i , j ) , our data structures return a least frequent element, mode, $$\alpha $$ α -minority, or top- $$k$$ k colors (values) of the multiset of elements in the unique path with endpoints at indices $$i$$ i and $$j$$ j in $$A$$ A or $$T$$ T . We describe a data structure that supports range least frequent element queries on arrays in $$O(\sqrt{n / w})$$ O ( n / w ) time, improving the $${\varTheta }(\sqrt{n})$$ Θ ( n ) worst-case time required by the data structure of Chan et al. (SWAT 2012), where $$w \in {\varOmega }(\log n)$$ w ∈ Ω ( log n ) is the word size in bits. We describe a data structure that supports path mode queries on trees in $$O(\log \log n \sqrt{n / w})$$ O ( log log n n / w ) time, improving the $${\varTheta }(\sqrt{n} \log n)$$ Θ ( n log n ) worst-case time required by the data structure of Krizanc et al. (ISAAC 2003). We describe the first data structures to support path least frequent element queries, path $$\alpha $$ α -minority queries, and path top- $$k$$ k color queries on trees in $$O(\log \log n \sqrt{n/w}),\,O(\alpha ^{-1} \log \log n)$$ O ( log log n n / w ) , O ( α - 1 log log n ) , and $$O(k)$$ O ( k ) time, respectively, where $$\alpha \in [0,1]$$ α ∈ [ 0 , 1 ] and $$k \in \{1,\ldots , n\}$$ k ∈ { 1 , … , n } are specified at query time.