Sorted Consecutive Occurrence Queries in Substrings

The suffix tree of string $T$ is a compacted trie for the set of suffixes of $T$ [37]. We denote by $\mathrm{𝗌𝗍𝗋}(v)$ the path-string obtained by concatenating the edge labels from the root to node $v$ of the suffix tree of $T$. If the last character of $T$ is unique (i.e., occurs in $T$ only once), then the suffix tree of $T$ has exactly $|T|$ leaves and there is a one-to-one correspondence between the leaves and the suffixes of $T$. More precisely, for each suffix $T[i..]$ of $T$, there exists a leaf ${\mathrm{\ell }}_i$ of the suffix tree of $T$ such that $\mathrm{𝗌𝗍𝗋}({\mathrm{\ell }}_i)=T[i..]$, and vice versa. Thus, we label such a leaf ${\mathrm{\ell }}_i$ with integer $i$. For a substring $w$ of $T$, we define $\mathrm{𝗅𝗈𝖼𝗎𝗌}(w)$ as the highest node $u$ of the suffix tree of $T$ such that $w$ is a prefix of the string $\mathrm{𝗌𝗍𝗋}(u)$.

The suffix tree of string $T$ over $\mathrm{\Sigma }$ can be constructed in $O(n\log |\mathrm{\Sigma }|)$ time [37].

In the rest of this paper, we assume that the last character of $T$ is unique (one can achieve this property by appending a new letter), and we denote by $𝒯$ the suffix tree of $T$. Namely, $𝒯$ has exactly $n$ leaves.

A heavy path of a tree is a root-to-leaf path in which each node has a size no smaller than the size of any of its siblings (the size of a node is the number of nodes in the subtree rooted at that node). Heavy path decomposition is a process of decomposing a tree into heavy paths [36]. First, we find a heavy path by starting from the tree’s root and choosing a child with the maximum size at each level. We follow the same procedure recursively for each subtree rooted at a node that is not on the heavy path, but its parent node is (on the heavy path). As a result, a collection of (disjoint) heavy paths is obtained. Some of its properties are:

• $\mathrm{■}$

  each node $v$ belongs to exactly one heavy path,

• $\mathrm{■}$

  any path from the root to a leaf can pass through at most ${\log }_{2}N$ heavy paths where $N$ is the size of the number of nodes in the tree,

• $\mathrm{■}$

  the number of heavy paths equals the number of leaves in the tree.

All heavy paths of a rooted tree with $N$ nodes can be computed in $O(N)$ time [36].

The segment tree [5] is an important data structure in computational geometry. It stores a set of $N$ line segments in the plane such that the segments intersected by a vertical query line can be computed in $O(\log N+K)$ time, where $K$ is the number of reported segments. It can be built in $O(N\log N)$ space and time. It is a balanced binary search tree of height $O(\log N)$ built over the $x$-coordinates of the segments’ endpoints. Each node stores a vertical slab $H(v):=[a,b)\times ℝ$ and a set $S(v)$ of segments, where $a$ and $b$ are real numbers. Let $l_1,l_2,\mathrm{\dots }{l}_m$ be the list of leaf nodes in the left-to-right order. The slab of a leaf node $l_i$ , for each $i=1,2,\mathrm{\dots }m-1$, is determined by the key values of $l_i$ and $l_{i+1}$, and the vertical slab of an internal node is the union of those of its children. Note that the vertical slabs of the nodes of any particular level form a partition of the plane. A segment $s$ is stored at each highest node $v$ such that $s\cap H(v)\ne \mathrm{\varnothing }$ and no endpoint of $s$ lies inside $H(v)$. Given a real value $x$, the path from the root to the leaf $l_i$ whose vertical slab contains $x$ is referred to as the search path for $x$. An important property of the segment tree is that a segment intersects the vertical line through $x$ if and only if it is stored at some node of the search path for $x$.

