Деревья отрезков и запросы на диапазонах на с++. н...

Ниже — краткий, но полный русскоязычный конспект по деревьям отрезков (segment trees) и диапазонным запросам в C++.

---

1. Идея и когда применять

Дерево отрезков хранит на каждом узле агрегированное значение (сумма, минимум, МНОЖЕСТВО, XOR и т. д.) для некоторого подотрезка массива.

• Построение: O(n)
• Запрос/обновление: O(log n)
• Подходит, когда нужна сменяемая операция моноид-типа (ассоциативная, есть нейтральный элемент).

---

2. Логическая структура

text
[0, n)                    — корень
/        \
[0, m)       [m, n)       — дети

• Лист = один элемент.
• Каждый узел хранит value = f(left.value, right.value).

---

3. Реализация: рекурсивная версия

cpp
struct SegTree {
    int n;
    vector<long long> t;          // дерево
    SegTree(const vector<long long>& a) {
        n = a.size();
        t.resize(4 * n);
        build(1, 0, n - 1, a);
    }
    void build(int v, int l, int r, const vector<long long>& a) {
        if (l == r) { t[v] = a[l]; return; }
        int m = (l + r) / 2;
        build(v*2, l, m, a);
        build(v*2+1, m+1, r, a);
        t[v] = t[v*2] + t[v*2+1]; // операция суммы
    }
    // точечное обновление: a[pos] = val
    void update(int v, int l, int r, int pos, long long val) {
        if (l == r) { t[v] = val; return; }
        int m = (l + r) / 2;
        if (pos <= m) update(v*2, l, m, pos, val);
        else          update(v*2+1, m+1, r, pos, val);
        t[v] = t[v*2] + t[v*2+1];
    }
    // запрос суммы на [ql, qr]
    long long query(int v, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;          // вне отрезка
        if (ql <= l && r <= qr) return t[v];     // целиком внутри
        int m = (l + r) / 2;
        return query(v*2, l, m, ql, qr) +
               query(v*2+1, m+1, r, ql, qr);
    }
};

Использование

cpp
vector<long long> a = {5, 3, 7, 9, 6};
SegTree st(a);
cout << st.query(1,0,4,1,3) << "\n"; // сумма [1,3] = 3+7+9 = 19
st.update(1,0,4,2,4);                // a[2]=4
cout << st.query(1,0,4,0,4) << "\n"; // 5+3+4+9+6 = 27

---

4. Итеративная (bottom-up) реализация

Проще в коде и быстрее на практике, особенно при частых запросах:

cpp
struct SegTreeIter {
    int n;
    vector<long long> t;
    SegTreeIter(const vector<long long>& a) {
        int sz = a.size();
        n = 1; while (n < sz) n <<= 1;      // степень двойки
        t.assign(2*n, 0);
        copy(a.begin(), a.end(), t.begin()+n);
        for (int v = n-1; v > 0; --v)
            t[v] = t[v<<1] + t[v<<1|1];
    }
    void point_set(int pos, long long val) {
        for (t[pos += n] = val; pos >>= 1;)
            t[pos] = t[pos<<1] + t[pos<<1|1];
    }
    long long range_sum(int l, int r) {      // включительно-исключительно [l,r)
        long long res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += t[l++];
            if (r & 1) res += t[--r];
        }
        return res;
    }
};

• Вопрос «включительно-исключительно» ([l, r)) – главное не путать.

---

5. Ленивая пропагация (lazy propagation)

Нужна, когда обновляется целый диапазон за O(log n) (например, прибавить x на отрезке) и после этого всё равно поддерживать O(log n) на запросы.

Ключевые идеи:

1. В каждом узле храните не только агрегат, но и отложенное (lazy) значение.
2. При входе в узел сначала «распушить» lazy — передать детям и обновить агрегаты.
3. Обновление или запрос на подотрезке обходят только O(log n) узлов.

Мини-шаблон (сумма + добавление на отрезке):

cpp
struct Node { long long sum = 0, add = 0; };

void push(int v, int l, int r) {
    if (st[v].add == 0 || l == r) return;
    int m = (l + r) / 2, lc = v<<1, rc = v<<1|1;
    long long add = st[v].add;
    st[lc].add += add;  st[lc].sum += add * (m - l + 1);
    st[rc].add += add;  st[rc].sum += add * (r - m);
    st[v].add = 0;
}

Полный код занимает ~80 строк; смысл — забыть про повторение обхода всех элементов.

---

6. Типичные задачи

