Дерево ОтрезковSegment Tree

Дерево строится рекурсивно поверх фиксированного массива: корень отвечает за весь диапазон [0, n-1], каждый внутренний узел делит свой диапазон пополам между двумя детьми, а лист отвечает за один элемент. Каждый узел хранит агрегат (сумму, минимум и т.д.) по своему диапазону — узел с диапазоном [l, r] хранит agg(a[l..r]), вычисленный как agg(левый ребёнок) ⊕ agg(правый ребёнок), где ⊕ — любая ассоциативная операция (сложение, min, max, gcd, XOR...). Всего в дереве O(n) узлов (примерно 2n-1 для полного бинарного дерева над n листьями), а высота — O(log n), потому что диапазон делится пополам на каждом уровне.The tree is built recursively over the fixed array: the root is responsible for the entire range [0, n-1], each internal node splits its range in half between two children, and a leaf is responsible for a single element. Every node stores an aggregate (sum, min, etc.) over its range — a node with range [l, r] stores agg(a[l..r]), computed as agg(left child) ⊕ agg(right child), where ⊕ is any associative operation (addition, min, max, gcd, XOR...). The tree has O(n) nodes total (about 2n-1 for a complete binary tree over n leaves), and height O(log n), because the range is halved at every level.

Запрос диапазона [l, r] спускается от корня: если диапазон текущего узла целиком внутри [l, r] — вернуть его агрегат сразу, не спускаясь глубже; если целиком снаружи — вернуть нейтральный элемент (0 для суммы, +∞ для минимума), тоже без спуска; иначе (частичное пересечение) — рекурсивно опросить обоих детей и объединить результаты. На каждом уровне высоты рекурсия "разветвляется" не более чем в двух узлах с частичным пересечением, остальные обрываются мгновенно — отсюда и O(log n), а не O(n), несмотря на кажущуюся похожесть на полный обход. Точечное обновление проще: путь от корня до нужного листа единственен, длина пути — высота дерева, O(log n), и на обратном пути пересчитываются агрегаты предков.A range query [l, r] descends from the root: if the current node's range is entirely inside [l, r] — return its aggregate immediately, without descending further; if entirely outside — return the neutral element (0 for sum, +∞ for min), also without descending; otherwise (partial overlap) — recursively query both children and combine the results. At each level of height, the recursion "branches" into at most two partially-overlapping nodes, the rest terminate instantly — hence O(log n), not O(n), despite superficially resembling a full traversal. A point update is simpler: the path from the root to the target leaf is unique, its length is the tree's height, O(log n), and ancestor aggregates are recomputed on the way back up.

struct SegTree {
    std::vector<long long> tree;
    int n;
    SegTree(const std::vector<int>& a) : n((int)a.size()), tree(4 * a.size()) { build(1, 0, n - 1, a); }

    void build(int node, int lo, int hi, const std::vector<int>& a) {
        if (lo == hi) { tree[node] = a[lo]; return; }
        int mid = (lo + hi) / 2;
        build(2 * node, lo, mid, a);
        build(2 * node + 1, mid + 1, hi, a);
        tree[node] = tree[2 * node] + tree[2 * node + 1];      // ⊕ = сложение здесь// ⊕ = addition here
    }

    void update(int node, int lo, int hi, int idx, int val) {
        if (lo == hi) { tree[node] = val; return; }
        int mid = (lo + hi) / 2;
        if (idx <= mid) update(2 * node, lo, mid, idx, val);
        else          update(2 * node + 1, mid + 1, hi, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;                       // нейтральный элемент для суммы// neutral element for sum
        if (l <= lo && hi <= r) return tree[node];              // диапазон узла целиком внутри — не спускаемся// node range fully inside — don't descend
        int mid = (lo + hi) / 2;
        return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
    }
};

Дерево построено над фиксированным массивом из 6 чисел. query проигрывает рекурсию узел за узлом: зелёным — узлы, чей диапазон целиком внутри запроса (агрегат взят напрямую, без дальнейшего спуска), серым — узлы вне диапазона (пропущены мгновенно). update показывает путь от листа до корня с пересчётом сумм.The tree is built over a fixed array of 6 numbers. query auto-plays the recursion node by node: green marks nodes whose range is entirely inside the query (aggregate taken directly, no further descent), gray marks nodes outside the range (skipped instantly). update shows the path from the leaf to the root with sums recomputed.

Дерево отрезков не хранит ключи вообще — оно строится над фиксированными позициями массива, а не над множеством значений, которые вставляются и удаляются. Отсюда нет операций вставки/удаления элемента в привычном для BST смысле (хотя существуют более сложные "динамические" варианты с этой возможностью) — базовая версия работает над массивом заранее известного размера n, и это её главное структурное отличие от BST-семейства (2.3.2.1-2.3.2.5): она отвечает не "какой элемент здесь", а "что можно сказать про весь этот диапазон элементов сразу".A segment tree doesn't store keys at all — it's built over fixed array positions, not over a set of values that get inserted and removed. Hence there's no insert/delete-element operation in the BST sense (though more elaborate "dynamic" variants with that capability exist) — the basic version operates over an array of known size n, and that's its main structural difference from the BST family (2.3.2.1-2.3.2.5): it answers not "what element is here" but "what can be said about this whole range of elements at once."