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

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, Treap, Splay и т. Д.

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

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

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

3. Для каждого веса обновления [x] = v удалите x из веса BST [x] и добавьте x к BST v

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

Пространство сложность: O(n)