# Efficient Data Structures for Range Shortest Unique Substring Queries +
## 1 Introduction
### Paper Organization  
In Section 2, we prove Theorem 1 and, in Section 3, we prove Theorem 2. We conclude this paper in Section 4 with some future proposals. An early version of this paper appeared as [33]. When compared to that early version ([33]), Theorem 2 is new. **2. An \(\mathcal{O}(n\log n)\)-Word Data Structure**  
Our construction is based on ingredients, such as the suffix tree [7], heavy-light decomposition [34], and a geometric data structure for rectangle stabbing [35]. Let us start with some definitions. **Definition 1**. : _For a position \(k\in[1,n]\) and \(h\geq 1\), we define \(\mathsf{Prev}(k,h)\) and \(\mathsf{Next}(k,h)\), as follows:_  
\[\mathsf{Prev}(k,h) =\max_{j}\{\{j<k\mid\mathsf{T}[k,k+h-1]=\mathsf{T}[j,j+h-1]\} \cup\{-\infty\}\}\] \[\mathsf{Next}(k,h) =\min_{j}\{\{j>k\mid\mathsf{T}[k,k+h-1]=\mathsf{T}[j,j+h-1]\} \cup\{+\infty\}\}.\]  
Intuitively, let \(x\) and \(y\) be the occurrences of \(\mathsf{T}[k,k+h-1]\) right before and right after the position \(k\), respectively. Subsequently, \(\mathsf{Prev}(k,h)=x\) and \(\mathsf{Next}(k,h)=y\). If \(x\) (resp., \(y\)) does not exist, then \(\mathsf{Prev}(k,h)=-\infty\) (resp., \(\mathsf{Next}(k,h)=+\infty\)). **Definition 2**. : _Let \(k\in[a,b]\). We define \(\lambda(a,b,k)\), as follows:_  
\[\lambda(a,b,k)=\min\{h\mid\mathsf{Prev}(k,h)<a\ \ \text{and}\ \ \mathsf{Next}(k,h)>b\}.\]  
Intuitively, \(\lambda(a,b,k)\) denotes the length of the shortest substring that starts at position \(k\) with exactly one occurrence in \([a,b]\). **Definition 3**. : _For a position \(k\in[1,n]\), we define \(C_{k}\), as follows:_  
\[C_{k}=\{h>1\mid(\mathsf{Next}(k,h),\mathsf{Prev}(k,h))\
eq(\mathsf{Next}(k,h- 1),\mathsf{Prev}(k,h-1))\}\cup\{1\}\]  
**Example 2**. : _(Running Example for Definition 3) Let \(\mathsf{T}=\textbf{caabcadaacaddaaaabac}\) and \(k=10\). We have that \((\mathsf{Next}(10,1),\mathsf{Prev}(10,1))=(12,9)\), \((\mathsf{Next}(10,2),\mathsf{Prev}(10,2))=(20,-\infty)\), and \((\mathsf{Next}(10,3),\mathsf{Prev}(10,3))=(+\infty,-\infty)\). Thus, \(C_{10}=\{2,3\}\cup\{1\}=\{1,2,3\}\)._  
Intuitively, \(C_{k}\) stores the set of candidate lengths for the shortest unique substrings starting at position \(k\). We make the following observation. **Observation 1**. : \(\lambda(a,b,k)\in C_{k}\)_, for any \(1\leq a\leq b\leq n\)._  
**Example 3**. : _(Running Example for Observation 1) Let \(\mathsf{T}=\textbf{caabcadaaacaddaaaabac}\) and \(k=10\). We have that \(C_{10}=\{1,2,3\}\). For \(a=5\) and \(b=16\), \(\lambda(5,16,10)=2\), denoting substring **ac**. For \(a=5\) and \(b=20\), \(\lambda(5,20,10)=3\), denoting substring **ac**._  
The following combinatorial lemma is crucial for efficiency. **Lemma 1**. : \(\sum_{k}|C_{k}|=\mathcal{O}(n\log n)\)_._  
Proof. : The proof of Lemma 1 is deferred to Section 2.1. We are now ready to present our construction. By Observation 1, for a given query range \([\alpha,\beta]\), the answer \((p,\ell)\) that we are looking for is the pair \((k,h)\) with the minimum \(h\) under the following conditions: \(k\in[\alpha,\beta]\), \(h\in C_{k}\), \(\mathsf{Prev}(k,h)<\alpha\) and \(\mathsf{Next}(k,h)>\beta\). Equivalently, \((p,\ell)\) is the pair \((k,h)\)with the minimum \(h\), such that \(h\in C_{k}\), \(\alpha\in(\mathsf{Prev}(k,h),k]\), and \(\beta\in[k,\mathsf{Next}(k,h))\). We map each \(h\in C_{k}\) into a weighted rectangle \(R_{k,h}\) with weight \(h\), which is defined as follows:  
\[R_{k,h}=[\mathsf{Prev}(k,h)+1,k]\times[k,\mathsf{Next}(k,h)-1].\]  
Let \(\mathcal{R}\) be the set of all such rectangles, then the lowest weighted rectangle in \(\mathcal{R}\) stabbed by the point \((\alpha,\beta)\) is \(R_{p,\ell}\). In short, an \(\mathsf{rSUS}\) query on \(\mathsf{T}[1,n]\) with an input range \([\alpha,\beta]\) can be reduced to an equivalent top-1 rectangle stabbing query on a set \(\mathcal{R}\) of rectangles with input point \((\alpha,\beta)\).