Segment Tree

The segment tree: range sum and point update in O(log n).

Prefix sums answer "sum on a segment" in O(1) but break as soon as the array starts CHANGING: one update — recompute all prefixes. The segment tree does both the query and the update in O(log n). The idea: build a binary tree over the array; each node stores the sum of its segment. The root — the sum of the whole array, the leaves — individual elements. • updating an element touches only the nodes on the path from the leaf to the root — O(log n) of them; • a query [l, r] decomposes into O(log n) ready-made tree segments.

Try it yourself — the code is editable

#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;
}

Input (sample — feel free to edit)

Enter: 5 3, the array 1 2 3 4 5, then: sum 2 4 / set 3 10 / sum 2 4

Run the example: the sum of [2,4] is 9 at first, and after set 3 10 it becomes 16. How to read the code: • node v is responsible for the segment [tl, tr]; its children are the halves of the segment, numbered 2v and 2v+1; • the tree array of size 4n is guaranteed to fit the whole tree; • query returns 0 for non-overlapping segments — zero is neutral for the sum. The segment tree is a construction kit: replace + with min or max (and the neutral element with infinity) — and you get minimum/maximum queries. The advanced version with "lazy" updates can modify whole segments in O(log n) — study it when you meet such a problem.

Task: convert the tree to range MAXIMUM (three edits: the operation, the neutral element, the output) and test it on your own example. Mark the lesson as completed.