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

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

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

(Весь подход использует методологию, представленную в Алгоритм разреженной таблицы (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 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 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 from LCA to RMQ part that confuses me, more below.

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

The Cartesian Tree from the data

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

Ответы

Ответ 1

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

  • Чтобы уменьшить RMQ до LCA, вам нужно преобразовать массив в дерево, а затем выполнить тур Euler по этому дереву.
  • Чтобы совершить тур Euler, вам нужно сохранить дерево таким образом, чтобы каждый node указывал на его дочерние элементы.
  • Редукция, указанная в RMQ для LCA, имеет каждый node пункт родителя, а не его дочерних элементов.

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

  • Создать массив из n узлов. Каждый node имеет поле значений, левый дочерний элемент и правый дочерний элемент.
  • Сначала установите nth node, чтобы иметь нулевой левый дочерний элемент, нулевой правый дочерний элемент и значение n-го элемента из массива.
  • Итерации по массиву T (где T [n] является родительским индексом n) и выполните следующие действия:
    • Если T [n] = *, то n-я запись является корнем. Вы можете сохранить это для последующего использования.
    • В противном случае, если T [n] n, то вы знаете, что node n должен быть правильным дочерним элементом его родителя, который хранится в позиции T [n]. Поэтому установите для правильного ребенка T [n] th node значение nth node.
    • В противном случае, если T [n] > n, то вы знаете, что node n должен быть левым дочерним элементом его родителя, который хранится в позиции T [n]. Поэтому установите левый дочерний элемент T [n] th node равным nth node.

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

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

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