Диапазон Минимальный запрос ‹O(n), O(1)›подход (от дерева к ограниченному RMQ)

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

В разделе, где он представил подход, что я могу понять до сих пор, так это:

(Фактически весь подход использует методологию, представленную в Sparse Table ( ST) Алгоритм, Переход с LCA на RMQ и от RMQ до LCA)

Учитывая массив A[N], нам нужно преобразовать его в декартово дерево, таким образом сделав проблему RMQ проблемой LCA (наименьший общий предок). Позже мы можем получить упрощенную версию массива A и сделать ее ограниченной задачей RMQ.

Так что это в основном два преобразования. Таким образом, первая часть RMQ для LCA проста. Используя стек, мы можем выполнить преобразование за время O(n), в результате чего получится массив T[N], где T[i] — родительский элемент i. И дерево готово.

Но вот чего я не могу понять. Для подхода O(n) требуется массив, где |A[i] - A[i-1]| = 1, и этот массив представлен в Сокращение от LCA до RMQ раздела руководства. Это включает Эйлеровский тур по этому дереву. Но как этого добиться с моим конечным результатом преобразования? Мой подход к этому не является линейным, поэтому в этом подходе его следует считать плохим, каким будет для этого линейный подход?

ОБНОВЛЕНИЕ: момент, который меня смущает

Here's the array A[]:

  n : 0  1  2  3  4  5  6  7  8  9
A[n]: 2  4  3  1  6  7  8  9  1  7

Here's the array T[]:

  n : 0  1  2  3  4  5  6  7  8  9
T[n]: 3  2  0  *  8  4  5  6  3  8  // * denotes -1, which is the root of the tree

//Above is from RMQ to LCA, it's from LCA to RMQ part that confuses me, more below.

Изображение дерева:

Декартово дерево по данным

Euler Tour должен знать дочерний элемент каждого узла, точно так же, как DFS (поиск в глубину), в то время как T [n] имеет только корень каждого элемента, а не дочерний элемент.


algorithm tree least-common-ancestor rmq cartesian-tree
person Shane Hsu    schedule 08.02.2013    source источник
comment
Я не уверен, что понимаю, что вы имеете в виду под тем, как этого можно достичь с моим конечным результатом преобразования. Можно уточнить, что конкретно вас смущает?   -  person templatetypedef    schedule 08.02.2013
comment
@templatetypedef Хорошо, я добавлю это к вопросу.   -  person Shane Hsu    schedule 08.02.2013
comment
Добавлен @templatetypedef.   -  person Shane Hsu    schedule 08.02.2013
comment
Откуда вы взяли этот массив T? Я не вижу, чтобы это было описано нигде в учебнике, поэтому я не уверен, как помочь.   -  person templatetypedef    schedule 08.02.2013
comment
@templatetypedef От RMQ до LCA. В этом разделе есть код.   -  person Shane Hsu    schedule 08.02.2013
comment
Думаю, меня смущают ваши обозначения. У вас есть два массива параллельно для каждого массива. Что означают верхние и нижние числа?   -  person templatetypedef    schedule 08.02.2013
comment
@templatetypedef сверху — это позиция элемента, снизу — сам элемент. Думаю, так понятнее, но я ошибаюсь. Удалим. На самом деле после того, как я отредактировал его, я обнаружил, что копирование и вставка фактически изменили то, что я скопировал. Странный. Во всяком случае, это исправлено.   -  person Shane Hsu    schedule 08.02.2013
comment
@RBarryYoung Да, это была ошибка, и она исправлена.   -  person Shane Hsu    schedule 08.02.2013

Ответы (1)


arrow_upward
9
arrow_downward

Вот мое текущее понимание того, что вас смущает:

  1. Чтобы уменьшить RMQ до LCA, вам нужно преобразовать массив в дерево, а затем выполнить обход Эйлера по этому дереву.
  2. Чтобы выполнить Эйлеров тур, вам нужно сохранить дерево так, чтобы каждый узел указывал на своих дочерних элементов.
  3. Сокращение, указанное в списке от RMQ до LCA, имеет каждый узел, указывающий на своего родителя, а не на своих дочерних элементов.

Если это так, ваши опасения полностью оправданы, но есть простой способ это исправить. В частности, когда у вас есть массив всех родительских указателей, вы можете преобразовать его в дерево, где каждый узел указывает на своих дочерних элементов за время O(n). Идея заключается в следующем:

  • Создайте массив из n узлов. Каждый узел имеет поле значения, левый дочерний элемент и правый дочерний элемент.
  • Первоначально установите n-й узел, чтобы иметь нулевой левый дочерний элемент, нулевой правый дочерний элемент и значение n-го элемента из массива.
  • Iterate across the T array (where T[n] is the parent index of n) and do the following:
    • If T[n] = *, then the nth entry is the root. You can store this for later use.
    • В противном случае, если T[n] ‹ n, то вы знаете, что узел n должен быть правым потомком своего родителя, который хранится в позиции T[n]. Поэтому установите правым дочерним элементом T [n]-го узла n-й узел.
    • В противном случае, если T[n] > n, то вы знаете, что узел n должен быть левым дочерним элементом своего родителя, который хранится в позиции T[n]. Поэтому установите левый дочерний элемент T [n]-го узла как n-й узел.

Это выполняется за время O(n), так как каждый узел обрабатывается ровно один раз.

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

Надеюсь это поможет!

person templatetypedef    schedule 08.02.2013
comment
Спасибо! Помогло, очень! Спасибо, что уделили столько времени комментариям и ответам! - person Shane Hsu; 08.02.2013