Chan et al.<ref name=":0">{{cite book |last1=Chan|first1=Timothy M. |date=2012|chapter-url=http://dx.doi.org/10.1007/978-3-642-31155-0_26 |pages=295–306|place=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|isbn=978-3-642-31154-3|access-date=2021-12-20|last2=Durocher|first2=Stephane|last3=Skala|first3=Matthew|last4=Wilkinson|first4=Bryan T.|title=Algorithm Theory – SWAT 2012 |chapter=Linear-Space Data Structures for Range Minority Query in Arrays |series=Lecture Notes in Computer Science |volume=7357 |doi=10.1007/978-3-642-31155-0_26 }}</ref> proposed a data structure that given a one-dimensional array<math>{{mvar|A</math>}}, a subrange <math>{{mvar|R</math>}} of <math>{{mvar|A</math>}} (specified at query time) and a threshold <math>\{{mvar|&tau</math>;}} (specified at query time), is able to return the list of all <math>\{{mvar|&tau</math>;}}-majorities in <math>O(1/\tau)</math> time requiring <math>O(n \log n)</math> words of space. To answer such queries, Chan et al.<ref name=":0" /> begin by noting that there exists a data structure capable of returning the ''top-k'' most frequent items in a range in <math>O(k)</math> time requiring <math>O(n)</math> words of space. For a one-dimensional array <math>A[0,..,n-1]</math>, let a one-sided top-k range query to be of form <math>A[0..i] \text</math> {{nowrap|for } <math>0 \leq i \leq n-1</math>.}} For a maximal range of ranges <math>A[0..i] \text</math> {{nowrap|through } <math>A[0..j]</math>}} in which the frequency of a distinct element <math>{{mvar|e</math>}} in <math>{{mvar|A</math>}} remains unchanged (and equal to <math>{{itco|{{mvar|f</math>}}}}), a horizontal line segment is constructed. The <math>{{mvar|x</math>}}-interval of this line segment corresponds to <math>[i,j]</math> and it has a <math>{{mvar|y</math>}}-value equal to <math>{{mvar|f</math>}}. Since adding each element to <math>{{mvar|A</math>}} changes the frequency of exactly one distinct element, the aforementioned process creates <math>O(n)</math> line segments. Moreover, for a vertical line <math>x=i</math> all horizonal line segments intersecting it are sorted according to their frequencies. Note that, each horizontal line segment with <math>{{mvar|x</math>}}-interval <math>[\ell,r]</math> corresponds to exactly one distinct element <math>{{mvar|e</math>}} in <math>{{mvar|A</math>}}, such that <math>A[\ell]=e</math>. A top-k query can then be answered by shooting a vertical ray <math>x=i</math> and reporting the first <math>{{mvar|k</math>}} horizontal line segments that intersect it (remember from above that these line segments are already sorted according to their frequencies) in <math>O(k)</math> time.
Chan et al.<ref name=":0" /> first construct a [[range tree]] in which each branching node stores one copy of the data structure described above for one-sided range top-k queries and each leaf represents an element from <math>{{mvar|A</math>}}. The top-k data structure at each node is constructed based on the values existing in the subtrees of that node and is meant to answer one-sided range top-k queries. Please note that for a one-dimensional array <math>{{mvar|A</math>}}, a range tree can be constructed by dividing <math>{{mvar|A</math>}} into two halves and recursing on both halves; therefore, each node of the resulting range tree represents a range. It can also be seen that this range tree requires <math>O(n \log n)</math> words of space, because there are <math>O(\log n)</math> levels and each level <math>\{{mvar|&ell</math>;}} has <math>2^{\ell}</math> nodes. Moreover, since at each level <math>\{{mvar|&ell</math>;}} of a range tree all nodes have a total of <math>{{mvar|n</math>}} elements of <math>{{mvar|A</math>}} at their subtrees and since there are <math>O(\log n)</math> levels, the space complexity of this range tree is <math>O(n \log n)</math>.
Using this structure, a range <math>\{{mvar|&tau</math>;}}-majority query <math>A[i..j]</math> on <math>A[0..n-1]</math> with <math>0\leq i\leq j \leq n</math> is answered as follows. First, the [[lowest common ancestor]] (LCA) of leaf nodes <math>{{mvar|i</math>}} and <math>{{mvar|j</math>}} is found in constant time. Note that there exists a data structure requiring <math>O(n)</math> bits of space that is capable of answering the LCA queries in <math>O(1)</math> time.<ref>{{Cite book|last1=Sadakane|first1=Kunihiko|last2=Navarro|first2=Gonzalo|title=Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms |chapter=Fully-Functional Succinct Trees |date=2010-01-17 |pages=134–149 |___location=Philadelphia, PA|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611973075.13|isbn=978-0-89871-701-3 |s2cid=3189222 |doi-access=free}}</ref> Let <math>{{mvar|z</math>}} denote the LCA of <math>{{mvar|i </math>}} and <math>{{mvar|j</math>}}, using <math>{{mvar|z</math>}} and according to the decomposability of range <math>\{{mvar|&tau</math>;}}-majority queries (as described above and in <ref name=":1" />), the two-sided range query <math>A[i..j]</math> can be converted into two one-sided range top-k queries (from <math>{{mvar|z</math>}} to <math>{{mvar|i</math>}} and <math>{{mvar|j</math>}}). These two one-sided range top-k queries return the top-(<math>1/\tau</math>) most frequent elements in each of their respective ranges in <math>O(1/\tau)</math> time. These frequent elements make up the set of ''candidates'' for <math>\{{mvar|&tau</math>;}}-majorities in <math>A[i..j]</math> in which there are <math>O(1/\tau)</math> candidates some of which might be false positives. Each candidate is then assessed in constant time using a linear-space data structure (as described in Lemma 3 in <ref>{{Cite journal|last1=Chan|first1=Timothy M.|last2=Durocher|first2=Stephane|last3=Larsen|first3=Kasper Green|last4=Morrison|first4=Jason|last5=Wilkinson|first5=Bryan T.|date=2013-03-08|title=Linear-Space Data Structures for Range Mode Query in Arrays|url=http://dx.doi.org/10.1007/s00224-013-9455-2|journal=Theory of Computing Systems|volume=55|issue=4|pages=719–741|doi=10.1007/s00224-013-9455-2|s2cid=253747004 |issn=1432-4350}}</ref>) that is able to determine in <math>O(1)</math> time whether or not a given subrange of an array <math>{{mvar|A</math>}} contains at least <math>{{mvar|q</math>}} instances of a particular element <math>{{mvar|e</math>}}.
