Отвечать на запросы о количестве различных чисел в заданном диапазоне

Question

Эта проблема

У меня есть массив с N номерами. Числа могут быть несоответствующими, а также могут быть неупорядоченными. Я должен ответить на Q вопросов о том, сколько различных чисел существует между A и B. Где A, B - индексы между 0 <= A <= B

Я знаю, как сделать это O(N) на запрос, используя HashTable, но я прошу более эффективное решение. Я попытался улучшить его с помощью декомпозиции sqrt, а также с помощью дерева сегментов, но не смог. Я не показываю никакого кода, потому что я не нашел ни одной идеи, которая работала. Я ищу кого-то, чтобы дать объяснение более быстрого решения.

ОБНОВИТЬ

Я прочитал, что вы можете собирать запросы, а затем отвечать на них, используя двоичное индексированное дерево (BIT). Может кто-нибудь объяснить, как это сделать. Предположим, я знаю, как работает BIT.

Answer 1

Для каждого индекса i найти предыдущий индекс prev[i] имеет то же значение (или -1, если такого индекса нет). Это может быть сделано в O(n) среднее значение, перейдя слева направо с помощью hash_map, тогда ответом для диапазона [l;r) индексов будет число элементов i в диапазоне [l;r), так что их значение меньше l (это требует определенного мышления, но должно быть ясно)

Теперь мы решим проблему "заданного диапазона [l;r) и значение c найти количество элементов, которые меньше, чем c"на массиве prev, Это может быть сделано в O(log^2) используя дерево сегментов, если мы сохраним в каждой вершине все числа, которые находятся в ее диапазоне (поддерево). (На каждый запрос мы получим O(log n) вершины и делать бинарный поиск по ним)