Есть ли способ найти частоту числа в данном диапазоне, используя дерево сегментов?

Question

Предположим, у меня есть массив [1, 2, 3, 5, 5, 6, 5, 5]

Теперь может быть два вида операций. Одной из них является операция "обновления", то есть увеличение значения в индексе 4[индексирование на основе 1] на X. Другая операция - операция "запрос", где задан диапазон, предположим [4, 8](оба включительно) и Значение предположим 5. Теперь найдите частоту значения 5 в заданном диапазоне [4, 8]. В этом случае ответ должен быть 4.

Как я могу сделать этот шаг "запрос", используя дерево сегментов??

Заранее спасибо.

Answer 1

У меня есть два решения, но без использования дерева сегментов

Первое решение:

• Разделить каждый запрос на freq(r,x)-freq(l-1,x)

• Перебирайте ввод и сохраняйте счет в массиве (или, если
  ассортимент большой)

• Если на вашей позиции есть запрос, добавьте / вычтите счет из массива. Это должно работать в O(n + q), если элементы достаточно малы
  для массива или O(n + q log n), если вам нужно использовать карту.

Второе решение: использовать алгоритм Мо для решения этой проблемы со сложностью времени O((N + Q) * sqrt(N) * F).