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

Я прочитал несколько руководств о двух общих структурах данных, которые могут обеспечить обновление диапазона и запрос в O (lg N): Дерево сегментов и двоичное индексированное дерево (BIT/Fenwick Tree).

Большинство примеров, которые я нашел, - это некоторые ассоциативные и коммутативные операции, такие как "Сумма целых чисел в диапазоне", "Целочисленные числа XOR в диапазоне" и т.д.

Интересно, могут ли эти две структуры данных (или любые другие структуры данных/алгоритм предложить) можно выполнить следующий запрос в O (lg N)? (Если нет, как насчет O (sqrt N))

Если задан массив целых чисел A, запросите количество различных целых чисел в диапазоне [l, r]

PS: Предполагая, что число доступных целых чисел равно ~ 10 ^ 5, поэтому used[color] = true или bitmask не возможно

Например: A = [1,2,3,2,4,3,1], query ([2,5]) = 3, где индекс диапазона основан на 0.

Ответ 1

Да, это можно сделать в 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) с использованием метода Fractional Cascading, что в основном позволяет выполнять двоичный поиск не в каждом узле, а только в корне. Однако достаточно сложно описать это сообщение.

Теперь вернемся к исходной проблеме. Предположим, у вас есть массив 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]", которая тривиально сводится к тому, что я описал выше.

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

Ответ 2

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

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

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

Ответ 3

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

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

O (log ^d n + k)

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

_{Bentley - важное имя, когда дело касается этой области.}_:)