Chazelle and Guibas [11] introduced the fractional cascading technique, a data structure technique which is useful in the scenarios where one needs to search an item in multiple sorted lists. It speeds up the search process. We briefly describe the idea of the technique in the context where lists are associated with the nodes of a balanced binary tree, the reader may refer to [11] for full details. Let $T$ be a balanced binary tree with $O(\log n)$ height, and each node $v$ stores a sorted list $L_v$ of comparable items where $n$ is the combined size of all lists. Given a root-to-leaf path in $T$, one can trivially find the position (rank) of an item in the list of each node on the path in $O({\log }^{2}n)$ time; performing a binary search at each node of the path. By employing fractional cascading technique, the search time can be reduced to $O(\log n)$. The technique introduces an augmented list $A_v$ for each node $v$ in the tree: the augmented list $A_v$ consists of the items of $L_v$ and every fourth item from the list of each child; the list $A_v$ is also sorted. These augmented lists are built in a bottom-up fashion. Each item $x$ in $A_v$ stores a constant amount of information: (1) whether $x$ is from $L_v$ or from one of $v$’s children, (2) pointers to immediate neighbors of $x$ on either side in $A_v$ that belong to $L_v$, (3) a pointer to the appropriate item in $A_w$ for each child $w$ of $v$. If the position of $x$ in $A_v$ is known, one can find its position in the list of either child (of node $v$) in $O(1)$ time using the saved pointers. Suppose we are to find the position (rank) of an item $\alpha$ in lists of nodes on a particular root-to-leaf path $\pi =⟨u_0=\mathrm{𝑟𝑜𝑜𝑡},u_1,u_2,\mathrm{\dots }⟩$. A binary search is used to find the location of $\alpha$ in $A_{u_0}$ (and hence in $L_{u_0}$). Then, using the pointers stored in $A_{u_0}$, the correct rank of $\alpha$ in the list $L_{u_1}$ of the next node $u_1$ on the path $\pi$ can be computed in $O(1)$ time. Generally speaking, if the rank of $\alpha$ in $L_{u_j}$ is known, the rank of $i$ in $L_{u_{j+1}}$ can be obtained in $O(1)$ time using the pointers stored in $A_{u_j}$. Thus, the total time spent would be $O(\log n)$.

A sorted range reporting problem over an array $A$ of integers is, given a query $([x_1,x_2],k)$ where $x_1,x_2,k$ are integers, to report the $k$ smallest values in sub-array $A[x_1:x_2]$ in sorted order. The following result is due to Brodal et al. [9].

A 2D orthogonal range reporting problem asks to represent a set of 2D planar points into an efficient data structure such that all the points inside an orthogonal query rectangle can be reported efficiently. Nekrich and Navarro [29] studied a variant of the problem where the output points are to be reported in increasing (or decreasing) order of one of the two coordinates. They proposed an almost $O(N)$ space solution to the problem that takes $O(\log \log N+K)$ time to answer a query, where $N$ is the size of the input set and $K$ is the number of reported points. The output points are reported one by one in the sorted order. Their main result is as follows.

A dynamic fusion node [30] is a data structure for a dynamic set of integers which supports operations on the set including insertion, deletion, predecessor, and successor. Every query can be executed in $O(\log N/\log w)$ time where $N$ is the size of the dynamic set and $w$ is the machine word size. The data structure uses $O(N)$ space. If $N$ is close to $w$, the following holds:

We will use this lemma later in the case where $N\le \log |T|\in O(w)$.

Given set $I$ of horizontal segments, we build a segment tree $T$ over $I$. Each node $v\in T$ maintains the segments stored at node $v$, in a list $L_v$ sorted by their weights. To efficiently perform predecessor search, we employ the fractional cascading technique (see also Section 2) on the sorted lists $L_v$ for all $v\in T$. We define an array $Y_v$ over the list $L_v$ such that $Y_v[i]$ stores the y-coordinate of segment $L_v[i]$. We then preprocess the array $Y_v$ for the sorted range reporting queries of Lemma 3. The size of the enhanced segment tree structure is $O(|I|\log |I|)$ since data structures associated with each node $v$ use $O(|L_v|)$ space and $O({\sum }_{v\in T}|L_v|)=O(|I|\log |I|)$ holds.

Given a query $(x,[w_1,w_2],k)$, we first find the search path $\pi$ for $x$ in the segment tree $T$. Let $\pi =⟨u_0=\mathrm{𝑟𝑜𝑜𝑡},u_1,\mathrm{\dots },u_{|\pi |-1}⟩$. We then traverse the path $\pi$ in the top-down fashion and for each node $v\in \pi$, compute the positions (ranks) of $w_1$ and $w_2$ in list $L_v$, respectively denoted by ${\mathrm{𝑟𝑛𝑘}}_v(w_1)$ and ${\mathrm{𝑟𝑛𝑘}}_v(w_2)$, using the pointers provided by the fractional cascading technique described in Section 2. We prepare an incremental buffer $B$ of size $O(k+\log n)$ consisting of $|\pi |=O(\log n)$ rows. Each $i$th row of $B$ corresponds to the node $u_i$ on the path $\pi$, denoted by $B[u_i]$. Moreover, we maintain a min-heap $H$ implemented as a dynamic fusion node (Lemma 5). See Figure 3 for illustration.

