# Efficient Data Structures for Range Shortest Unique Substring Queries +
## 3 An \(\mathcal{O}(n)\)-Word Data Structure  
This section is dedicated to proving Theorem 2. For simplicity, we only focus on the computation of the length \(\ell\) of the output \((p,\ell)\). Let \(\mathsf{SA}\) be the suffix array of string \(\mathsf{T}\) of length \(n\), which is a permutation of \(\{1,\cdots,n\}\), such that \(\mathsf{SA}[i]=j\) if \(\mathsf{T}[j,n]\) is the \(i\)th lexicographically smallest suffix of \(\mathsf{T}\)[37]. Further, let \(\mathsf{SA}^{-1}\) be the _inverse suffix array_ of string \(\mathsf{T}\) of length \(n\), which is a permutation of \(\{1,\cdots,n\}\), such that \(\mathsf{SA}^{-1}[\mathsf{SA}[i]]=i\). Moreover, \(\mathsf{SA}\) of \(\mathsf{T}\) can be constructed in linear time and space [38; 39]. We observe that an \(\mathcal{O}(\beta-\alpha+1)\)-time solution is straightforward with the aid of the suffix tree of \(\mathsf{T}\) as follows. First, identify those leaves corresponding to the suffixes starting within \([\alpha,\beta]\) using the inverse suffix array of \(\mathsf{T}\) and mark them. Subsequently, for each marked leaf, identify its lowest ancestor node (and double mark it), such that a marked neighbor is also under it. This can be done via at most two \(\mathcal{O}(1)\)-time Lowest Common Ancestor (LCA) queries over the suffix tree of \(\mathsf{T}\) while using \(\mathcal{O}(n)\) additional space [22]. Afterwards, find the minimum over the string-depth of all double-marked nodes, add \(1\) to it, and report it as the length \(\ell\). The correctness is readily verified. We employ the above procedure when \(\beta-\alpha+1<3\Delta\), where \(\Delta\) is a parameter to be set later. We now consider the case when \(\beta-\alpha+1\geq 3\Delta\). Note that \(\ell\) is the smallest element in \(S^{*}=\{\lambda(\alpha,\beta,k)\mid k\in[\alpha,\beta]\}\). Let \(\alpha^{\prime}\) be the smallest number after \(\alpha\) and \(\beta^{\prime}\) be the largest number before \(\beta\), such that \(\alpha^{\prime}\) and \(\beta^{\prime}\) are multiples of \(\Delta\). Subsequently, \(S^{*}\) can be written as the union of \(S^{\prime}=\{\lambda(\alpha,\beta,k)\mid k\in[\alpha,\alpha^{\prime}-1]\cup[ \beta^{\prime}+1,\beta]\}\) and \(S^{\prime\prime}=\{\lambda(\alpha,\beta,k)\mid k\in[\alpha^{\prime},\beta^{ \prime}]\}\). Furthermore, \(S^{\prime\prime}\) can be written as \(S^{\prime\prime}_{1}\cup S^{\prime\prime}_{2}\cup S^{\prime\prime}_{3}\), where  
* \(S^{\prime\prime}_{1}=\{h=\lambda(\alpha,\beta,k)\mid k\in[\alpha^{\prime}, \beta^{\prime}],\mathsf{Prev}(k,h)\in[\alpha^{\prime}-\Delta,\alpha-1]\}\)
* \(S^{\prime}_{2}=\{h=\lambda(\alpha,\beta,k)\mid k\in[\alpha^{\prime},\beta^{ \prime}],\mathsf{Next}(k,h)\in[\beta+1,\beta^{\prime}+\Delta]\}\)
* \(S^{\prime\prime}_{3}=\{h=\lambda(\alpha,\beta,k)\mid k\in[\alpha^{\prime}, \beta^{\prime}],\mathsf{Prev}(k,h)\in(-\infty,\alpha^{\prime}-\Delta-1],\mathsf{ Next}(k,h)\in[\beta^{\prime}+\Delta+1,\infty)\}\). Our construction is based on a solution to the Orthogonal Range Predecessor/Successor in 2-d problem. A set \(\mathcal{P}\) of \(n\) points in an \([1,n]\times[1,n]\) grid can be preprocessed into a linear-space data structure, such that the following queries can be answered in \(\mathcal{O}(\log^{\varepsilon}n)\) time per query [40]:  
* \(\mathsf{ORQ}([x^{\prime},x^{\prime\prime}],[-\infty,y^{\prime\prime}])=\arg \max_{j}\{(i,j)\in\mathcal{P}\cap[x^{\prime},x^{\prime\prime}]\times[-\infty, y^{\prime\prime}]\}\)
* \(\mathsf{ORQ}([-\infty,x^{\prime\prime}],[y^{\prime},y^{\prime\prime}])=\arg \max_{i}\{(i,j)\in\mathcal{P}\cap[-\infty,x^{\prime\prime}]\times[y^{\prime}, y^{\prime\prime}]\}\)
* \(\mathsf{ORQ}([x^{\prime},x^{\prime}],[y^{\prime},+\infty])=\arg\min_{j}\{(i,j) \in\mathcal{P}\cap[x^{\prime},x^{\prime\prime}]\times[y^{\prime},+\infty]\}\)
* \(\mathsf{ORQ}([x^{\prime},+\infty],[y^{\prime},y^{\prime\prime}])=\arg\min_{i}\{(i, j)\in\mathcal{P}\cap[x^{\prime},+\infty]\times[y^{\prime},y^{\prime\prime}]\}\).