Запрос диапазона (информатика)

Тон или стиль этой статьи может не отражать энциклопедический тон , используемый в Википедии . См. руководство Википедии по написанию лучших статей для предложений. ( Декабрь 2017 ) ( Узнайте, как и когда удалять это сообщение )

В информатике проблема запроса диапазона состоит в эффективном ответе на несколько запросов относительно заданного интервала элементов в массиве . Например, распространенная задача, известная как запрос минимума диапазона , заключается в поиске наименьшего значения внутри заданного диапазона в списке чисел.

Учитывая функцию , которая принимает массив, запрос диапазона для массива принимает два индекса и и возвращает результат при применении к подмассиву . Например, для функции , которая возвращает сумму всех значений в массиве, запрос диапазона возвращает сумму всех значений в диапазоне . ^{[ необходима цитата ]}${\displaystyle f}$${\displaystyle f_{q}(л,р)}$${\displaystyle a=[a_{1},..,a_{n}]}$${\displaystyle л}$${\displaystyle r}$${\displaystyle f}$${\displaystyle [a_{l},\ldots ,a_{r}]}$${\displaystyle \operatorname {сумма} }$${\displaystyle \operatorname {сумма} _{q}(l,r)}$${\displaystyle [л,р]}$

Запросы суммы диапазона могут быть получены за постоянное время и линейное пространство путем предварительного вычисления массива p той же длины, что и входные данные, так что для каждого индекса i элемент p _i является суммой первых i элементов a . Любой запрос может быть затем вычислен следующим образом:$${\displaystyle \operatorname {сумма} _{q}(l,r)=p_{r}-p_{l-1}.}$$

Эту стратегию можно распространить на любую другую бинарную операцию , обратная функция которой хорошо определена и легко вычисляется. ^[1] Ее также можно распространить на более высокие измерения с аналогичной предварительной обработкой. ^[2] Например, если p _i,j содержит сумму первых i × j элементов a , то${\displaystyle f}$ ${\displaystyle f^{-1}}$$${\displaystyle \operatorname {сумма} _{q}(l,r,t,b)=p_{r,b}-p_{l-1,b}-p_{r,t-1}+p_{l-1,t-1}.}$$

Более сложная подгруппа проблемы состоит из выполнения запросов диапазона на динамических данных; то есть данных, которые могут мутировать между каждым запросом. Для эффективного обновления значений массива необходимы более сложные структуры данных, такие как дерево сегментов или дерево Фенвика . ^{[ необходима цитата ]}

Когда интересующая функция в запросе диапазона является полугрупповым оператором, понятие не всегда определено, поэтому стратегия в предыдущем разделе не работает. Эндрю Яо показал ^[3] , что существует эффективное решение для запросов диапазона, которые включают полугрупповые операторы. Он доказал, что для любой константы c предварительная обработка времени и пространства позволяет отвечать на запросы диапазона в списках, где f является полугрупповым оператором по времени, где является определенным функциональным обращением функции Аккермана .${\displaystyle f^{-1}}$${\displaystyle \Тета (c\cdot n)}$${\displaystyle \theta (\alpha _{c}(n))}$${\displaystyle \альфа _{c}}$

Существуют некоторые операторы полугрупп, которые допускают немного лучшие решения. Например, когда . Предположим , то возвращает индекс минимального элемента . Затем обозначает соответствующий запрос минимального диапазона. Существует несколько структур данных, которые позволяют ответить на запрос минимального диапазона во времени, используя предварительную обработку времени и пространства . Одно из таких решений основано на эквивалентности между этой проблемой и проблемой наименьшего общего предка .${\displaystyle f\in \{\max ,\min \}}$${\displaystyle f=\мин}$${\displaystyle \min(A[1..n])}$${\displaystyle A[1..n]}$${\textstyle \min _{i,j}(A)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

Декартово дерево массива имеет в качестве корня и в качестве левого и правого поддеревьев декартово дерево и декартово дерево соответственно. Запрос на минимальный диапазон является наименьшим общим предком в и . Поскольку наименьший общий предок может быть решен за постоянное время с использованием предварительной обработки времени и пространства , запрос на минимальный диапазон также может быть решен. Решение при аналогично. Декартовы деревья могут быть построены за линейное время .${\displaystyle T_{A}}$${\displaystyle A[1,n]}$${\displaystyle a_{i}=\min\{a_{1},a_{2},\ldots ,a_{n}\}}$${\displaystyle A[1,i-1]}$${\displaystyle A[i+1,n]}$${\textstyle \min _{i,j}(A)}$${\displaystyle T_{A}}$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle O(n)}$${\displaystyle f=\макс }$

