*Дерево отрезков* — структура данных, позволяющая находить значение некоторой ассоциативной функции `f` на произвольном отрезке `a_i, a_{i + 1},..., a_j` массива за асимптотику `O(log N)`. В качестве `f` можно взять сумму, максимум или минимум. Изменять элементы (увеличивать, умножать, присваивать новое значение) можно также на отрезке за `O(log N)`. Можно комбинировать несколько операций изменения и функций.
Для обеспечения указанной эффективности над массивом надстраивается пирамида, каждый элемент которой содержит результат вычислений функции для двух элементов ниже (и рекурсивно для всего поддерева) и "отложенную" операцию, которая применяется к этому результату.

В нижнем слое пирамиды (листья бинарного дерева) находятся значения типа T, в остальных слоях -- пара значений из типов Operation и State, у которого должен быть определен конструктор-преобразователь из типа T и конструктор по умолчанию, возращающий нейтральный элемент для функции `f`. Функция `f` принимает два значения типа State и возвращает значение типа State.
"Отложенная" операция -- это тип, у которого должны быть определены три метода:
```c++
struct Operation {
State operator()(State s, size_t k) const;
T operator()(T v) const;
optional<Operation> combine(Operation other) const;
}
```
Если операции изменения выполняются только над одним элементом, то можно обновлять пирамиду снизу вверх. В общем случае операция изменения спускается сверху вниз, пока она будет соответствовать поддереву целиком, где она комбинируется с операцией, которая уже применена к этому поддереву, а при возврате из рекурсии обновляется поле State родительских вершин в пирамиде.
Указатели на дочерние вершины можно не хранить, если воспользоваться уже рассмотренным [приемом для хранения пирамиды в массиве](51057-4.html). Дочерние вершины для вершины `i` имеют номера `2*i` и `2*i+1`, а родительская -- номер `|__ i//2 __|`. Вершина пирамиды находится в элементе массива с индексом 1.
```c++
template <typename T, typename State, typename Operation>
class STree {
using func=function<State(State,State)>;
size_t n,n2;
vector<pair<optional<Operation>,State>> pyrmd;
vector<T> values;
func f;
void update(size_t i, size_t k1, size_t k2) {
if(i>=n2) return; // не применяется к листу
pyrmd[i].second=f(state(2*i,k1),state(2*i+1,k2)); // обновляем состояние поддерева
}
void add_op(size_t i, Operation op) { // добавить или применить операцию
if(i>=n2) values[i-n2]=op(values[i-n2]); // применить к листу
else if(!pyrmd[i].first) pyrmd[i].first=op;
else pyrmd[i].first=pyrmd[i].first->combine(op);
}
void clear_op(size_t i, size_t k) { // сдвинуть операцию вниз
if(i>=n2 || !pyrmd[i].first) return;
Operation op=*(pyrmd[i].first);
pyrmd[i].second=op(pyrmd[i].second,k);
pyrmd[i].first={};
add_op(2*i,op);
add_op(2*i+1,op);
}
State state(size_t i, size_t k) { // состояние поддерева или листа
if(i>=n2) {
if(i-n2>=n) return State();
return State(values[i-n2]);
}
if(pyrmd[i].first) return (*(pyrmd[i].first))(pyrmd[i].second,k);
return pyrmd[i].second;
}
State calc(size_t p, size_t k, size_t pi, size_t pj, size_t i, size_t j) {
if(k==1) return State(values[p-n2]); // лист
if(i<=pi && pj<=j) // все поддерево
return state(p,pj+1-pi);
clear_op(p,pj+1-pi); // сдвинуть операцию
k/=2;
size_t m=pi+k;
// вернуть из одного поддерева
if(j<m) return calc(p*2,k,pi,m-1,i,j);
if(i>=m) return calc(p*2+1,k,m,pj,i,j);
// или комбинацию
return f(calc(p*2,k,pi,m-1,i,j), calc(p*2+1,k,m,pj,i,j));
}
void apply(size_t p, size_t k, size_t pi, size_t pj, size_t i, size_t j, optional<Operation> op, T v) {
if(k==1) { // лист
if(op) values[p-n2]=(*op)(values[p-n2]);
else values[p-n2]=v;
return;
}
if(i<=pi && pj<=j) // полный отрезок
{ if(op) add_op(p,*op);
return;
}
clear_op(p,pj+1-pi); // сдвинуть операцию
k/=2;
size_t m=pi+k;
if(i<m) // обработать поддеревья, если есть
apply(p*2,k,pi,m-1,i,j,op,v);
if(j>=m)
apply(p*2+1,k,m,pj,i,j,op,v);
update(p,min(pj+1,m)-pi,max((int)(pj+1-m),0)); // пересчитать
}
public:
STree(size_t n, func f):n(n),n2(bit_ceil(n-1)),pyrmd(n2,{{},State()}),values(n,T()),f(f) {}
size_t size() const { return n; } // размер
State calc(size_t i, size_t j) { // получить значение функции на отрезке
if(i>=n || j>=n || i>j) throw runtime_error("Wrong index");
return calc(1,n2,0,n-1,i,j);
}
T get(size_t i) { // получить i-й элемент
if(i>=n) throw runtime_error("Wrong index");
size_t p=1, k=n2, a=0, b=n;
while(p<n2) // бинарный поиск, пока не дойдем до листа
{ clear_op(p,b-a);
k/=2;
size_t m=a+k;
if(i<m) {
p=2*p;
b=m;
}
else {
p=2*p+1;
a=m;
}
}
return values[p-n2];
}
void set(size_t i, T v) { // изменить i-й элемент
if(i>=n) throw runtime_error("Wrong index");
apply(1,n2,0,n-1,i,i,{},v);
}
void apply(size_t i, size_t j, Operation op) { // изменить значения на отрезке
if(i>=n || j>=n || i>j) throw runtime_error("Wrong index");
apply(1,n2,0,n-1,i,j,op,T());
}
};
```
В декартовом дереве по неявному ключу уже подсчитывается количество элементов в поддереве. Можно добавить еще несколько полей, которые будут рассчитываться при разрезании и слиянии дерева. Также можно сохранять операции, которые применяются ко всему поддереву. Преимуществом дерева отрезков на дерамиде по сравнению с реализацией на массиве фиксированного размера является возможность удаления и вставки значений.