We find top-$1$ (i.e., the smallest) items from the subarrays $Y_v[{\mathrm{𝑟𝑛𝑘}}_v(w_1)..{\mathrm{𝑟𝑛𝑘}}_v(w_2)]$ for all nodes $v\in \pi$ and initialize the heap $H$ with the minima. Also, we initialize the counter $e(v)=0$ for each node $v\in \pi$. We then keep repeating the following steps until the heap $H$ gets empty or $k$ items are reported:

1. 1.

   Pop the minimum item $\mu$ from the heap $H$ and report it. Let $v$ be the node on the path $\pi$ from which the item $\mu$ came.

2. 2.

   If $v$’s buffer $B[v]$ is non-empty, simply pop the minimum item from $B[v]$ and insert it into the heap $H$. Then continue to the next iteration.

3. 3.

   Otherwise (if $B[v]$ is empty), find top-$2^{e(v)+1}$ items from $Y_v[{\mathrm{𝑟𝑛𝑘}}_v(w_1)..{\mathrm{𝑟𝑛𝑘}}_v(w_2)]$ by using Lemma 3. Then remove the first half $2^{e(v)}$ of them, which have already been moved to $H$ in previous steps, and insert the remaining items to $B[v]$. Lastly, pop the minimum item from $B[v]$ and insert it into the heap $H$, and increment $v$’s counter $e(v)$ by $1$.

We focus on the changes to the buffer $B[v]$ for any fixed node $v\in \pi$ throughout the query algorithm. Buffer $B[v]$ grows only if we enter Step 3, where $B[v]$ is empty. Picking up only steps where $B[v]$ grows, in each such step, $B[v]$ is updated to the top-$2^{e(v)}$ items from the items in $Y_v[{\mathrm{𝑟𝑛𝑘}}_v(w_1)..{\mathrm{𝑟𝑛𝑘}}_v(w_2)]$ that are not inserted to $H$ before, for incremental $e(v)=0,1,2,\mathrm{\dots }$. Also, when the smallest item from $B[v]$ is inserted to $H$ at Step 2, the item is removed from $B[v]$. Hence, buffer $B[v]$ keeps the top-$c$ items from $Y_v[{\mathrm{𝑟𝑛𝑘}}_v(w_1)..{\mathrm{𝑟𝑛𝑘}}_v(w_2)]$ that have not been inserted to $H$ for some $c\ge 0$. Also, the smallest unreported item from $Y_v[{\mathrm{𝑟𝑛𝑘}}_v(w_1)..{\mathrm{𝑟𝑛𝑘}}_v(w_2)]$ is always present in heap $H$ for every $v\in \pi$ due to Step 2. Thus, for each iteration of the three steps of the algorithm, the smallest unreported item from $\pi$ that satisfies the weight constraint will be reported at Step 1 of the iteration.

We now analyze the running time of the query algorithm. Given $x$, determining the search path $\pi$ in the segment tree $T$ takes $O(\log n)$ time. Also, thanks to the fractional cascading technique, all the ranks of $w_1$ and $w_2$ in the nodes in $\pi$ can be computed in a total of $O(\log n)$ time. As the heap $H$ is implemented as dynamic fusion node structure, initializing $H$ takes $O(\log n)$ time. While iterating the loop, when buffer $B[v]$ becomes empty (i.e., all items of $B[v]$ have either been moved to $H$ or reported as output) for a node $v$, it is replaced by a new buffer twice the size of the previous one in $O(|B[v]|)$ time by Lemma 3. Since (1) the size of $B[v]$ is at most the number of items from $v$ already reported or moved to $H$ and (2) the number of rows in $B$ is $|\pi |\in O(\log n)$, the total size of the buffer $B$ is $O(k+\log n)$. Further, each operation in a dynamic fusion node structure takes constant time. To summarize, the total time spent²²2Note that if we implement the heap $H$ as a standard binary heap instead of the dynamic fusion node, the query time becomes $O((k+\log n)\log \log n)$ since the size of $H$ is $O(\log n)$. to answer the query is $O(k+\log n)$.

We have completed the proof of Theorem 9.