Режим массива — это элемент, который появляется в нем чаще всего. Например, режим — это${\displaystyle а=[4,5,6,7,4]}$4 . В случае равенства любой из наиболее частых элементов может быть выбран в качестве моды. Запрос диапазона моды заключается в предварительной обработке, так что мы можем найти моду в любом диапазоне . Для решения этой проблемы было разработано несколько структур данных, мы суммируем некоторые результаты в следующей таблице. ^[1]${\displaystyle A[1,n]}$${\displaystyle A[1,n]}$

Запросы режима диапазона

Космос	Время запроса	Ограничения
${\displaystyle O(n^{2-2\epsilon})}$	${\displaystyle O(n^{\epsilon }\log n)}$	${\displaystyle 0\leq \epsilon \leq {\frac {1}{2}}}$
${\displaystyle O\left({\frac {n^{2}\log \log n}{\log n}}\right)}$	${\displaystyle O(1)}$

Недавно Йоргенсен и др. доказали нижнюю границу для модели клеточного зонда для любой структуры данных, которая использует S- клетки. ^[4]${\displaystyle \Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)}$

Этот частный случай представляет особый интерес, поскольку нахождение медианы имеет несколько приложений. ^[5] С другой стороны, медианная задача, частный случай задачи выбора , разрешима за O ( n ), используя алгоритм медианы медиан . ^[6] Однако ее обобщение посредством запросов на медиану диапазона появилось недавно. ^[7] Запрос на медиану диапазона , где A,i и j имеют обычные значения, возвращает элемент медианы . Эквивалентно, должен возвращать элемент ранга . Запросы на медиану диапазона не могут быть решены с помощью любого из предыдущих методов, обсуждавшихся выше, включая подход Яо для операторов полугруппы. ^[8]${\displaystyle \operatorname {медиана} (A,i,j)}$${\displaystyle A[i,j]}$${\displaystyle \operatorname {медиана} (A,i,j)}$${\displaystyle A[i,j]}$${\displaystyle {\frac {ji}{2}}}$

Были изучены два варианта этой проблемы: офлайн -версия, где все k интересующих запросов задаются в пакете, и версия, где вся предварительная обработка выполняется заранее. Офлайн-версия может быть решена с помощью времени и пространства.${\displaystyle O(n\log k+k\log n)}$${\displaystyle O(n\log k)}$

Следующий псевдокод алгоритма быстрого выбора показывает, как найти элемент ранга r в несортированном массиве различных элементов, чтобы найти заданные нами медианы диапазона . ^[7]${\displaystyle A[i,j]}$${\displaystyle r={\frac {ji}{2}}}$

rangeMedian(A, i, j, r) { если A.length() == 1 вернуть A[1] если A.low не определен , то m = медиана(A) A.low = [e в A | e <= m] A.high = [e в A | e > m ] вычислить t количество элементов A[i, j], которые принадлежат A.low если r <= t, то  вернуть rangeMedian(A.low, i, j, r), иначе  вернуть rangeMedian(A.high, i, j, rt)}

