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

Дерево отрезков (ленивое обновление)

Массовое присваивание на отрезке и запрос суммы за O(log n)

🐍 Python (реализация)
n, m = map(int, input().split())
t = [0] * (n * 4 + 1)
p = [-1] * (n * 4 + 1)

def apply(v, z, l, r):
    t[v] = z * (r - l)
    p[v] = z

def push(v, l, r):
    if p[v] != -1:
        m = (l + r) // 2
        apply(v * 2 + 1, p[v], l, m)
        apply(v * 2 + 2, p[v], m, r)
        p[v] = -1

def update(v, l, r, ql, qr, z):
    if r <= ql or l >= qr:
        return
    if l >= ql and r <= qr:
        apply(v, z, l, r)
        return
    m = (l + r) // 2
    push(v, l, r)
    update(v * 2 + 1, l, m, ql, qr, z)
    update(v * 2 + 2, m, r, ql, qr, z)
    t[v] = t[v * 2 + 1] + t[v * 2 + 2]

def get(v, l, r, ql, qr):
    if r <= ql or l >= qr:
        return 0
    if l >= ql and r <= qr:
        return t[v]
    m = (l + r) // 2
    push(v, l, r)
    return get(v * 2 + 1, l, m, ql, qr) + get(v * 2 + 2, m, r, ql, qr)

for _ in range(m):
    L = input().split()
    if L[0] == "Q":
        l, r = int(L[1]), int(L[2])
        print(get(0, 0, n, l - 1, r))
    else:
        l, r, a = int(L[1]), int(L[2]), int(L[3])
        update(0, 0, n, l - 1, r, a)
⚙️ C++ (реализация)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> t, p;
int n;

void apply(int v, ll z, int l, int r) {
    t[v] = z * (r - l);
    p[v] = z;
}

void push(int v, int l, int r) {
    if (p[v] != -1) {
        int m = (l + r) / 2;
        apply(v * 2 + 1, p[v], l, m);
        apply(v * 2 + 2, p[v], m, r);
        p[v] = -1;
    }
}

void update(int v, int l, int r, int ql, int qr, ll z) {
    if (r <= ql || l >= qr) return;
    if (l >= ql && r <= qr) {
        apply(v, z, l, r);
        return;
    }
    int m = (l + r) / 2;
    push(v, l, r);
    update(v * 2 + 1, l, m, ql, qr, z);
    update(v * 2 + 2, m, r, ql, qr, z);
    t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

ll get(int v, int l, int r, int ql, int qr) {
    if (r <= ql || l >= qr) return 0;
    if (l >= ql && r <= qr) return t[v];
    int m = (l + r) / 2;
    push(v, l, r);
    return get(v * 2 + 1, l, m, ql, qr) + get(v * 2 + 2, m, r, ql, qr);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int m;
    cin >> n >> m;
    
    t.assign(n * 4 + 1, 0);
    p.assign(n * 4 + 1, -1);
    
    for (int i = 0; i < m; i++) {
        char type;
        cin >> type;
        if (type == 'Q') {
            int l, r;
            cin >> l >> r;
            cout << get(0, 0, n, l - 1, r) << "\n";
        } else {
            int l, r, a;
            cin >> l >> r >> a;
            update(0, 0, n, l - 1, r, a);
        }
    }
    
    return 0;
}

Как работает дерево отрезков с ленивым обновлением?

Ленивое обновление — это техника, которая позволяет выполнять массовые операции на отрезке за O(log n) вместо O(n). Вместо того чтобы обновлять каждый элемент, мы помечаем вершину дерева как "ленивую" и применяем изменение только при необходимости.

Основные функции

  • apply(v, z, l, r): присваивает значение z всему отрезку [l, r) вершины v. Обновляет t[v] = z × длина_отрезка и помечает вершину как ленивую.
  • push(v, l, r): проталкивает ленивую метку из вершины v в её детей. Если вершина помечена, значение передаётся детям, а метка сбрасывается.
  • update(v, l, r, ql, qr, z): присваивает значение z всем элементам на отрезке [ql, qr). Рекурсивно спускается по дереву, применяя ленивые метки при необходимости.
  • get(v, l, r, ql, qr): возвращает сумму элементов на отрезке [ql, qr).

Важные особенности

Временная сложность: O((n + m) log n) — каждый запрос и обновление выполняются за O(log n).

Пространственная сложность: O(n) для хранения дерева.

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

Ввод:

Вывод:

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

10 6
u 1 5 3
Q 1 5
u 3 7 7
Q 1 10
u 1 10 0
Q 1 10

Вывод:

15
43
0

Пояснение:
Изначально массив из 10 нулей.
1) присвоили [1..5] = 3 → сумма[1..5] = 15
2) присвоили [3..7] = 7 → массив: [3,3,7,7,7,7,7,0,0,0], сумма[1..10] = 43
3) присвоили [1..10] = 0 → все нули, сумма = 0

Попробовать ленивое дерево отрезков онлайн

Введите запросы (u l r a — обновление, Q l r — сумма):

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