# Efficient Data Structures for Range Shortest Unique Substring Queries +
## 3 An \(\mathcal{O}(n)\)-Word Data Structure
We next show how to maintain additional structures, so that the smallest element in each of the above sets can be efficiently computed and, thus, the smallest among them can be reported as \(\ell\). * Computing the Smallest Element in \(S^{\prime}\): for each \(k\in[\alpha,\alpha^{\prime}-1]\cup[\beta^{\prime}+1,\beta]\), we compute \(\lambda(\alpha,\beta,k)\) and report the smallest among them. We handle each \(\lambda(\alpha,\beta,k)\) query in time \(\mathcal{O}(\log^{\varepsilon}n)\), as follows: first find the leaf corresponding to the string position \(k\) in the suffix tree of \(\mathsf{T}\), then the last (resp., first) leaf on its left (resp., right) side, such that the string position \(x\) (resp., \(y\)) corresponding to it is in \([\alpha,\beta]\), and report \(1+\max\{\mathsf{lep}(k,x),\mathsf{lep}(k,y)\}\). To efficiently enable the computation of \(x\) (resp., \(y\)), we preprocess the suffix array into an \(\mathcal{O}(n)\)-word data structure that can answer orthogonal range predecessor (resp., successor) queries in \(\mathcal{O}(\log^{\varepsilon}n)\) time [40]. * Computing the Smallest Element in \(S^{\prime\prime}_{1}\): for each \(r\in[\alpha^{\prime}-\Delta,\alpha-1]\), we compute the smallest element in \(\{h=\lambda(\alpha,\beta,k)\mid k\in[\alpha^{\prime},\beta^{\prime}],\mathsf{ Prev}(k,h)=r\}\) and report the smallest among them. The procedure is the following: find the leaf corresponding to the string position \(r\) in the suffix tree of \(\mathsf{T}\) and the last (resp., first) leaf on its left (resp., right) side, such that its corresponding string position \(x\) (resp., \(y\)) is in \([\alpha^{\prime},\beta^{\prime}]\) (via orthogonal range successor/predecessor queries as earlier). Subsequently, \(t=\max\{\mathsf{lcp}(r,x),\mathsf{lcp}(r,y)\}\) is the length of the longest prefix of \(\mathsf{T}[r,n]\) with an occurrence \(d\) in \([\alpha^{\prime},\beta^{\prime}]\). However, we need to verify whether occurrence \(d\) is unique and its \(\mathsf{Prev}(d,t)=r\). For this, find the two leftmost occurrences of \(\mathsf{T}[r,r+t-1]\) after \(r\), denoted by \(x^{\prime}\) and \(y^{\prime}\) (\(x^{\prime}<y^{\prime}\)), via two orthogonal range successor queries. If \(y^{\prime}\) does not exist, set \(y^{\prime}=+\infty\). Then report \(\lambda(\alpha,\beta,d)\) if \(\alpha^{\prime}\leq x^{\prime}\leq\beta^{\prime}<y^{\prime}\). Otherwise, report \(+\infty\). * Computing the Smallest Element in \(S_{2}^{\prime\prime}\): for each \(r\in[\beta+1,\beta^{\prime}+\Delta]\), we compute the smallest element in \(\{h=\lambda(\alpha,\beta,k)\mid k\in[\alpha^{\prime},\beta^{\prime}],\mathsf{ Next}(k,h)=r\}\) and report the smallest among them. The procedure is analogous to that of \(S_{1}^{\prime\prime}\); i.e., find the length \(t\) of the longest prefix of \(\mathsf{T}[r,n]\) with an occurrence \(d\) in \([\alpha^{\prime},\beta^{\prime}]\). Then, find the two rightmost occurrences of \(\mathsf{T}[r,r+t-1]\) before \(r\), denoted by \(x^{\prime}\) and \(y^{\prime}\) (\(x^{\prime}<y^{\prime}\)), via two orthogonal range successor queries. If \(x^{\prime}\) does not exist, set \(x^{\prime}=+\infty\). Subsequently, report \(\lambda(\alpha,\beta,d)\) if \(x^{\prime}<\alpha^{\prime}\leq y^{\prime}\leq\beta^{\prime}\). Otherwise, report \(+\infty\). * Computing the Smallest Element in \(S_{3}^{\prime\prime}\): the set \(S_{3}^{\prime\prime}\) can be written as \(\{\lambda(\alpha^{\prime}-\Delta,\beta^{\prime}+\Delta,k)\mid k\in[\alpha^{ \prime},\beta^{\prime}]\}\), which is now dependent only on \(\alpha^{\prime},\beta^{\prime}\) and \(\Delta\). Therefore, our idea is to pre-compute and explicitly store the minimum element in \(\{\lambda(a-\Delta,b+\Delta,k)\mid k\in[a,b]\}\) for all \((a,b)\) pairs, where both \(a\) and \(b\) are multiples of \(\Delta\), and for that the desired answer can be retrieved in constant time. The additional space needed is \(\mathcal{O}((n/\Delta)^{2})\). We set \(\Delta=\lfloor\sqrt{n}\rfloor\).