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

Question

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

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

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

Answer 1

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

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

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