Можно ли запросить количество различных целых чисел в диапазоне за O (lg N)?

Да, это можно сделать за O(log n), даже если вам придется отвечать на запросы онлайн. Однако для этого требуются довольно сложные приемы.

Сначала решим следующую задачу: по заданному массиву ответим на запросы вида «сколько чисел ‹= x содержится в индексах [l, r]». Это делается с помощью структуры, похожей на дерево сегментов, которую иногда называют деревом сортировки слиянием. По сути, это дерево сегментов, в котором каждый узел хранит отсортированный подмассив. Эта структура требует O(n log n) памяти (поскольку существует log n слоев, и каждый из них требует хранения n чисел). Он также построен на O(n log n): вы просто идете снизу вверх и для каждой внутренней вершины объединяете отсортированные списки ее дочерних элементов.

Вот пример. Скажем, 1 5 2 6 8 4 7 1 будет исходным массивом.

|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|

Теперь вы можете ответить на эти запросы за время O(log^2 n): просто сделайте регулярный запрос к дереву сегментов (обходя O(log n) узлов) и выполните бинарный поиск, чтобы узнать, сколько чисел ‹= x существует. в этом узле (дополнительно O (log n) отсюда).

Это можно ускорить до O(log n) с помощью дробного каскадирования, который в основном позволяет вам делать бинарный поиск не в каждом узле, а только в корне. Однако это достаточно сложно, чтобы описать его в посте.

Теперь вернемся к исходной задаче. Предположим, у вас есть массив a_1,..., a_n. Создайте еще один массив b_1, ..., b_n, где b_i = индекс следующего вхождения a_i в массиве или ∞, если это последнее вхождение.

Пример (1-индексированный):

a = 1 3 1 2 2 1 4 1
b = 3 ∞ 6 5 ∞ 8 ∞ ∞

Теперь посчитаем числа в [l, r]. Для каждого уникального числа мы посчитаем его последнее появление в сегменте. С понятием b_i вы можете видеть, что вхождение числа является последним тогда и только тогда, когда b_i > r. Таким образом, проблема сводится к тому, «сколько чисел > r в отрезке [l, r]», что тривиально сводится к тому, что я описал выше.

Надеюсь, поможет.

Данная проблема также может быть решена с использованием алгоритма Мо (офлайн), также называемого алгоритмом разложения квадратного корня.

Общая временная сложность составляет O(N*SQRT(N)).

Обратитесь к mos-algorithm для подробного объяснения, он даже имеет анализ сложности и проблему SPOJ, которая может решить при таком подходе.

Существует хорошо известный офлайн-метод для решения этой проблемы. Если у вас есть массив размера n и q запросов к нему и в каждом запросе, вам нужно знать количество различных чисел в этом диапазоне, тогда вы можете решить все это за время сложности O (n log n + q log n). Что похоже на решение каждого запроса за время O (log n).

Давайте решим задачу, используя метод RSQ (запрос суммы диапазона). Для метода RSQ вы можете использовать дерево сегментов или BIT. Давайте обсудим метод дерева сегментов.

Для решения этой задачи вам понадобится автономная методика и дерево сегментов. Теперь, что такое автономная техника?? Офлайновая техника делает что-то в офлайне. При решении проблем примером автономной техники является то, что вы сначала вводите все запросы, а затем переупорядочиваете их, чтобы вы могли ответить на них правильно и легко и, наконец, вывести ответы в заданном порядке ввода.

Идея решения:

Сначала возьмите входные данные для тестового примера и сохраните заданные n чисел в массиве. Пусть массив имеет имя array[] и принимает входные запросы q и сохраняет их в векторе v. где каждый элемент v содержит три поля — l, r, idx. где l — начальная точка запроса, r — конечная точка запроса, а idx — количество запросов. например, это n^th запрос. Теперь отсортируйте вектор v на основе конечной точки запроса. Пусть у нас есть дерево отрезков, в котором может храниться информация хотя бы о 10^5 элементах. и у нас также есть область с именем last[100005]. который хранит последнюю позицию числа в массиве [].

Изначально все элементы дерева равны нулю, а все элементы последнего равны -1. теперь запустите цикл на массиве []. теперь внутри цикла вы должны проверить это для каждого индекса массива [].

last[array[i]] равно -1 или нет? если это -1, то напишите last[array[i]]=i и вызовите функцию update(), которая добавит +1 в позицию last[array[i]] дерева сегментов. если last[array[i]] не равен -1, то вызовите функцию update() дерева сегментов, которая вычтет 1 или добавит -1 в позицию last[array[i]] дерева сегментов. Теперь вам нужно сохранить текущую позицию как последнюю позицию на будущее. поэтому вам нужно написать last[array[i]]=i и вызвать функцию update(), которая добавит +1 в позицию last[array[i]] дерева сегментов.

Теперь вам нужно проверить, завершен ли запрос в текущем индексе. то есть если (v[current].r==i). если это так, то вызовите функцию query() дерева сегментов, которая вернет и суммирует диапазон от v[current].l до v[current].r и сохранит результат в индексе v[current].idx^th массив ответов []. вам также нужно увеличить значение current на 1. 6. Теперь напечатайте массив answer[], который содержит ваш окончательный ответ в заданном порядке ввода.

сложность алгоритма O (n log n).

kd-trees обеспечивают диапазон запросов в O(logn), где n – количество точек. .

Если вам нужен более быстрый запрос, чем kd-дерево, и вы готовы платить за память, тогда деревья диапазонов ваши друзья, предлагающие запрос:

O(log^dn + k)

где n — количество точек, хранящихся в дереве, d — размерность каждой точки, а k — количество точек, о которых сообщает данный запрос.

_{Bentley — важное имя в этой области. :)}

Если вы готовы отвечать на запросы в автономном режиме, старые добрые деревья сегментов/BIT все еще могут помочь.

• Сортировка запросов на основе значений r.
• Создайте дерево сегментов для запросов суммы диапазона [0, n]

• Для каждого значения во входном массиве слева направо:

  1. Increment by 1 at current index i in the segment tree.

  2. Для текущего элемента, если он был замечен ранее, уменьшается на 1 в
     дереве сегментов в его предыдущей позиции.

  3. Отвечайте на запросы, оканчивающиеся на текущий индекс i, запрашивая сумму в диапазоне [l, r == i].

Короче говоря, идея состоит в том, чтобы продолжать отмечать правые индексы, последнее вхождение каждого отдельного элемента и устанавливать предыдущие вхождения обратно в 0. Сумма диапазона даст количество уникальных элементов.

Общая временная сложность снова будет равна nLogn.