Процедура rangeMedianразбивает A, используя Aмедиану , на два массива A.lowи A.high, где первый содержит элементы , Aкоторые меньше или равны медиане m, а второй — остальные элементы A. Если мы знаем, что количество элементов , которые попадают в , равно и это число больше , то мы должны продолжать искать элемент ранга в ; в противном случае мы должны искать элемент ранга в . Чтобы найти t , достаточно найти максимальный индекс такой, что находится в , и максимальный индекс такой, что находится в . Тогда . Общая стоимость любого запроса, без учета части разбиения, равна , поскольку выполняется максимум рекурсивных вызовов и в каждом из них выполняется только постоянное количество операций (чтобы получить значение t , следует использовать дробное каскадирование ). Если используется линейный алгоритм для поиска медиан, общая стоимость предварительной обработки для медианных запросов в диапазоне k составляет . Алгоритм также можно модифицировать для решения онлайн- версии задачи. ^[7]${\displaystyle A[i,j]}$A.lowtrrA.low${\displaystyle (rt)}$A.high${\displaystyle m\leq i-1}$${\displaystyle а_{м}}$A.low${\displaystyle l\leq j}$${\displaystyle а_{л}}$A.high${\displaystyle t=лм}$${\displaystyle \log n}$${\displaystyle \log n}$ ${\displaystyle n\log k}$

Поиск частых элементов в заданном наборе элементов является одной из самых важных задач в интеллектуальном анализе данных. Поиск частых элементов может быть сложной задачей, когда большинство элементов имеют схожие частоты. Поэтому может быть более полезным, если для обнаружения таких элементов используется некоторый порог значимости. Один из самых известных алгоритмов для поиска большинства в массиве был предложен Бойером и Муром ^[9] , который также известен как алгоритм большинства голосов Бойера–Мура . Бойер и Мур предложили алгоритм для поиска большинства элемента строки (если он есть) во времени и с использованием пространства. В контексте работы Бойера и Мура и вообще говоря, большинство элементов в наборе элементов (например, строки или массива) — это тот, количество экземпляров которого составляет более половины размера этого набора. Несколько лет спустя Мисра и Грис ^[10] предложили более общую версию алгоритма Бойера и Мура, использующую сравнения для поиска всех элементов в массиве, относительные частоты которых больше некоторого порога . Запрос range -majority — это запрос, который, учитывая поддиапазон структуры данных (например, массив) размером , возвращает набор всех отдельных элементов, которые появляются более (или в некоторых публикациях равно) раз в этом заданном диапазоне. В различных структурах, которые поддерживают запросы range -majority, может быть либо статическим (указывается во время предварительной обработки), либо динамическим (указывается во время запроса). Многие из таких подходов основаны на том факте, что независимо от размера диапазона для заданного может быть не более отдельных кандидатов с относительными частотами не менее . Проверяя каждого из этих кандидатов за постоянное время, достигается время запроса. Запрос range -majority является разложимым ^[11] в том смысле, что -majority в диапазоне с разделами и должно быть -majority в либо . Благодаря этой разложимости некоторые структуры данных отвечают на большинство запросов на одномерных массивах, находя наименьшего общего предка (LCA) конечных точек диапазона запроса в дереве диапазонов и проверяя два набора кандидатов (размером ) от каждой конечной точки до наименьшего общего предка за постоянное время, что приводит к времени запроса.${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle O\left(n\log \left({\frac {1}{\tau }}\right)\right)}$${\displaystyle 0<\тау <1}$${\displaystyle \тау}$${\displaystyle |Р|}$${\displaystyle \тау |R|}$${\displaystyle \тау}$${\displaystyle \тау}$${\displaystyle \тау}$${\displaystyle O(1/\тау)}$${\displaystyle \тау}$${\displaystyle O(1/\тау)}$${\displaystyle \тау}$${\displaystyle \тау}$${\displaystyle R}$${\displaystyle R_{1}}$${\displaystyle R_{2}}$${\displaystyle \тау}$${\displaystyle R_{1}}$${\displaystyle R_{2}}$${\displaystyle \тау}$${\displaystyle O(1/\тау)}$${\displaystyle O(1/\тау)}$

