Range mode query

Let ${\displaystyle A}$ and ${\displaystyle B}$ be any multisets. If ${\displaystyle c}$ is a mode of ${\displaystyle A\cup B}$ and ${\displaystyle c\notin A}$, then ${\displaystyle c}$ is a mode of ${\displaystyle B}$.

Let ${\displaystyle c\notin A}$ be a mode of ${\displaystyle C=A\cup B}$ and ${\displaystyle f_{c}}$ be its frequency in ${\displaystyle C}$. Suppose that ${\displaystyle c}$ is not a mode of ${\displaystyle B}$. Thus, there exists an element ${\displaystyle b}$ with frequency ${\displaystyle f_{b}}$ that is the mode of ${\displaystyle B}$. Since ${\displaystyle b}$ is the mode of ${\displaystyle B}$ and that ${\displaystyle c\notin A}$, then ${\displaystyle f_{b}>f_{c}}$. Thus, ${\displaystyle b}$ should be the mode of ${\displaystyle C}$ which is a contradiction.

Let ${\displaystyle A[1:n]}$ be an array, and ${\displaystyle D[1:\Delta ]}$ be an array that contains the distinct values of A, where ${\displaystyle \Delta }$ is the number of distinct elements. We define ${\displaystyle B[1:n]}$ to be an array such that, for each ${\displaystyle i}$, ${\displaystyle B[i]}$ contains the rank (position) of ${\displaystyle A[i]}$ in ${\displaystyle D}$. Arrays ${\displaystyle B,D}$ can be created by a linear scan of ${\displaystyle A}$.

