Дерево отрезков: Построение, Запросы и Lazy Propagation

Дерево отрезков для быстрых запросов на отрезке (Range Minimum/Sum Query) за O(log N) и массовых обновлений с отложенными операциями (Lazy Propagation).

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Запросы на отрезках: предварительные знания, план уроков и практика →

Структура Дерева отрезков

Дерево отрезков хранит информацию о подотрезках массива. Память: $4N$ .

cpp

void updateLazy(int node, int start, int end, int l, int r, int val, vector<int>& tree, vector<int>& lazy) {
    if (lazy[node] != 0) {
        tree[node] += (end - start + 1) * lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if (start > end || start > r || end < l) return;
    if (start >= l && end <= r) {
        tree[node] += (end - start + 1) * val;
        if (start != end) {
            lazy[2 * node] += val;
            lazy[2 * node + 1] += val;
        }
        return;
    }
    int mid = (start + end) / 2;
    updateLazy(2 * node, start, mid, l, r, val, tree, lazy);
    updateLazy(2 * node + 1, mid + 1, end, l, r, val, tree, lazy);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Что дальше?

Закрепите материал задачей: Повторить число.

Изучено — к практике →

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».