Представим дерево, которое получается при рекурсивном запуске сортировки слиянием.
Если нарисовать, то получится структура напоминающая ДО, что позволяет автору считать данную структуру подвидом дерева отрезков.
Размер дерева будет равен \(O(n \log{n})\), так как на каждом уровне ровно \(n\) элементов, а всего логарифм уровней дерева. Строится оно за такое же асимптотику (сортировка слиянием так и работает).
Пусть дан массив \(a\) длины \(n\) и даны запросы вида: сколько чисел на отрезке \([l;r]\), которые меньше \(x\)?
Чтобы решить задачу давайте построим MergeSort Tree (далее ДО или просто дерево) на массиве \(a\).
Когда приходит запрос найдем все вершины, которые покрывают отрезок, как в обычном ДО. Теперь для каждой вершины найдем ответ и сложим его.
Ответ для конкретной вершины легко найти бинпоиском, т.к. подотрезок отсортирован. Асимптотика \(O(n \log{n})\)
Простые модификации: запросы на изменение в точке. Если массив изменяется, придется поддерживать структуру вроде pbds_tree, чтобы уметь обновлять её и находить количество элементов меньше данного.
На самом деле в вершине можно хранить все что угодно. Главное уметь обрабатывать вершину за небольшое время.
Решим и такую задачу: так же дан массив \(a\) длиной \(n\). Необходимо уметь отвечать на запросы количества различных чисел на отрезке.
Давайте построим массив \(next\), где \(next[i]\) будет хранить наиближайшее \(j\) справа, такое что \(a_i = a_j\). Если подобного \(j\) не существует, запишем что-нибудь вроде \(n+1\).
Теперь для каждого запроса посчитаем количество чисел на отрезке которые встречаются последний раз. Это все индексы, где \(next[i] > r\). А подобное мы уже умеем решать с помощью бинпоиска и нашего ДО.