Түсіндіру

Segment Tree, яғни дерево отрезков — бұл структура данных. Ол массивтің бір отрезогы бойынша сұрақтарға тез жауап береді.

Егер жай циклмен санасақ, көп уақыт кетуі мүмкін. Ал Segment Tree арқылы запрос 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, онда бұл бір ғана элемент. Сол үшін sum = 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] отрезогындағы сумманы қайтарады.

Егер қазіргі отрезок толық запрос ішінде жатса, бірден tr[u].sum қайтарамыз.

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 [l, r] отрезогындағы барлық элементке x қосады.

Егер қазіргі вершина толық запрос ішінде болса, бірден 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)

query [l, r] отрезогындағы сумманы қайтарады.

Егер қазіргі отрезок толық запрос ішінде болса, tr[u].sum қайтарамыз. Әйтпесе төменге түспей тұрып pushdown жасаймыз.

Асимптотика