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

Question

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

"Идея состоит в том, чтобы обрабатывать a_i, b_i и c_i асимметрично. BIT поддерживает минимальные запросы для ключевых интервалов, начинающихся с 1. Мы используем c_{i в} качестве значений и b_{i в} качестве ключей. Они вставляются в порядке увеличения_i. Таким образом, для каждого a_i в свою очередь, структура данных позволяет запрашивать наименьшее значение c_j (возможно, ∞) для b_j в [1..b_i) и a_j i. У нас есть c_j i, если и только если участник i не превосходен."

источник

Сейчас мне трудно понять это решение.

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

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

Answer 1

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

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

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