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

Question

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

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

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

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

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

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

Answer 1

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

Во-первых, давайте решим следующую проблему: для данного массива ответим на запросы вида "сколько чисел <= x в индексах [l, r]". Это делается с помощью структуры, подобной сегментному дереву, которая иногда называется Merge Sort Tree. Это в основном дерево сегментов, где каждый узел хранит отсортированный подмассив. Эта структура требует 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 time): просто сделайте регулярный запрос к дереву сегментов (обходя 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]", которое тривиально сводится к тому, что я описал выше.

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

Answer 2

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

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

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

  1. Увеличение на 1 при текущем индексе i в дереве сегментов.

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

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

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

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

Answer 3

Есть известный офлайн-метод решения этой проблемы. Если у вас есть массив размером 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^ й запрос. Теперь отсортируйте вектор v на основе конечной точки запроса. Пусть у нас есть дерево сегментов, в котором может храниться информация как минимум о 10^5 элементах. и у нас также есть область, называемая last[100005]. который хранит последнюю позицию числа в массиве [].

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

O (log ^d n + k)

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

---

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

Answer 6

Основываясь на лучшем ответе Ивана Смирнова, вот его прототип реализации, написанный на Python.

      from bisect import bisect_left
import random
import time

def build_index(input):
    n = len(input)
    last = {}
    next = []
    for j in range(n):
        i = n - j - 1
        if input[i] in last:
            next.append(last[input[i]])
        else:
            next.append(n)
        last[input[i]] = i
    next.reverse()
    return next

def merge(left, right):
    answer = []
    p = 0
    q = 0
    while True:
        if p == len(left):
            if q == len(right):
                return answer
            else:
                answer.append(right[q])
                q += 1
        elif q == len(right):
            answer.append(left[p])
            p += 1
        elif left[p] < right[q]:
            answer.append(left[p])
            p += 1
        else:
            answer.append(right[q])
            q += 1

def build_tree(input, l, r):
    if r - l == 1:
        return (input[l:r], None, None)
    else:
        mid = (l + r) // 2
        left = build_tree(input, l, mid)
        right = build_tree(input, mid, r)
        merged = merge(left[0], right[0])
        return (merged, left, right)
    
def query(index, tree_left, tree_right, query_l, query_r):
    tree_width = tree_right - tree_left
    if tree_width == 1:
        if index[0][0] >= query_r:
            return 1
        else:
            return 0
    else:
        mid = (tree_left + tree_right) // 2
        if query_r <= mid:
            return query(index[1], tree_left, mid, query_l, query_r)
        elif query_l >= mid:
            return query(index[2], mid, tree_right, query_l, query_r)
        elif query_l <= tree_left and query_r >= tree_right:
            arr = index[0]
            return tree_width - bisect_left(arr, query_r)
        else:
            return query(index[1], tree_left, mid, query_l, query_r) + query(index[2], mid, tree_right, query_l, query_r)

def brute(input, i, j):
    seen = {}
    for k in range(i, j):
        seen[input[k]] = True
    return len(seen)

input = random.choices(list(range(8)), k=100000)
index = build_index(input)
tree = build_tree(index, 0, len(index))
n = len(input)
i = random.randint(0, n)
j = random.randint(i + 1, n)

t1 = time.time()
q = query(tree, 0, len(index), i, j)
t2 = time.time()
b = brute(input, i, j)
t3 = time.time()

print(q == b)
print(t2 - t1)
print(t3 - t2)