Сегментное дерево: количество чисел меньше x

Question

Я пытаюсь решить эту проблему.

Я нашел учебник по этой проблеме, но я не понимаю, как построить дерево сегментов, которое будет находить количество чисел меньше x в O(log n) (x может измениться). В учебнике это было опущено.

Может кто-нибудь объяснить мне, как это сделать?

Answer 1

Это довольно просто:

1. Хранить отсортированный массив всех чисел в диапазоне, охватываемом конкретным узлом
   (O(n * log n) память и время для инициализации).

2. Чтобы ответить на запрос, разложите сегмент запроса на O(log n) узлы (так же, как это делается для стандартного дерева сегментов мин / макс / сумма) и запускают бинарный поиск по массиву, хранящемуся в каждом из этих узлов, чтобы найти число элементов меньше x, Это дает O(log^2 n) время на запрос. Вы также можете достичь O(log n) с использованием дробного каскадирования, но это не обязательно.