Gagie et al. ^[12] предложили структуру данных, которая поддерживает запросы range-majority на массиве . Для каждого запроса в этой структуре данных указываются порог и прямоугольный диапазон , а набор всех элементов, которые имеют относительные частоты (внутри этого прямоугольного диапазона) больше или равные, возвращается в качестве выходных данных. Эта структура данных поддерживает динамические пороги (указанные во время запроса) и порог предварительной обработки, на основе которого она строится. Во время предварительной обработки на массиве строится набор вертикальных и горизонтальных интервалов . Вместе вертикальный и горизонтальный интервалы образуют блок. Каждый блок является частью суперблока, который в девять раз больше его самого (в три раза больше размера горизонтального интервала блока и в три раза больше размера его вертикального). Для каждого блока хранится набор кандидатов (с элементами не более), который состоит из элементов, которые имеют относительные частоты не менее (порог предварительной обработки, как указано выше) в его соответствующем суперблоке. Эти элементы хранятся в невозрастающем порядке в соответствии с их частотами, и легко увидеть, что любой элемент, имеющий относительную частоту хотя бы в блоке, должен появиться в его наборе кандидатов. На каждый запрос -majority сначала отвечают путем нахождения блока запроса или самого большого блока, который содержится в предоставленном прямоугольнике запроса за время. Для полученного блока запроса первые кандидаты возвращаются (без проверки) за время, поэтому этот процесс может возвращать некоторые ложные срабатывания. Многие другие структуры данных (как обсуждается ниже) предложили методы для проверки каждого кандидата за постоянное время и, таким образом, поддержания времени запроса при отсутствии ложных срабатываний. Случаи, в которых блок запроса меньше, обрабатываются путем сохранения различных экземпляров этой структуры данных в следующей форме:${\displaystyle \тау}$${\displaystyle m\times n}$${\displaystyle А}$${\displaystyle \operatorname {Q} =(\operatorname {R} ,\tau )}$${\displaystyle 0<\тау <1}$${\displaystyle \operatorname {R} }$${\displaystyle \тау}$${\displaystyle \альфа}$${\displaystyle m\times n}$${\displaystyle {\frac {9}{\alpha }}}$${\displaystyle {\frac {\alpha }{9}}}$${\displaystyle \альфа}$${\displaystyle \тау}$${\displaystyle O(1)}$${\displaystyle {\frac {9}{\tau }}}$${\displaystyle O(1/\тау)}$${\displaystyle O(1/\тау)}$${\displaystyle 1/\alpha }$${\displaystyle \log \left({\frac {1}{\alpha }}\right)}$

${\displaystyle \beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}}$

где — порог предварительной обработки -го экземпляра. Таким образом, для блоков запроса, меньших, чем -й экземпляр, запрашивается. Как упоминалось выше, эта структура данных имеет время запроса и требует бит пространства, сохраняя его копию, закодированную по Хаффману (обратите внимание на фактор, а также см. кодирование Хаффмана ).${\displaystyle \beta }$${\displaystyle i}$${\displaystyle 1/\alpha }$${\displaystyle \lceil \log(1/\tau )\rceil }$${\displaystyle O(1/\tau )}$${\displaystyle O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)}$${\displaystyle \log({\frac {1}{\alpha }})}$

