Запрос и изменение элемента

Всё дерево отрезков стоит на двух наблюдениях.

Любой отрезок разбивается на $O(\log n)$ узлов дерева. Не на произвольные куски, а именно на узлы, ответы для которых уже посчитаны.

Каждый элемент лежит ровно в $\log n$ узлах — на пути от своего листа к корню. Значит изменение элемента затрагивает только этот путь.

Запрос

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

Три строки-случая: узел не пересекается с запросом, узел целиком внутри, узел пересекается частично. Первые два — остановка, третий — спуск.

Почему логарифм

На каждом уровне дерева частично пересечённых узлов не больше двух — по одному у левой и правой границы запроса. Все остальные либо целиком внутри (остановка), либо целиком снаружи (остановка).

Уровней $\log n$, значит спусков не больше $2 \log n$, а посещённых узлов — не больше $4 \log n$.

Изменение элемента

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

Спуск до листа, изменение, пересчёт по дороге вверх. Ровно $\log n$ узлов.

Замечание про нейтральный элемент

В первой строке запроса возвращается NEUTRAL — значение, не влияющее на ответ: ноль для суммы, $+\infty$ для минимума. Требования к нему разобраны в статье «Какие функции ложатся в дерево».

Второй способ — не заходить в непересекающиеся узлы вовсе:

if (l <= tm) left = query(2 * v, tl, tm, l, r);
if (r > tm) right = query(2 * v + 1, tm + 1, tr, l, r);

Он избавляет от нейтрального элемента, но требует аккуратности при склейке. На составных узлах обычно берут именно его.