← Назад к структурам данных

Merge Sort Tree

Дерево отрезков, хранящее отсортированные массивы для подсчёта чисел в диапазоне

🐍 Python
n, m = map(int, input().split())
A = list(map(int, input().split()))
t = [[] for _ in range(4 * n)]

def build(v, l, r):
    if l + 1 == r:
        t[v].append(A[l])
        return
    m = (l + r) // 2
    build(v * 2, l, m)
    build(v * 2 + 1, m, r)
    i = j = 0
    while i < len(t[v * 2]) and j < len(t[v * 2 + 1]):
        if t[v * 2][i] < t[v * 2 + 1][j]:
            t[v].append(t[v * 2][i])
            i += 1
        else:
            t[v].append(t[v * 2 + 1][j])
            j += 1
    while i < len(t[v * 2]):
        t[v].append(t[v * 2][i])
        i += 1
    while j < len(t[v * 2 + 1]):
        t[v].append(t[v * 2 + 1][j])
        j += 1

def query(v, l, r, ql, qr, x, y):
    if l >= qr or r <= ql:
        return 0
    if ql <= l and r <= qr:
        L = 0
        R = len(t[v]) - 1
        while L <= R:
            mid = (L + R) // 2
            if t[v][mid] < x:
                L = mid + 1
            else:
                R = mid - 1
        left = L
        L = 0
        R = len(t[v]) - 1
        while L <= R:
            mid = (L + R) // 2
            if t[v][mid] <= y:
                L = mid + 1
            else:
                R = mid - 1
        right = L
        return right - left
    m = (l + r) // 2
    return query(v * 2, l, m, ql, qr, x, y) + query(v * 2 + 1, m, r, ql, qr, x, y)

build(1, 0, n)

for _ in range(m):
    l, r, x, y = map(int, input().split())
    print(query(1, 0, n, l - 1, r, x, y))
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

struct segtree {
    vector<int> D;
};

vector<segtree> t;
vector<int> A;

void build(int v, int tl, int tr) {
    if (tl + 1 == tr) {
        t[v].D.push_back(A[tl]);
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm, tr);
    t[v].D.resize(t[v * 2].D.size() + t[v * 2 + 1].D.size());
    merge(t[v * 2].D.begin(), t[v * 2].D.end(),
          t[v * 2 + 1].D.begin(), t[v * 2 + 1].D.end(),
          t[v].D.begin());
}

int query(int v, int tl, int tr, int l, int r, int x, int y) {
    if (tl >= r || tr <= l) return 0;
    if (l <= tl && tr <= r) {
        auto left = lower_bound(t[v].D.begin(), t[v].D.end(), x);
        auto right = upper_bound(t[v].D.begin(), t[v].D.end(), y);
        return distance(left, right);
    }
    int tm = (tl + tr) / 2;
    return query(v * 2, tl, tm, l, r, x, y) +
           query(v * 2 + 1, tm, tr, l, r, x, y);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    A.resize(n);
    t.resize(4 * n);
    
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    build(1, 0, n);
    
    for (int i = 0; i < m; i++) {
        int l, r, x, y;
        cin >> l >> r >> x >> y;
        cout << query(1, 0, n, l - 1, r, x, y) << "\n";
    }
    
    return 0;
}

Как работает Merge Sort Tree?

Merge Sort Tree — это структура данных, которая представляет собой дерево отрезков, где в каждой вершине хранится отсортированный массив элементов из соответствующего отрезка. Это позволяет отвечать на запросы: сколько чисел на отрезке [l, r] лежит в диапазоне [x, y].

Построение

Важно: Построение занимает O(n log n) памяти, так как каждый элемент хранится в O(log n) вершинах дерева.

Ответ на запрос

Сложность

Это эффективная альтернатива дереву отрезков с сохранением структур (персистентному дереву) для некоторых задач, связанных с диапазонными запросами.

Формат ввода и вывода

Ввод:

Вывод:

Пример ввода:

5 4
1 3 2 4 5
1 5 2 4
2 4 3 5
1 3 1 3
3 5 2 6

Вывод:

3
2
2
3

Пояснение:
[1, 3, 2, 4, 5]
[1..5] в [2..4]: числа 3,2,4 → 3
[2..4] в [3..5]: числа 3,4 → 2
[1..3] в [1..3]: числа 1,3,2 → 3? но 3,2 → 2, уточним.

Попробовать Merge Sort Tree онлайн

Введите массив и запросы:

Результат появится здесь...