Merge sort tree: как считать «сколько чисел <= x на отрезке» и какая сложность?
Запросы вида «сколько элементов на [l, r] не превосходят x» без обновлений. Слышал про merge sort tree (дерево отрезков, где в узле лежит отсортированный подмассив). Как оно устроено, как отвечает на запрос и какая итоговая асимптотика?
2 ответа
Merge sort tree — дерево отрезков, где в каждом узле хранится отсортированный массив элементов его подотрезка. Узел на [tl, tr] = слияние отсортированных массивов детей (как в merge sort, отсюда название).
Построение: лист — массив из одного элемента; внутренний узел — merge детей. Суммарно по уровням O(n) элементов на уровень × log n уровней = O(n log n) памяти и времени на построение.
Запрос «сколько <= x на [l, r]»: разбиваем [l, r] на O(log n) канонических узлов дерева отрезков, в каждом делаем upper_bound(x) по отсортированному массиву узла за O(log n). Итого O(log^2 n) на запрос.
vector<int> t[4*N];
void build(int v, int tl, int tr) {
if (tl == tr) { t[v] = {a[tl]}; return; }
int tm = (tl + tr) / 2;
build(2*v, tl, tm); build(2*v+1, tm+1, tr);
merge(t[2*v].begin(), t[2*v].end(),
t[2*v+1].begin(), t[2*v+1].end(),
back_inserter(t[v]));
}
int query(int v, int tl, int tr, int l, int r, int x) {
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r)
return upper_bound(t[v].begin(), t[v].end(), x) - t[v].begin();
int tm = (tl + tr) / 2;
return query(2*v, tl, tm, l, r, x) + query(2*v+1, tm+1, tr, l, r, x);
}
Подходит для статичных данных. С обновлениями — уже нужен либо persistent, либо MO, либо BIT of sorted sets.
Когда что выбрать для «количество <= x на отрезке»:
- Merge sort tree — просто пишется, O(n log n) память, O(log^2 n) запрос. Хорош, когда n до ~10^5–2·10^5.
- Persistent segment tree — O(log n) запрос, та же память, но сложнее код. Если запросов очень много и log^2 не лезет по времени — берите его.
- Оффлайн + BIT (если порядок запросов можно менять) — сортируем запросы по x, добавляем элементы по возрастанию, отвечаем Фенвиком за O(log n). Часто самое быстрое и экономное по памяти.
Граabля merge sort tree — память: vector<int> в 4N узлах с накладными расходами вектора может неожиданно дать MLE. Если значения помещаются в int и n большое, иногда выгоднее хранить плоский массив с указателями на сегменты, а не vector в каждом узле.