Дерево Фенвика для максимума

Про дерево Фенвика многие знают. Многие его используют. Однако считается, что деревом Фенвика нельзя находить максимум/минимум.
Мол, эта операция не ассоциативна. Однако небольшие изменения алгоритма позволяют нам решить и эту задачу тоже.
NB: Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.Тем, кто не знает, что такое дерево Фенвика, рекомендуется прочитать об этом где-нибудь, хоть в Кормене, хоть в статье на хабре

1.Постановка задачи

Есть массив. К нему выполняется много много запросов как на нахождение максимума на интервале, так и на увеличение значения в одной из ячеек.
Да, именно на увеличение. Значение в ячейке уменьшать нельзя, иначе алгоритм не работает.

2.Собственно алгоритм

Создадим класс — FenvikTree, который будет иметь два метода — Update(int i,double cost) и Max(int left,int right) — соответственно апдейт значения в i-ой ячейке и поиск максимума на интервале.
Как всегда в дереве Фенвика, нам понадобится k-минимальное число, такое что pow(2,k)>=a.size()
Хранить дерево будем в массиве.

Главное отличие от обычного дерева Фенвика

Нам понадобятся два массива, а не один, как в обычном дереве Фенвика, назовем их left и right
В i-й ячейке массива left будем хранить максимум на отрезке [i-G(i)+1,i], в i-й ячейке массива right— максимум на отрезке [i,i+G(i)-1] при i<pow(2,k) и на отрезке [i,i] при i=pow(2,k).
Собственно класс:

class FenvikTree { private:     vector<double> a;     vector<double> left;     vector<double> right; public:     void PreProc();     double Max(int left,int right);     void Update(int i,double cost); }; 

Функция PreProc() нужна, чтобы добавить в дерево наши первоначальные данные и выглядит ужасающе сложно:

void FenvikTree::PreProc(){  for(int i=0;i<a.size();i++) Update(i+1,a[i]); } 

Обращаю внимание, именно i+1, т.к. наша функция перехода в массивах G(x) = x-(x&(x-1)) работает для x>0
Теперь напишем функцию Update:

void FenvikTree::Update(int r,double cost) {     a[r-1]=cost;     int i=r;     while(i<=pow(2.0,double(k)))     {         left[i]=max(left[i],cost);         i=i+G(i);     }     i=r;     while(i>0)     {         right[i]=max(right[i],cost);         i=i-G(i);     } } 

и Max:

double FenvikTree::Max(int l,int r){     double res=0;     int i=l;     while(i+G(i)<=r)     {         res=max(res,right[i]);         i=i+G(i);     }     if(a[i-1]>res) ans=i;     res=max(res,a[i-1]);     i=r;     while(i-G(i)>=l)     {         res=max(res,left[i]);         i=i-G(i);     }     return res; } 

Вот и все.

Как видите, дерево Фенвика для максимума можно написать очень просто и очень быстро(что иногда критично).