Каноническая рекурсивная реализация дерева отрезков на сумму с точечным обновлением?
Нужна рабочая база: построить дерево отрезков на сумму, уметь update(pos, val) (присвоить) и query(l, r) (сумма на отрезке). Дайте корректный шаблон на C++ с асимптотикой, чтобы от него отталкиваться.
2 ответа
Классическая рекурсия с корнем 1 и полуинтервалами не нужна — удобнее закрытые отрезки [tl, tr]. Узел v отвечает за [tl, tr], потомки делят пополам.
#include <bits/stdc++.h>
using namespace std;
int n;
long long t[4 * 100000];
int a[100000];
void build(int v, int tl, int tr) {
if (tl == tr) { t[v] = a[tl]; return; }
int tm = (tl + tr) / 2;
build(2*v, tl, tm);
build(2*v+1, tm+1, tr);
t[v] = t[2*v] + t[2*v+1];
}
void update(int v, int tl, int tr, int pos, long long val) {
if (tl == tr) { t[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);
t[v] = t[2*v] + t[2*v+1];
}
long long query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0; // пустое пересечение
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
return query(2*v, tl, tm, l, min(r, tm))
+ query(2*v+1, tm+1, tr, max(l, tm+1), r);
}
Вызовы: build(1, 0, n-1), update(1, 0, n-1, pos, val), query(1, 0, n-1, l, r).
Сложность: build — O(n), update — O(log n), query — O(log n). Память O(n). Обязательно long long для суммы — иначе переполнение int при больших значениях.
Ключевая деталь корректности — обработка l > r в начале query (возвращаем нейтральный элемент, для суммы это 0). Без неё при разбиении [l, min(r,tm)] и [max(l,tm+1), r] один из подзапросов может оказаться пустым, и без проверки вы уйдёте в некорректную рекурсию.
Для минимума нейтраль — LLONG_MAX, для максимума — LLONG_MIN, для произведения по модулю — 1. Меняете только нейтральный элемент и операцию слияния t[v] = combine(t[2v], t[2v+1]) — вся остальная структура та же.