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

Проблема

У меня есть массив с N числами. Числа могут быть дискретными, а также могут быть неупорядоченными. Мне нужно ответить на вопросы Q о том, сколько различных чисел находится между A и B. Где A, B — индексы между 0 ‹= A ‹= B ‹ array.Length.

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

ОБНОВЛЕНИЕ

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


algorithm data-structures binary-indexed-tree
person Diego Becquer    schedule 07.01.2018    source источник
comment
Что вы подразумеваете под different numbers между A и B. Если речь идет о количестве чисел, т.е. диапазон, то почему бы просто не использовать B-A-1   -  person C0deDaedalus    schedule 07.01.2018
comment
Если у вас есть список и два произвольных числа, и вы хотите найти числа в списке между этими двумя числами, вы можете использовать двоичный поиск с временной сложностью O(logn). Это отличный ответ для начала.   -  person user3483203    schedule 07.01.2018
comment
@chrisz Он запрашивает количество различных чисел, что не может быть выполнено менее чем за O(n) (поскольку любой заданный элемент может быть дубликатом или отличным, поэтому нам нужно просмотреть каждый element), если это нужно сделать с нуля (то есть, если вопрос задавал 1 вместо Q запросов).   -  person Bernhard Barker    schedule 07.01.2018
comment
Я отредактировал вопрос. Спасибо   -  person Diego Becquer    schedule 07.01.2018
comment
Вы можете найти кое-что здесь: apps.topcoder.com/forums/ Но это правда, что нет правильного объяснения, это более эффективный рабочий код.   -  person Raudel Ravelo    schedule 07.01.2018
comment
@chrisz ты можешь еще раз прочитать? я обновил текст   -  person Diego Becquer    schedule 10.01.2018
comment
Подождите, вы просто хотите знать, основываясь на индексах? Итак, как и в массиве длиной 10, сколько уникальных чисел попадает между вторым и восьмым индексом?   -  person user3483203    schedule 10.01.2018

Ответы (1)


arrow_upward
1
arrow_downward

Для каждого индекса 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) вершин и делать в них бинарный поиск)

person RiaD    schedule 10.01.2018