# Efficient Data Structures for Range Shortest Unique Substring Queries +
## 1 Introduction
### Proof of Lemma 1  
Let \(\mathsf{lcp}(i,j)\) denote the length of the longest common prefix of the suffixes of \(\mathsf{T}\) starting at positions \(i\) and \(j\) in \(\mathsf{T}\). Additionally, let \(S\) denote the set of all \((x,y)\) pairs, such that \(1\leq x<y\leq n\) and \(\mathsf{lcp}(x,y)>\mathsf{lcp}(x,z)\), for all \(z\in[x+1,y-1]\). The proof can be broken down into Lemma 2 and Lemma 3. Lemma 2: \(\sum_{k}|C_{k}|=\mathcal{O}(|S|)\)  
Figure 1: Illustration of the problem reduction: \((k,h)\) is the output of the \(\mathsf{rSUS}\) problem with query range \([\alpha,\beta]\), where \(h=\lambda(\alpha,\beta,k)\in C_{k}\). \(R_{k,h}\) is the lowest weighted rectangle in \(\mathcal{R}\) containing the point \((\alpha,\beta)\). Proof. : Let us fix a position \(k\). Let  
\[C^{\prime}_{k}=\{h>1\mid\mathsf{Prev}(k,h)\
eq\mathsf{Prev}(k,h-1)\}\]  
\[C^{\prime\prime}_{k}=\{h>1\mid\mathsf{Next}(k,h)\
eq\mathsf{Next}(k,h-1)\}.\]  
Clearly we have that \(C_{k}=C^{\prime}_{k}\cup C^{\prime\prime}_{k}\cup\{1\}\). The following statements can be deduced by a simple contradiction argument:  
1. Let \(i=\mathsf{Prev}(k,h)\
eq-\infty\), where \(h\in C^{\prime}_{k}\), then \(i=\mathsf{Prev}(k,\mathsf{lcp}(i,k))\)
2. Let \(j=\mathsf{Next}(k,h)\
eq\infty\), where \(h\in C^{\prime\prime}_{k}\), then \(j=\mathsf{Next}(k,\mathsf{lcp}(k,j))\). Figure 2 illustrates the proof for the first statement. The second one can be proved in a similar fashion. Clearly, \(|C^{\prime}_{k}|\) is proportional to the number of \((i,k)\) pairs, such that \(\mathsf{lcp}(i,k)\
eq 0\) and \(i=\mathsf{Prev}(k,\mathsf{lcp}(i,k))\). Similarly, \(|C^{\prime\prime}_{k}|\) is proportional to the number of \((k,j)\) pairs, such that \(\mathsf{lcp}(k,j)\
eq 0\) and \(j=\mathsf{Next}(k,\mathsf{lcp}(k,j))\). Therefore, \(\sum_{k}|C_{k}|\) is proportional to the number of \((x,y)\) pairs, such that \(\mathsf{lcp}(x,y)\
eq 0\) and \(\mathsf{lcp}(x,y)>\mathsf{lcp}(x,z)\), for all \(z\in[x+1,y-1]\). This completes the proof of Lemma 2. **Lemma 3**. : \(|S|=\mathcal{O}(n\log n)\)_._  
Proof. : Consider the suffix tree data structure of string \(\mathsf{T}[1,n]\), which is a compact trie of the \(n\) suffixes of \(\mathsf{T}\) appended with a letter \(\$\
otin\Sigma\)[7]. This suffix tree consists of \(n+1\) leaves (one for each suffix of \(\mathsf{T}\)) and at most \(n\) internal nodes. The edges are labeled with substrings of \(\mathsf{T}\). Let \(u\) be the lowest common ancestor of the leaves corresponding to the strings \(\mathsf{T}[x,n]\$\) and \(\mathsf{T}[y,n]\$\). Subsequently, the concatenation of the edge labels on the path from the root to \(u\) is exactly the longest common prefix of \(\mathsf{T}[x,n]\$\) and \(\mathsf{T}[y,n]\$\). For any node \(u\), we denote, by \(\mathsf{size}(u)\), the total number of leaf nodes of the subtree rooted at \(u\).  
We decompose the nodes in the suffix tree into light and heavy nodes. The root node is light and for any internal node, exactly one child is heavy. Specifically, the heavy child is the one having the largest number of leaves in its subtree (ties are broken arbitrarily). All other children are light. This tree decomposition is known as heavy-light decomposition. We have the following critical observation. Any path from the root to a leaf node contains many nodes; however, the number of light nodes is at most \(\log n\)[34, 36]. Additionally, corresponding to the \(n+1\) leaves of the suffix tree, there are \(n+1\) paths from the root to the leaves. Therefore, the sum of subtree sizes over all light nodes is \(\mathcal{O}(n\log n)\).  
We are now ready to complete the proof. Let \(S_{u}\subseteq S\) denote the set of pairs \((x,y)\), such that the lowest common ancestor of the leaves corresponding to suffixes \(\mathsf{T}[x,n]\$\) and \(\mathsf{T}[y,n]\$\) is \(u\). Clearly, the paths from the root to the leaves that correspond to suffixes \(\mathsf{T}[x,n]\$\) and \(\mathsf{T}[y,n]\$\) pass from two distinct children of node \(u\) and then at least one of the two must be a light node. There are two cases.