Применение бинарного индексированного дерева

Я пытался решить эту алгоритмическую задачу и наткнулся на это прекрасное решение:

«Идея состоит в том, чтобы обрабатывать ai, bi и ci асимметрично. BIT поддерживает минимальные запросы для ключевых интервалов, начинающихся с 1. Мы используем ci в качестве значений и bi в качестве ключей. Они вставляются в порядке возрастания ai. Таким образом, для каждого a i, в свою очередь, структура данных позволяет запрашивать наименьшее значение cj (возможно, ∞) для bj в [1..b i) и aj ‹ ai. Имеем cj ‹ ci > тогда и только тогда, когда участник i не отличник».

источник

Теперь мне трудно понять это решение.

Вот что я понимаю об этом решении: я знаю, что двоичное индексированное дерево используется для ответов на такие запросы, как нахождение суммы интервалов в массиве, а также поддерживает обновления в элементах. Он выполняет обе операции с временной сложностью O (logn) каждая. Теперь это решение говорит о том, что мы строим BIT с ключами как ci и значением как bi, то есть в основном bi является дополнительным значением это идет с каждым узлом. Теперь мы вставляем элементы в дерево с возрастающими значениями ai, здесь я потерял хватку. Какая разница, в каком порядке мы вставляем узлы и что говорит оператор после этой части, я понятия не имею.

Пожалуйста, помогите мне понять, что говорит это решение.


person aroma    schedule 28.05.2017    source источник


Ответы (1)


Найдем всех неотличников. Другой участник j может быть лучше участника i только в том случае, если его a[j] < a[i]. Таким образом, мы можем игнорировать всех участников с большим значением a[j]. Вот почему мы сортируем их по a.

Это условие необходимо, но недостаточно. Нам также нужно проверить b и c. Как мы можем сделать это? Нам нужно знать, есть ли парень a[j] < a[i] (то есть тот, кто идет перед текущим в порядке сортировки) такой, что его b[j] < b[i] и c[j] < c[i]. Мы создаем BIT (с c[j] в качестве ключей и b[j] в качестве значений), чтобы проверить последние два условия. Понятно, что такое j существует тогда и только тогда, когда минимум на префиксе [0, c[i]) меньше b[i].

Подводя итог, идея такова: мы сортируем их по a[i], а затем игнорируем значения a. Таким образом, мы переходим от трехмерной к двумерной задаче, которую проще решить (вот почему порядок имеет значение. Парень с большим a[i] никогда не бывает лучше). Мы используем BIT для решения двумерной задачи.

person kraskevich    schedule 28.05.2017
comment
Хорошо, я понял, но это заставило меня задуматься, можно ли было бы сделать что-то подобное, если бы было 4 столбца? Я имею в виду, можно ли решить эту концепцию с помощью столбцов › 4 или эта проблема предназначена только для c = 3. - person aroma; 30.05.2017
comment
@ash Вы можете решить для двух столбцов с двухмерным деревом сегментов вместо BIT. В общем, можно решить k-D версию с k - 2-мерным деревом сегментов. Его явно становится сложнее реализовать, и он работает медленнее для более высоких измерений. На самом деле, очень вероятно, что вы начнете проигрывать наивному O(N^2) для больших k. Так что да, это остается хорошим только для 3-D. - person kraskevich; 30.05.2017