Чан и др. ^[13] предложили структуру данных, которая при заданном одномерном массиве , поддиапазоне ( указанном во время запроса) и пороге (указанном во время запроса) способна возвращать список всех -большинств за время, требующее слов пространства. Чтобы ответить на такие запросы, Чан и др. ^[13] начинают с того, что отмечают, что существует структура данных, способная возвращать самые частые элементы top-k в диапазоне за время, требующее слов пространства. Для одномерного массива пусть односторонний запрос top-k диапазона имеет вид . Для максимального диапазона диапазонов , в котором частота отдельного элемента в остается неизменной (и равной ), строится горизонтальный отрезок линии. -Интервал этого отрезка линии соответствует и он имеет -значение, равное . Поскольку добавление каждого элемента к изменяет частоту ровно одного отдельного элемента, вышеупомянутый процесс создает отрезки линии. Более того, для вертикальной линии все пересекающие ее горизонтальные отрезки линии сортируются в соответствии с их частотами. Обратите внимание, что каждый горизонтальный отрезок линии с -интервалом соответствует ровно одному отдельному элементу в , так что . Затем на запрос top-k можно ответить, испуская вертикальный луч и сообщая о первых горизонтальных отрезках линии, которые пересекают его (помните из вышеизложенного, что эти отрезки линии уже отсортированы в соответствии с их частотами) во времени.${\displaystyle A}$${\displaystyle R}$${\displaystyle A}$${\displaystyle \tau }$${\displaystyle \tau }$${\displaystyle O(1/\tau )}$${\displaystyle O(n\log n)}$${\displaystyle O(k)}$${\displaystyle O(n)}$${\displaystyle A[0,..,n-1]}$${\displaystyle A[0..i]{\text{ for }}0\leq i\leq n-1}$${\displaystyle A[0..i]{\text{ through }}A[0..j]}$${\displaystyle e}$${\displaystyle A}$${\displaystyle f}$${\displaystyle x}$${\displaystyle [i,j]}$${\displaystyle y}$${\displaystyle f}$${\displaystyle A}$${\displaystyle O(n)}$${\displaystyle x=i}$${\displaystyle x}$${\displaystyle [\ell ,r]}$${\displaystyle e}$${\displaystyle A}$${\displaystyle A[\ell ]=e}$${\displaystyle x=i}$${\displaystyle k}$${\displaystyle O(k)}$

Чан и др. ^[13] сначала строят дерево диапазонов , в котором каждый узел ветвления хранит одну копию структуры данных, описанной выше для односторонних запросов диапазона top-k, а каждый лист представляет элемент из . Структура данных top-k в каждом узле строится на основе значений, существующих в поддеревьях этого узла, и предназначена для ответа на односторонние запросы диапазона top-k. Обратите внимание, что для одномерного массива дерево диапазонов можно построить путем деления на две половины и рекурсии на обеих половинах; следовательно, каждый узел полученного дерева диапазонов представляет собой диапазон. Также можно увидеть, что это дерево диапазонов требует слов пространства, потому что есть уровни, а на каждом уровне есть узлы. Более того, поскольку на каждом уровне дерева диапазонов все узлы имеют в своих поддеревьях в общей сложности элементов и поскольку есть уровни, пространственная сложность этого дерева диапазонов составляет .${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle O(n\log n)}$${\displaystyle O(\log n)}$${\displaystyle \ell }$${\displaystyle 2^{\ell }}$${\displaystyle \ell }$${\displaystyle n}$${\displaystyle A}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

Используя эту структуру, запрос диапазона -majority на с отвечает следующим образом. Во-первых, наименьший общий предок (LCA) листовых узлов и находится за постоянное время. Обратите внимание, что существует структура данных, требующая бит пространства, которая способна отвечать на запросы LCA за время. ^[14] Пусть обозначит LCA и , используя и в соответствии с разложимостью запросов диапазона -majority (как описано выше и в ^[11] ), двусторонний запрос диапазона может быть преобразован в два односторонних запроса диапазона top-k (от до и ). Эти два односторонних запроса диапазона top-k возвращают top-( ) наиболее частые элементы в каждом из их соответствующих диапазонов по времени. Эти частые элементы составляют набор кандидатов для -majorities в , в котором есть кандидаты, некоторые из которых могут быть ложноположительными. Затем каждый кандидат оценивается за постоянное время с использованием линейно-пространственной структуры данных (как описано в лемме 3 в ^[15] ), которая способна определить за время, содержит ли заданный поддиапазон массива по крайней мере экземпляры определенного элемента .${\displaystyle \tau }$${\displaystyle A[i..j]}$${\displaystyle A[0..n-1]}$${\displaystyle 0\leq i\leq j\leq n}$${\displaystyle i}$${\displaystyle j}$${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle z}$${\displaystyle i}$${\displaystyle j}$${\displaystyle z}$${\displaystyle \tau }$${\displaystyle A[i..j]}$${\displaystyle z}$${\displaystyle i}$${\displaystyle j}$${\displaystyle 1/\tau }$${\displaystyle O(1/\tau )}$${\displaystyle \tau }$${\displaystyle A[i..j]}$${\displaystyle O(1/\tau )}$${\displaystyle O(1)}$${\displaystyle A}$${\displaystyle q}$${\displaystyle e}$

