RMQ с использованием двух деревьев Фенвика (двоичное индексированное дерево)

Question

Основываясь на этом документе, я обнаружил, что для выполнения RMQ достаточно использовать два BIT. O(lg N), поскольку его легче кодировать, чем сегментированное дерево, и в документе утверждается, что оно работает лучше, чем другие структуры данных.

Я понимаю, как построить дерево и как выполнить операцию запроса, но я запутался в операции обновления. Вот цитаты:

Сделаем следующее наблюдение: когда мы генерируем соответствующие интервалы узлов, мимо которых мы проходим, мы можем покрыть весь интервал [ p + 1, y ], начав с узла p + 1 и поднявшись по первому дереву (рис. 2.1). Таким образом, вместо того, чтобы выполнять запрос для каждого обновляемого узла, мы вычисляем результаты запросов на лету, поднимаясь по дереву один раз.

Аналогично, мы можем обновить все интервалы вида [x, p - 1], начав с узла p - 1 и взбираясь на второе дерево (рис. 2.2). Тот же алгоритм применяется для обновления обоих деревьев.

Я подозреваю, что все должно быть наоборот: для нахождения минимального интервала [ p + 1, y ] мы должны использовать второе дерево вместо первого; для нахождения минимума интервала [x, p-1] мы должны использовать первое дерево.

Мой вопрос: я прав? Если нет, может кто-нибудь привести простой пример, демонстрирующий, как работает операция обновления?

Answer 1

Объяснение немного двусмысленное. Я думаю, они имели в виду, что для [p+1,y] вы поднимаетесь на первые три, начиная с p+1, но используйте второе дерево для запроса.

Представим, что вы обновляете значение по 10-му индексу (из бумаги). Вам придется отвечать на вопросы для [x, 10 - 1] & [10 + 1, y] при обновлении деревьев. Для того, чтобы сделать это эффективно, вы строите два списка "лазания":

CLB1 взбираясь на первое дерево из p+1: {11, 12}, которые соответствуют следующим интервалам: [11..11], [12..15] второго дерева

CLB2 взбираясь на второе дерево из p-1: {9, 8}, которые соответствуют следующим интервалам: [9..9], [1..8] первого дерева

Теперь вы начинаете обновление первого дерева, взбираясь по первому дереву, начиная с 10.

10 - тривиальное обновление

12 - вам нужно сделать запрос [9..9], {10}, [11..11], {12}, У вас есть ответ на [9..9] от BIT1 взяв первого члена CLB2, И у вас есть ответ на [11..11] от BIT2, взяв первого члена CLB1, {10} а также {12} тривиальны.

16 - вам нужно запросить [1..9], {10}, [11..15] (нет {16} как это вымышлено). Вы принимаете [1..9] от BIT1 взяв первые два предмета CLB2, Вы принимаете [11..15] от BIT2 взяв первые два предмета CLB1, {10} тривиально.

Как видно из левых запросов, вы берете ответы из первого дерева, используя историю лазания из p-1 второго дерева. Для правильных запросов вы берете ответы из второго дерева, используя историю лазания p+1 первого дерева.

Подобный процесс используется для обновления правильного дерева.

Обновление: процесс для 9-го узла

В случае обновления 9-го индекса мы имеем следующий CLBs:

CLB1: {10, 12}интервалы: [10..11], [12..15] из BIT2,

CLB2: {8}интервалы: [1..8] из BIT1

обновление BIT1:

9 - тривиально

10 - тривиально (нам нужно только {9} а также {10})

12 - нам нужна первая запись из CLB1 - [10..11], а также {12} с {9}

16 - нам нужны две первые записи из CLB1 - [10..11] U [12..15], первая запись от CLB2 - [1..8] а также {9}

обновление BIT2:

9 - тривиально

8 - нам нужны первые две записи из CLB1 - [10..11] U [12..15] а также {9} с {8}

0 - нам нужны первые две записи из CLB1 - [10..11] U [12..15] и первая запись от CLB2 - [1..8] а также {9}