Найти количество элементов с весом к в диапазоне (с обновлениями и запросами)

Question

Я пытаюсь решить следующую проблему:

Учитывая массив элементов с целыми весами (произвольный порядок), мы можем иметь 2 возможных операции:

Запрос: выведите количество элементов, которые имеют вес k, в диапазоне от x до y.
Обновление: Изменение веса элемента на определенном индекса V

Пример:.

Учитывая массив: [1,2,3,2,5,6,7,3 ]

Если запрос для количества элементов с весом 2 от индекса 1 до 3, то ответ будет 2.

Если мы изменяем элемент с индексом 2, чтобы иметь вес 2, то повторите тот же запрос, ответ будет равен 3.

Это, конечно, проблема с деревом сегментов (с использованием точечных обновлений). Тем не менее, я столкнулся с проблемой здесь - каждый сегмент будет удерживать ответ только за 1 индекс. Следовательно, кажется, что я должен использовать векторы в моем дереве сегментов. Но это будет слишком сложно. Кроме того, я не уверен, как это сделать.

Может ли кто-нибудь посоветовать мне лучшее решение?

Answer 1

Вместо дерева сегмента, вы должны использовать дерево двоичного поиска (BST), как AVL, декартово дерево, разводиться и т.д.

1. Во-первых, хранить все индексы всех появились значения в отделенных BSTs. В вашем примере [1,2,3,2,5,6,7,3], должно быть шесть BSTs:

   BST 1: [0],
   BST 2: [1,3],
   БСТ 3: [2,7],
   БСТ 5: [4],
   БСТ 6: [5],
   БСТ 7: [6]

2. Для каждого запроса (х, у, к), подсчитайте количество элементов, попадающих в диапазон [x, y] в SBT k.

3. Для каждого веса обновления [х] = V, удалить х из BST веса [х] и добавьте й в BST против

Временной сложности: O (NlogN + mlogn) где п длина данных, а m - количество операций.

Сложная сложность: O (n)