Gagie et al. ^[16] предложили структуру данных, которая поддерживает запросы, такие, что при наличии двух узлов и в дереве они могут сообщать список элементов, которые имеют большую относительную частоту, чем на пути от до . Более формально, пусть будет помеченным деревом, в котором каждый узел имеет метку из алфавита размера . Пусть обозначит метку узла в . Пусть обозначит уникальный путь от до в , в котором средние узлы перечислены в порядке их посещения. При наличии и фиксированного (указанного во время предварительной обработки) порога , запрос должен возвращать набор всех меток, которые встречаются более раз в .${\displaystyle u}$${\displaystyle v}$${\displaystyle \tau }$${\displaystyle u}$${\displaystyle v}$${\displaystyle T}$${\displaystyle \sigma }$${\displaystyle label(u)\in [1,\dots ,\sigma ]}$${\displaystyle u}$${\displaystyle T}$${\displaystyle P_{uv}}$${\displaystyle u}$${\displaystyle v}$${\displaystyle T}$${\displaystyle T}$${\displaystyle 0<\tau <1}$${\displaystyle Q(u,v)}$${\displaystyle \tau |P_{uv}|}$${\displaystyle P_{uv}}$

Для построения этой структуры данных сначала узлы помечаются . Это можно сделать, пометив любой узел, который находится на расстоянии не менее от нижней части трех (высота) и глубина которого делится на . После этого можно заметить, что расстояние между каждым узлом и его ближайшим помеченным предком меньше . Для помеченного узла хранятся различные последовательности (пути к корню) ,${\displaystyle {O}(\tau n)}$${\displaystyle \lceil 1/\tau \rceil }$${\displaystyle \lceil 1/\tau \rceil }$${\displaystyle 2\lceil 1/\tau \rceil }$${\displaystyle x}$${\displaystyle \log(depth(x))}$${\displaystyle P_{i}(x)}$

${\displaystyle P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle }$

для , где возвращает метку прямого родителя узла . Иными словами, для каждого отмеченного узла хранится набор всех путей с длиной, равной степени двух (плюс один для самого узла) к корню. Более того, для каждого хранится набор всех кандидатов большинства. Более конкретно, содержит набор всех -большинств в или меток, которые появляются больше, чем раз в . Легко видеть, что набор кандидатов может иметь не более различных меток для каждого . Затем Гаги и др. ^[16] отмечают, что набор всех -большинств в пути от любого отмеченного узла до одного из его предков включен в некоторые (лемма 2 в ^[16] ), поскольку длина равна , таким образом, существует для , длина которого находится между , где - расстояние между x и z. Существование таких подразумевает, что -большинство в пути от до должно быть -большинством в , и, таким образом, должно появляться в . Легко видеть, что эта структура данных требует слов пространства, потому что, как упоминалось выше, на этапе построения узлы помечаются, и для каждого помеченного узла хранятся некоторые наборы кандидатов. По определению, для каждого помеченного узла такие наборы являются хранилищами, каждое из которых содержит кандидатов. Поэтому эта структура данных требует слов пространства. Обратите внимание, что каждый узел также хранит что равно количеству экземпляров на пути от к корню , это не увеличивает сложность пространства, поскольку добавляет только постоянное количество слов на узел.${\displaystyle 0\leq i\leq \log(depth(x))}$${\displaystyle \operatorname {par} (x)}$${\displaystyle x}$${\displaystyle P_{i}(x)}$ ${\displaystyle C_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle (\tau /2)}$${\displaystyle P_{i}(x)}$${\displaystyle (\tau /2).(2^{i}+1)}$${\displaystyle P_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle 2/\tau }$${\displaystyle i}$${\displaystyle \tau }$${\displaystyle x}$${\displaystyle z}$${\displaystyle C_{i}(x)}$${\displaystyle P_{i}(x)}$${\displaystyle (2^{i}+1)}$${\displaystyle P_{i}(x)}$${\displaystyle 0\leq i\leq \log(depth(x))}$${\displaystyle d_{xz}{\text{ and }}2d_{xz}}$${\displaystyle d_{xz}}$${\displaystyle P_{i}(x)}$${\displaystyle \tau }$${\displaystyle x}$${\displaystyle z}$${\displaystyle (\tau /2)}$${\displaystyle P_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle O(n\log n)}$${\displaystyle O(\tau n)}$${\displaystyle O(\log n)}$${\displaystyle O(1/\tau )}$${\displaystyle O(\log n\times (1/\tau )\times \tau n)=O(n\log n)}$${\displaystyle x}$${\displaystyle count(x)}$${\displaystyle label(x)}$${\displaystyle x}$${\displaystyle T}$

