Создайте структуру данных для выполнения обратных и отчетов о запросах за многократное время

Question

Учитывая последовательность n чисел, { a ₁ , a ₂ , a ₃ ,…, a _n }. Создайте структуру данных таким образом, чтобы следующие операции могли выполняться во время полихрена.

1. Реверс ( i , j ):

   Переверните все элементы в диапазоне от i до j , как показано ниже:
   Исходная последовательность: <… <em>a _{i -1} , a _i , a _{i + 1} ,…, a _{j -1} , a _j , a _{j + 1} ,…>
   Последовательность после обмена: <… <em>a _{i -1} , a _j , a _{j -1} ,…, a _{i -1} , a _i , a _{j + 1} ,…>

2. Отчет ( i ):

   Сообщите i -й элемент в последовательности, т.е. a _i .

Здесь poly-logn означает некоторую мощность log n . например, log ( n ) · log ( n ) может быть приемлемым.

[ Примечание: спасибо профессору Басване за этот вопрос. ]

Answer 1

Я думал об использовании двоичного дерева с узлом, дополненным индикатором Left | Right и количеством элементов в этом поддереве.

• Еслииндикатор установлен на Left, затем начните с чтения левого потомка, затем прочитайте правый
• Else (установите на Right), затем начните с чтения правого потомка, затем прочитайте левый

Report довольно очевиден: O(log n)

Revert немного сложнее, и я не уверен, действительно ли это сработает.

Идея заключалась бы в том, чтобы «изолировать» последовательность элементов для обращения в определенном поддереве (минимально возможное).Это поддерево содержит диапазон [a..b], включая [i..j]

• Обратное минимальное поддерево, которое содержит эту последовательность (изменение индикатора)
• Применить операцию Revert к [a..i-1] и [j+1..b]

Не уверен, что это действительно работает, хотя: /

РЕДАКТИРОВАТЬ :

Предыдущее решение не работает:) Я не могу представить решение, которое не переставляет дерево, и они не соблюдают требования сложности.

Я оставлю это там на случай, если оно даст кому-то идею, и яудалите его потом, если я сам не найду решение.

Answer 2

Splay деревьев + ваши украшения амортизируются O (log n). Структурные проблемы, с которыми столкнулся Матье, связаны с тем фактом, что за время амортизации O (log n) мы можем изменить корень на любой узел, который нам нравится.

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