Создайте структуру данных за O (n + k) времени, которая позволит мне найти количество целых чисел в некотором диапазоне в массиве за постоянное время

Question

У меня есть массив целых чисел, и я знаю диапазон значений этих целых чисел

Я хочу создать структуру данных за время O (n + k), которая может позволить мне найти число целых чисел в некотором диапазоне в массиве за постоянное время.

Возможно ли это, хотя я не хочу сортировать массив, возможно ли это с каким-то сбалансированным деревом? AVL деревья?

Answer 1

Вы можете создать другой массив, где значения - это число значений в целевом массиве, превышающее индекс.Затем, чтобы найти число в пределах диапазона, вам просто нужно найти [max] - a [min].

Чтобы создать массив, вы можете перебирать целевой массив, увеличивая значение на индекспоисковый массив (это O (n)).Затем вы перебираете поисковый массив в обратном порядке, делая каждое значение суммой самого себя и всех значений после него в массиве (O (k), если k - диапазон данных).Конечно, для этого потребуется совсем немного памяти, в зависимости от размера вашего массива, но он будет иметь требуемые характеристики производительности.

Answer 2

дерева операций, как правило, log (n)

У меня был бы массив с размером диапазона, который я предварительно заполнил бы «числом целых чисел меньше этого значения» и возвратил бы разницу между min имаксимальная дальность задается.это постоянное время.