Arrays ${\displaystyle Q_{1},Q_{2},...,Q_{\Delta }}$ are also created, such that, for each ${\displaystyle a\in \{1,...,\Delta \}}$, ${\displaystyle Q_{a}=\{b\;|\;B[b]=a\}}$. We then create an array ${\displaystyle B'[1:n]}$, such that, for all ${\displaystyle b\in \{1,...,n\}}$, ${\displaystyle B'[b]}$ contains the rank of ${\displaystyle b}$ in ${\displaystyle Q_{B[b]}}$. Again, a linear scan of ${\displaystyle B}$ suffices to create arrays ${\displaystyle Q_{1},Q_{2},...,Q_{\Delta }}$ and ${\displaystyle B'}$.

It is now possible to answer queries of the form "is the frequency of ${\displaystyle B[i]}$ in ${\displaystyle B[i:j]}$ at least ${\displaystyle q}$" in constant time, by checking whether ${\displaystyle Q_{B[i]}[B'[i]+q-1]\leq j}$.

The array is split B into ${\displaystyle s}$ blocks ${\displaystyle b_{1},b_{2},...,b_{s}}$, each of size ${\displaystyle t=\lceil n/s\rceil }$. Thus, a block ${\displaystyle b_{i}}$ spans over ${\displaystyle B[i\cdot t+1:(i+1)t]}$. The mode and the frequency of each block or set of consecutive blocks will be pre-computed in two tables ${\displaystyle S}$ and ${\displaystyle S'}$. ${\displaystyle S[b_{i},b_{j}]}$ is the mode of ${\displaystyle b_{i}\cup b_{i+1}\cup ...\cup b_{j}}$, or equivalently, the mode of ${\displaystyle B[b_{i}t+1:(b_{j}+1)t]}$, and ${\displaystyle S'}$ stores the corresponding frequency. These two tables can be stored in ${\displaystyle O(s^{2})}$ space, and can be populated in ${\displaystyle O(s\cdot n)}$ by scanning ${\displaystyle B}$ ${\displaystyle s}$ times, computing a row of ${\displaystyle S,S'}$ each time with the following algorithm:

algorithm computeS_Sprime is
    input: Array B = [0:n - 1], 
        Array D = [0:Delta - 1], 
        Integer s
    output: Tables S and Sprime
    let S ← Table(0:n - 1, 0:n - 1)
    let Sprime ← Table(0:n - 1, 0:n - 1)
    let firstOccurence ← Array(0:Delta - 1)
    for all i in {0, ..., Delta - 1} do
        firstOccurence[i] ← -1 
    end for
    for i ← 0:s - 1 do    
        let j ← i × t
        let c ← 0
        let fc ← 0
        let noBlock ← i
        let block_start ← j
        let block_end ← min{(i + 1) × t - 1, n - 1}
        while j < n do    
            if firstOccurence[B[j]] = -1 then
                firstOccurence[B[j]] ← j
            end if		
            if atLeastQInstances(firstOccurence[B[j]], block_end, fc + 1) then
                c ← B[j]
                fc ← fc + 1
            end if		
            if j = block_end then
                S[i * s + noBlock] ← c
                Sprime[i × s + noBlock] ← fc			
                noBlock ← noBlock + 1
                block_end ← min{block_end + t, n - 1}
            end if
        end while
        for all j in {0, ..., Delta - 1} do
            firstOccurence[j] ← -1 
        end for
    end for

We will define the query algorithm over array ${\displaystyle B}$. This can be translated to an answer over ${\displaystyle A}$, since for any ${\displaystyle a,i,j}$, ${\displaystyle B[a]}$ is a mode for ${\displaystyle B[i:j]}$ if and only if ${\displaystyle A[a]}$ is a mode for ${\displaystyle A[i:j]}$. We can convert an answer for ${\displaystyle B}$ to an answer for ${\displaystyle A}$ in constant time by looking in ${\displaystyle A}$ or ${\displaystyle B}$ at the corresponding index.

Given a query ${\displaystyle mode(B,i,j)}$, the query is split in three parts: the prefix, the span and the suffix. Let ${\displaystyle b_{i}=\lceil (i-1)/t\rceil }$ and ${\displaystyle b_{j}=\lfloor j/t\rfloor -1}$. These denote the indices of the first and last block that are completely contained in ${\displaystyle B}$. The range of these blocks is called the span. The prefix is then ${\displaystyle B[i:min\{b_{i}t,j\}]}$ (the set of indices before the span), and the suffix is ${\displaystyle B[max\{(b_{j}+1)t+1,i\}:j]}$ (the set of indices after the span). The prefix, suffix or span can be empty, the latter is if ${\displaystyle b_{j}<b_{i}}$.

For the span, the mode ${\displaystyle c}$ is already stored in ${\displaystyle S[b_{i},b_{j}]}$. Let ${\displaystyle f_{c}}$ be the frequency of the mode, which is stored in ${\displaystyle S'[b_{i},b_{j}]}$. If the span is empty, let ${\displaystyle f_{c}=0}$. Recall that, by Theorem 1, the mode of ${\displaystyle B[i:j]}$ is either an element of the prefix, span or suffix. A linear scan is performed over each element in the prefix and in the suffix to check if its frequency is greater than the current candidate ${\displaystyle c}$, in which case ${\displaystyle c}$ and ${\displaystyle f_{c}}$ are updated to the new value. At the end of the scan, ${\displaystyle c}$ contains the mode of ${\displaystyle B[i:j]}$ and ${\displaystyle f_{c}}$ its frequency.

The procedure is similar for both prefix and suffix, so it suffice to run this procedure for both:

Let ${\displaystyle x}$ be the index of the current element. There are three cases:

1. If ${\displaystyle Q_{B[x]}[B'[x]-1]\geq i}$, then it was present in ${\displaystyle B[i:x-1]}$ and its frequency has already been counted. Pass to the next element.
2. Otherwise, check if the frequency of ${\displaystyle B[x]}$ in ${\displaystyle B[i:j]}$ is at least ${\displaystyle f_{c}}$ (this can be done in constant time since it is the equivalent of checking it for ${\displaystyle B[x:j]}$).
   1. If it is not, then pass to the next element.
   2. If it is, then compute the actual frequency ${\displaystyle f_{x}}$ of ${\displaystyle B[x]}$ in ${\displaystyle B[i:j]}$ by a linear scan (starting at index ${\displaystyle B'[x]+f_{c}-1}$) or a binary search in ${\displaystyle Q_{B[x]}}$. Set ${\displaystyle c:=B[x]}$ and ${\displaystyle f_{c}:=f_{x}}$.

This linear scan (excluding the frequency computations) is bounded by the block size ${\displaystyle t}$, since neither the prefix or the suffix can be greater than ${\displaystyle t}$. A further analysis of the linear scans done for frequency computations shows that it is also bounded by the block size.[1] Thus, the query time is ${\displaystyle O(t)=O(n/s)}$.

Let ${\displaystyle A[1:n]}$ be an array. The preprocessing is done in three steps:

1. Split the array ${\displaystyle A}$ in ${\displaystyle s}$ blocks ${\displaystyle b_{1},b_{2},...,b_{s}}$, where the size of each block is ${\displaystyle t=\lceil n/s\rceil }$. Build a table ${\displaystyle S}$ of size ${\displaystyle s\times s}$ where ${\displaystyle S[i,j]}$ is the mode of ${\displaystyle b_{i}\cup b_{i+1}\cup ...\cup b_{j}}$. The total space for this step is ${\displaystyle O(s^{2})}$
2. For any query ${\displaystyle mode(A,i,j)}$, let ${\displaystyle b_{i'}}$ be the block that contains ${\displaystyle i}$ and ${\displaystyle b_{j'}}$ be the block that contains ${\displaystyle j}$. Let the span be the set of blocks completely contained in ${\displaystyle A[i:j]}$. The mode ${\displaystyle c}$ of the block can be retrieved from ${\displaystyle S}$. By Theorem 1, the mode can be either an element of the prefix (indices of ${\displaystyle A[i:j]}$ before the start of the span), an element of the suffix (indices of ${\displaystyle A[i:j]}$ after the end of the span), or ${\displaystyle c}$. The size of the prefix plus the size of the suffix is bounded by ${\displaystyle 2t}$, thus the position of the mode isstored as an integer ranging from ${\displaystyle 0}$ to ${\displaystyle 2t}$, where ${\displaystyle [0:2t-1]}$indicates a position in the prefix/suffix and ${\displaystyle 2t}$ indicates that the mode is the mode of the span. There are ${\displaystyle {\binom {t}{2}}}$ possible queries involving blocks ${\displaystyle b_{i'}}$ and ${\displaystyle b_{j'}}$, so these values are stored in a table of size ${\displaystyle t^{2}}$. Furthermore, there are ${\displaystyle (2t+1)^{t^{2}}}$ such tables, so the total space required for this step is ${\displaystyle O(t^{2}(2t+1)^{t^{2}})}$. To access those tables, a pointer is added in addition to the mode in the table ${\displaystyle S}$ for each pair of blocks.
3. To handle queries ${\displaystyle mode(A,i,j)}$ where ${\displaystyle i}$ and ${\displaystyle j}$ are in the same block, all such solutions are precomputed. There are ${\displaystyle O(st^{2})}$ of them, they are stored in a three dimensional table ${\displaystyle T}$ of this size.

The total space used by this data structure is ${\displaystyle O(s^{2}+t^{2}(2t+1)^{t^{2}}+st^{2})}$, which reduces to ${\displaystyle O\left({\frac {n^{2}\log {\log {n}}}{\log {n}}}\right)}$ if we take ${\displaystyle t={\sqrt {\log {n}/\log {\log {n}}}}}$.

Given a query ${\displaystyle mode(A,i,j)}$, check if it is completely contained inside a block, in which case the answer is stored in table ${\displaystyle T}$. If the query spans exactly one or more blocks, then the answer is found in table ${\displaystyle S}$. Otherwise, use the pointer stored in table ${\displaystyle S}$ at position ${\displaystyle S[b_{i'},b_{j'}]}$, where ${\displaystyle b_{i'},b_{j'}}$ are the indices of the blocks that contain respectively ${\displaystyle i}$ and ${\displaystyle j}$, to find the table ${\displaystyle U_{b_{i'},b_{j'}}}$ that contains the positions of the mode for these blocks and use the position to find the mode in ${\displaystyle A}$. This can be done in constant time.