Дерево отрезков

Дерево отрезков: сумма на отрезке и обновление точки за O(log n).

Префиксные суммы отвечают на «сумму на отрезке» за O(1), но ломаются, как только массив начинает МЕНЯТЬСЯ: одно обновление — пересчёт всех префиксов. Дерево отрезков делает и запрос, и обновление за O(log n). Идея: над массивом строится двоичное дерево; каждая вершина хранит сумму своего отрезка. Корень — сумма всего массива, листья — отдельные элементы. • обновление элемента затрагивает только вершины на пути от листа к корню — их O(log n); • запрос [l, r] разбивается на O(log n) готовых отрезков дерева.

Попробуйте сами — код можно менять

#include <iostream>
#include <vector>
#include <string>

int n;
std::vector<long long> tree;

void update(int v, int tl, int tr, int pos, long long val) {
    if (tl == tr) {
        tree[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * v, tl, tm, pos, val);
    else update(2 * v + 1, tm + 1, tr, pos, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

long long query(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return 0;          // отрезки не пересекаются
    if (l <= tl && tr <= r) return tree[v];  // отрезок дерева целиком внутри
    int tm = (tl + tr) / 2;
    return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r);
}

int main() {
    int q;
    std::cin >> n >> q;
    tree.assign(4 * n, 0);

for (int i = 1; i <= n; i++) {
        long long x;
        std::cin >> x;
        update(1, 1, n, i, x);
    }

while (q--) {
        std::string type;
        std::cin >> type;
        if (type == "set") {
            int pos;
            long long val;
            std::cin >> pos >> val;
            update(1, 1, n, pos, val);
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Входные данные (пример — можно менять)

Введите: 5 3, массив 1 2 3 4 5, затем: sum 2 4 / set 3 10 / sum 2 4

Запустите пример: сумма [2,4] сначала 9, после set 3 10 становится 16. Как читать код: • вершина v отвечает за отрезок [tl, tr]; дети — половины отрезка, номера 2v и 2v+1; • массив tree размером 4n гарантированно вмещает всё дерево; • query возвращает 0 для непересекающихся отрезков — ноль нейтрален для суммы. Дерево отрезков — конструктор: замените + на min или max (и нейтральный элемент на бесконечность) — получите запросы минимума/максимума. Продвинутая версия с «ленивыми» обновлениями умеет менять целые отрезки за O(log n) — изучите её, когда встретите такую задачу.

Задание: переделайте дерево на МАКСИМУМ на отрезке (три правки: операция, нейтральный элемент, вывод) и проверьте на своём примере. Отметьте урок пройденным.