Задача	Операция	Lazy нужен?
Сумма/минимум/максимум на отрезке, точечное присваивание	+ / min / max	Нет
«Сумма на отрезке, прибавить x к диапазону»	+	Да
«К-я статистика на отрезке» (order statistics)	Сложнее (дерево отрезков Фенвика + ranking)	Иногда
«Найти первый/последний префикс с суммой ≥ k»	Двоичный поиск по дереву	Нет

---

7. Полезные советы

1. Размер массива: выделяйте 4*n (рекурс) или 2*n (итератив).
2. Нейтральный элемент: сумма → 0, минимум → +∞, максимум → -∞.
3. Типы данных: для больших сумм – long long.
4. 0- vs 1-based: определитесь сразу и следуйте везде.
5. Тесты: проверьте всегда нулевой/крайний отрезок, полный отрезок, точечный запрос.

---

Мини-пример для тренировки

text
Вход: 
5            // n
5 3 7 9 6    // a
3            // q
sum 1 3
set 2 4
sum 0 4
Выход:
19
27

Первый запрос – сумма на [1,3].
Второй – присвоить a[2]=4.
Третий – сумма всего массива.

---

8. Где почитать/потренироваться

• E-maxx.ru – классическая статья «Сегментное дерево».
• Codeforces EDU (раздел Data Structures) – глубокий курс с задачами.
• Книга «Competitive Programming 4» – главы 2.3.2–2.3.3.

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

Ниже — два полностью работающих примера C++ (стандарт C++17).

1. Базовый: точечное присваивание + сумма на отрезке.
2. Lazy-вариант: прибавление к целому диапазону + сумма на отрезке (ленивая пропагация).

Вы можете скопировать любой файл целиком, скомпилировать

bash
g++ -std=c++17 -O2 segtree.cpp -o segtree

и протестировать на входе вида

text
5
5 3 7 9 6
4
sum 1 3
set 2 4
add 0 4 1
sum 0 4

---

1. Базовый сегмент-дерево (точечное = set, запрос sum)

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

struct SegTree {
    int n;
    vector<long long> t;

    SegTree(const vector<long long>& a) {
        n = a.size();
        t.resize(2 * n);
        // листья
        copy(a.begin(), a.end(), t.begin() + n);
        // построение снизу-вверх
        for (int v = n - 1; v > 0; --v)
            t[v] = t[v << 1] + t[v << 1 | 1];
    }

    // присвоить a[pos] = val
    void point_set(int pos, long long val) {
        for (t[pos += n] = val; pos >>= 1;)
            t[pos] = t[pos << 1] + t[pos << 1 | 1];
    }

    // сумма на [l, r] (включительно)
    long long range_sum(int l, int r) const {
        long long res = 0;
        for (l += n, ++r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += t[l++];
            if (r & 1) res += t[--r];
        }
        return res;
    }
};

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

    int n;                    // размер массива
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (long long &x : a) cin >> x;
    SegTree st(a);

    int q;                    // число запросов
    cin >> q;
    while (q--) {
        string op;
        cin >> op;
        if (op == "sum") {
            int l, r;
            cin >> l >> r;
            cout << st.range_sum(l, r) << '\n';
        } else if (op == "set") {
            int pos; long long val;
            cin >> pos >> val;
            st.point_set(pos, val);
        }
    }
    return 0;
}

---

2. Сегмент-дерево с ленивой пропагацией

(операции: add l r x — прибавить x к каждому элементу диапазона; sum l r — сумма)

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

struct SegTree {
    struct Node {
        long long sum = 0;   // агрегат (сумма)
        long long add = 0;   // ленивое приращение
    };

    int n;
    vector<Node> st;

    SegTree(const vector<long long>& a) {
        int sz = a.size();
        n = 1; while (n < sz) n <<= 1;
        st.resize(2 * n);
        // заполняем листья
        for (int i = 0; i < sz; ++i)
            st[n + i].sum = a[i];
        for (int v = n - 1; v > 0; --v)
            pull(v);
    }

    /*---------- служебные функции ----------*/
    void apply(int v, int len, long long add) {
        st[v].sum += add * len;
        st[v].add += add;
    }

    void push(int v, int len) {       // проталкиваем к детям
        if (st[v].add == 0) return;
        int lc = v << 1, rc = v << 1 | 1;
        int half = len >> 1;
        apply(lc, half, st[v].add);
        apply(rc, half, st[v].add);
        st[v].add = 0;
    }