На каждый запрос между двумя узлами и можно ответить, используя свойство разложения (как объяснено выше) запросов range -majority и разбив путь запроса между и на четыре подпути. Пусть будет наименьшим общим предком и , причем и будут ближайшими отмеченными предками и соответственно. Путь от до разлагается на пути от и до и соответственно (размер этих путей меньше, чем по определению, все из которых рассматриваются как кандидаты), и пути от и до (путем нахождения подходящего , как объяснено выше, и рассмотрения всех его меток как кандидатов). Обратите внимание, что граничные узлы должны обрабатываться соответствующим образом, чтобы все эти подпути были непересекающимися, и из всех них выводится набор кандидатов. Затем каждый из этих кандидатов проверяется с помощью комбинации запроса , который возвращает наименьшего предка узла , имеющего метку, и полей каждого узла. На -битной оперативной памяти и алфавите размером запрос может быть дан за время, имея линейные требования к пространству. ^[17] Таким образом, проверка каждого из кандидатов во времени приводит к общему времени запроса для возврата набора всех -большинств на пути от до .${\displaystyle u}$${\displaystyle v}$${\displaystyle \tau }$${\displaystyle u}$${\displaystyle v}$${\displaystyle z}$${\displaystyle u}$${\displaystyle v}$${\displaystyle x}$${\displaystyle y}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle x}$${\displaystyle y}$${\displaystyle 2\lceil 1/\tau \rceil }$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle C_{i}(x)}$${\displaystyle O(1/\tau )}$${\displaystyle labelanc(x,\ell )}$${\displaystyle x}$${\displaystyle \ell }$${\displaystyle count(x)}$${\displaystyle w}$${\displaystyle \sigma }$${\displaystyle labelanc(x,\ell )}$${\displaystyle O\left(\log \log _{w}\sigma \right)}$${\displaystyle O(1/\tau )}$${\displaystyle O\left(\log \log _{w}\sigma \right)}$${\displaystyle O\left((1/\tau )\log \log _{w}\sigma \right)}$${\displaystyle \tau }$${\displaystyle u}$${\displaystyle v}$

Все проблемы, описанные выше, были изучены для более высоких измерений, а также их динамических версий. С другой стороны, запросы диапазона могут быть расширены на другие структуры данных, такие как деревья , ^[8], такие как проблема предка уровня . Похожее семейство проблем — это запросы ортогонального диапазона , также известные как запросы подсчета.

• Проблема предка уровня
• Наименьший общий предок

• Открытая структура данных - Глава 13 - Структуры данных для целых чисел
• Структуры данных для запросов с медианным диапазоном — Герт Столтинг Бродал и Аллан Грёнлунд Йоргенсен