Lazy Операции в дереве отрезков

Lazy операции в дереве отрезков представляют собой способ оптимизации вычислений, позволяющий избежать лишних рекурсивных вызовов и повысить эффективность операций обновления и запроса на отрезках.

Идея

Основная идея заключается в том, чтобы отложить вычисления до тех пор, пока они не потребуются. Вместо того, чтобы немедленно пересчитывать значения во всех узлах дерева при каждом обновлении или запросе, lazy операции хранят только те изменения, которые необходимы для вычисления конечного результата.

Пример реалиации

Пример реализации lazy операций в дереве отрезков для вычисления суммы на отрезках:

// Массив для хранения дерева отрезков
int tree[4*MAXN];
// Массив для хранения ленивых операций
int lazy[4*MAXN];

// Функция построения дерева
void build(int a[], int v, int tl, int tr) {
    lazy[v] = 0; // Инициализация ленивой операции
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        tree[v] = tree[v*2] + tree[v*2+1]; // Для суммы на отрезке
    }
}

// Функция ленивого обновления
void apply_lazy(int v, int tl, int tr) {
    if (lazy[v] != 0) {
        tree[v] += (tr - tl + 1) * lazy[v]; // Обновление значения в узле
        if (tl != tr) {
            lazy[v*2] += lazy[v]; // Применение ленивой операции к левому потомку
            lazy[v*2+1] += lazy[v]; // Применение ленивой операции к правому потомку
        }
        lazy[v] = 0; // Сброс ленивой операции
    }
}

// Функция запроса суммы на отрезке
int sum(int v, int tl, int tr, int l, int r) {
    apply_lazy(v, tl, tr); // Применение ленивой операции
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return tree[v];
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm)) + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

// Функция обновления элементов на отрезке
void update(int v, int tl, int tr, int l, int r, int val) {
    apply_lazy(v, tl, tr); // Применение ленивой операции
    if (l > r)
        return;
    if (l == tl && r == tr) {
        lazy[v] += val; // Обновление ленивой операции
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, val);
        tree[v] = tree[v*2] + tree[v*2+1]; // Обновление значения в узле
    }
}

Очевидно, что мы можем делать и другие lazy операции.

Задача

Даны прямоугольники с целыми координатами и точки с целыми координатами. Для каждой точки хотим понять, в скольких прямоугольниках она лежит.

Пусть у нас пока все координаты ограничены справа какой-то константой C. В каждой точке прямой нам интересно сколько она покрывает прямоугольников. С помошью сканлайна (сканирующей прямой) мы умеем такое делать. А теперь прикрутим ДО с массовыми(ленивыми) операциями!!! И все задача схлопнулась до C * n + m * log m, где m - количество точек.

При этом меня интересует только границы прямоугольника. Поэтому на самом деле я могу идти только по нужным мне прямым, оптимизируя мое время до n log n +n log n+ m * log m. Тадам!!!

Но если есть константа. Так что надо оптимизировать. Но для этого нам надо сжимать декартовы координаты.