    void pull(int v) {                // пересчитываем из детей
        st[v].sum = st[v << 1].sum + st[v << 1 | 1].sum;
    }

    /*---------- публичные методы ----------*/
    // прибавить x к диапазону [l, r]
    void range_add(int l, int r, long long x) { range_add(1, 0, n - 1, l, r, x); }
    // сумма на диапазоне [l, r]
    long long range_sum(int l, int r) { return range_sum(1, 0, n - 1, l, r); }

private:
    void range_add(int v, int tl, int tr, int l, int r, long long x) {
        if (l > r) return;
        if (l == tl && r == tr) {
            apply(v, tr - tl + 1, x);
            return;
        }
        push(v, tr - tl + 1);
        int tm = (tl + tr) >> 1;
        range_add(v << 1, tl, tm, l, min(r, tm), x);
        range_add(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, x);
        pull(v);
    }

    long long range_sum(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (l == tl && r == tr) return st[v].sum;
        push(v, tr - tl + 1);
        int tm = (tl + tr) >> 1;
        return range_sum(v << 1, tl, tm, l, min(r, tm)) +
               range_sum(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r);
    }
};

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

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (long long &x : a) cin >> x;
    SegTree st(a);

    int q;
    cin >> q;
    while (q--) {
        string op; cin >> op;
        if (op == "sum") {
            int l, r; cin >> l >> r;
            cout << st.range_sum(l, r) << '\n';
        } else if (op == "add") {
            int l, r; long long x; cin >> l >> r >> x;
            st.range_add(l, r, x);
        }
    }
    return 0;
}

Что дальше?

• Расширить операции (минимум, максимум) —- замените агрегат sum на функцию min/max и адаптируйте apply.
• Для присваивания на диапазоне (set) понадобятся два ленивых поля: «прибавка» и «флаг присваивания».

Удачи в кодировании и решении задач!

#include <bits/stdc++.h> — это неофициальный «объединяющий» заголовок, который ставит GCC/Clang в Linux (и MinGW-w64 в Windows).
Если вы компилируете:

• MSVC (Visual Studio) — такого файла нет по умолчанию.
• Clang или старый/обрезанный MinGW — тоже может отсутствовать.

Что делать

1. Поставить полноценный GCC (g++)

   • Linux / WSL: sudo apt install g++
   • Windows: MinGW-w64 (например, через MSYS2: pacman -S mingw-w64-x86_64-gcc).
     После этого bits/stdc++.h будет найден.

2. Или заменить «волшебный» заголовок обычными
   В наших примерах нужны только стандартные контейнеры и алгоритмы, поэтому достаточно подключить их явно.

---

Обновлённый базовый сегмент-дерево без bits/stdc++.h

cpp
// segtree_basic.cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct SegTree {
    int n;
    vector<long long> t;

    SegTree(const vector<long long>& a) {
        n = a.size();
        t.resize(2 * n);
        copy(a.begin(), a.end(), t.begin() + n);
        for (int v = n - 1; v > 0; --v)
            t[v] = t[v << 1] + t[v << 1 | 1];
    }
    void point_set(int pos, long long val) {
        for (t[pos += n] = val; pos >>= 1;)
            t[pos] = t[pos << 1] + t[pos << 1 | 1];
    }
    long long range_sum(int l, int r) const {
        long long res = 0;
        for (l += n, ++r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += t[l++];
            if (r & 1) res += t[--r];
        }
        return res;
    }
};

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

    int n;                   // размер массива
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    SegTree st(a);

    int q;                   // число запросов
    cin >> q;
    while (q--) {
        string op; cin >> op;
        if (op == "sum") {
            int l, r; cin >> l >> r;
            cout << st.range_sum(l, r) << '\n';
        } else if (op == "set") {
            int pos; long long val; cin >> pos >> val;
            st.point_set(pos, val);
        }
    }
    return 0;
}

Компилируйте так же:

bash
g++ -std=c++17 -O2 segtree_basic.cpp -o segtree

---

Хотите автоматически подстраиваться под наличие bits/stdc++.h?

cpp
#if __has_include(<bits/stdc++.h>)
    #include <bits/stdc++.h>
#else
    #include <iostream>
    #include <vector>
    #include <algorithm>
#endif
using namespace std;

Этот трюк позволяет оставлять один и тот же файл: в Linux он возьмёт облегчённый заголовок, а в Visual Studio подключит нужные стандартные.

---

Теперь код должен собираться в любой среде. Если появятся другие ошибки компиляции — дайте знать, разберём!