Получить k-мельчайшие элементы в диапазоне, отсортированном с помощью Sparse Table в O (klogk) - PullRequest
0 голосов
/ 25 декабря 2018

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

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

Проблема:

Учитывая разреженную таблицу массива, мы хотим добавить еще один запрос для получения k-мельчайших элементов в отсортированном диапазоне (в порядке возрастания).

Query input  : k, left index, right index
Query output : k smallest elements in range sorted

Решение без использования разреженной таблицы:

Мы можем получить k-мельчайшие элементы, отсортированные с помощью Алгоритм выбора , но сложность по времени будет O (L + klogk) где L - длина диапазона (k <= L <= n). </p>

Но как мы можем использовать Sparse Table, чтобы вместо этого уменьшить временную сложность запроса до O (klogk)O (L + Клогк)?

1 Ответ

0 голосов
/ 25 декабря 2018

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

Решением для этого является использование min Binary Heap и вставляем корень дерева, а затем k раз мы удаляем элемент min из кучи и вставляем его сыновей в дерево.

Псевдокод для задачи о декартовом дереве:

minValues(k, root):
  arr  = Array[0 . . . k - 1]
  heap = emptyMinHeap()

  heap.insert(root)
  for(i = 0 . . . k - 1):
      node <- heap.pop()
      arr[i] <- node.key

      if node has left son:  heap.insert(node.left)
      if node has right son: heap.insert(node.right)

  return arr

Причина, по которой это работает, заключается в том, что дочерние элементы узла в декартовом дереве не меньше, чем сам узел.Итак, мы знаем, что самый маленький узел находится в корне, и, следовательно, это первый из K самых маленьких.Теперь, по аналогичному аргументу, следующий наименьший элемент должен быть одним из двух дочерних элементов этого узла.Следующим наименьшим будет либо другой потомок корня, либо один из двух потомков узла, который мы только что взяли, и так далее ...

Соу, как мы можем использовать это для решениянаша проблема?

Мы можем «обработать» любой конкретный диапазон в массиве как декартово дерево, сказав, что минимальное значение в диапазоне является корнем (мы можем найти его в O (1), используяразреженной таблицы), и его левый потомок является значением min между корнем и самым левым индексом (если только значение min не находится в самом левом индексе и в этом случае оно будет равно NULL), а правый потомок левого дочернего элемента являетсямин между левым потомком и корнем, и мы можем продолжать таким образом, чтобы получить дочерние элементы каждого узла без фактического построения декартового дерева.

Таким образом, мы можем использовать тот же алгоритм для декартового дерева, но вместо вставки в узлы кучииз декартового дерева мы вставляем диапазон поддерева узла, и ключом кучи будет RMQ для этого диапазона (минимальное значение в строкеe, который мы можем найти в O (1)).

Например: если у нас есть это декартово дерево: Cartesian tree И мы хотим вставить узел со значением 3, которое мы вставляемв кучу вместо диапазона:

0,2

И если мы хотим вставить узел со значением 10, мы вставляем в кучу:

5,9

И если мы хотим вставить корень, мы вставляем в кучу:

0, 10

И так далее ...

Поскольку поиск значенияузла (минимум в диапазоне) принимает O (1), сложность этого алгоритма будет одинаковой (O (klogk)).

Псевдокод:

//assuming our static array is called: St

K_MinValuesInRange(k, left, right, SparseTable):
  arr  = Array[0 . . . k - 1]

  /*key of node in the heap is determined
    by St[SparseTable.RMQ(node.left, node.right)]
    which takes O(1) to calculate*/
  heap = emptyMinHeap()

  heap.insert(left, right)
  for(i = 0 . . . k - 1):
      node <- heap.pop()
      min_pos <- SparseTable.RMQ(node.left, node.right)
      arr[i]  <- St[min_pos]

      /* if node has left son: insert left son*/
      if node.left < min_pos: heap.insert(node.left, min_pos - 1)

      /* if node has right son: insert right son*/
      if node.right > min_pos: heap.insert(min_pos + 1, node.right)

  return arr
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...