Объяснение

Дерево отрезков — это структура данных, которая быстро отвечает на запросы по отрезку.

Без дерева отрезков нужно проходить весь отрезок, это может быть долго. Дерево отрезков делает запросы за O(log n).

Каждая вершина отвечает за свой отрезок.

Что храним в вершине?

struct Node {
    int l, r;
    long long sum;
};

• l — левая граница отрезка
• r — правая граница отрезка
• sum — сумма на этом отрезке

Задача 1: обычное дерево отрезков

Нужно поддерживать массив и делать два типа запросов.

Input

5 5
1 2 3 4 5
Q 1 5
Q 2 4
C 3 10
Q 1 5
Q 3 3

Output

15
9
22
10

Полная реализация обычного ДО

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

struct Node {
    int l, r;
    long long sum;
} tr[N * 4];

int a[N];

void pushup(int u) {
    tr[u].sum = tr[u * 2].sum + tr[u * 2 + 1].sum;
}

void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;

    if (l == r) {
        tr[u].sum = a[l];
        return;
    }

    int mid = (l + r) / 2;

    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);

    pushup(u);
}

void change(int u, int pos, int x) {
    if (tr[u].l == tr[u].r) {
        tr[u].sum = x;
        return;
    }

    int mid = (tr[u].l + tr[u].r) / 2;

    if (pos <= mid) {
        change(u * 2, pos, x);
    } else {
        change(u * 2 + 1, pos, x);
    }

    pushup(u);
}

long long query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u].sum;
    }

    int mid = (tr[u].l + tr[u].r) / 2;
    long long ans = 0;

    if (l <= mid) {
        ans += query(u * 2, l, r);
    }

    if (r > mid) {
        ans += query(u * 2 + 1, l, r);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (q--) {
        char op;
        cin >> op;

        if (op == 'Q') {
            int l, r;
            cin >> l >> r;

            cout << query(1, l, r) << '\n';
        } else if (op == 'C') {
            int pos, x;
            cin >> pos >> x;

            change(1, pos, x);
        }
    }

    return 0;
}

Объяснение функций обычного ДО

1. pushup

void pushup(int u) {
    tr[u].sum = tr[u * 2].sum + tr[u * 2 + 1].sum;
}

pushup пересчитывает сумму вершины через двух детей.

2. build

void build(int u, int l, int r)

build строит дерево отрезков. Вершина u отвечает за отрезок [l, r].

Если l == r, значит это один элемент массива. Тогда сумма равна a[l].

if (l == r) {
    tr[u].sum = a[l];
    return;
}

3. change

void change(int u, int pos, int x)

change меняет один элемент массива. Например, change(1, 3, 10) означает: поставить a[3] = 10.

Функция идет вниз до нужной позиции. Потом пересчитывает суммы обратно через pushup.

4. query

long long query(int u, int l, int r)

query возвращает сумму на отрезке [l, r].

Если текущий отрезок полностью лежит внутри запроса, мы сразу берем его сумму.

if (l <= tr[u].l && tr[u].r <= r) {
    return tr[u].sum;
}

Если запрос пересекает левую часть, идем в левого сына. Если пересекает правую часть, идем в правого сына.

Задача 2: ДО с обновлениями на отрезке

Теперь нужно уметь прибавлять число ко всему отрезку.

Input

5 5
1 2 3 4 5
Q 1 5
A 2 4 10
Q 1 5
Q 2 4
Q 3 3

Output

15
45
39
13

Полная реализация ДО с pushdown

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

struct Node {
    int l, r;
    long long sum;
    long long add;
} tr[N * 4];

int a[N];

void pushup(int u) {
    tr[u].sum = tr[u * 2].sum + tr[u * 2 + 1].sum;
}

void apply(int u, long long x) {
    int len = tr[u].r - tr[u].l + 1;

    tr[u].sum += x * len;
    tr[u].add += x;
}

void pushdown(int u) {
    if (tr[u].add == 0) {
        return;
    }

    apply(u * 2, tr[u].add);
    apply(u * 2 + 1, tr[u].add);

    tr[u].add = 0;
}

void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].add = 0;

    if (l == r) {
        tr[u].sum = a[l];
        return;
    }

    int mid = (l + r) / 2;

    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);

    pushup(u);
}

void modify(int u, int l, int r, long long x) {
    if (l <= tr[u].l && tr[u].r <= r) {
        apply(u, x);
        return;
    }

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) / 2;

    if (l <= mid) {
        modify(u * 2, l, r, x);
    }

    if (r > mid) {
        modify(u * 2 + 1, l, r, x);
    }

    pushup(u);
}

long long query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u].sum;
    }

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) / 2;
    long long ans = 0;

    if (l <= mid) {
        ans += query(u * 2, l, r);
    }

    if (r > mid) {
        ans += query(u * 2 + 1, l, r);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (q--) {
        char op;
        cin >> op;

        if (op == 'A') {
            int l, r;
            long long x;

            cin >> l >> r >> x;

            modify(1, l, r, x);
        } else if (op == 'Q') {
            int l, r;
            cin >> l >> r;

            cout << query(1, l, r) << '\n';
        }
    }

    return 0;
}

Объяснение функций с pushdown

1. pushup

void pushup(int u) {
    tr[u].sum = tr[u * 2].sum + tr[u * 2 + 1].sum;
}

Работает так же, как в обычном дереве отрезков. Берем сумму левого и правого сына.

2. apply

void apply(int u, long long x) {
    int len = tr[u].r - tr[u].l + 1;

    tr[u].sum += x * len;
    tr[u].add += x;
}

apply применяет прибавление ко всей вершине.

add запоминает, что это прибавление потом нужно передать детям.

3. pushdown

void pushdown(int u) {
    if (tr[u].add == 0) {
        return;
    }

    apply(u * 2, tr[u].add);
    apply(u * 2 + 1, tr[u].add);

    tr[u].add = 0;
}

pushdown передает отложенное прибавление детям.

Это нужно перед тем, как идти вниз в детей.

4. build

void build(int u, int l, int r)

Строит дерево. В этой версии еще нужно поставить add = 0, потому что сначала нет отложенных обновлений.

5. modify

void modify(int u, int l, int r, long long x)

modify прибавляет x ко всем элементам на отрезке [l, r].

Если текущая вершина полностью лежит внутри запроса, мы просто вызываем apply.

if (l <= tr[u].l && tr[u].r <= r) {
    apply(u, x);
    return;
}

Если нужно идти глубже, сначала вызываем pushdown, чтобы дети получили старые отложенные обновления.

6. query

long long query(int u, int l, int r)

Возвращает сумму на отрезке [l, r].

Если текущий отрезок полностью внутри запроса, возвращаем tr[u].sum. Иначе перед спуском вызываем pushdown.

Асимптотика