Fenwick tree for maximum

Many people know about the Fenwick tree. Many use it. However, it is believed that the Fenwick tree cannot be found maximum / minimum.
Like, this operation has no inverse. However, small changes to the algorithm allow us to solve this problem as well.
NB: This article was written for those who know what a tree Fenwick and describes a modification to maksimuma.Tem who do not know what tree Fenwick, it is recommended to read about it somewhere, even in Louis Marie de la Haye, though in the article on Habré .

1. Statement of the problem

There is an array. Many requests are made to it, both to find the maximum in the interval and to increase the value in one of the cells.
Yes, it’s an increase. The value in the cell cannot be reduced, otherwise the algorithm does not work.

2. Actually the algorithm

Let's create a class - FenwickTree, which will have two methods - Update (int i, double cost) and Max (int left, int right) - respectively update the values ​​in the i-th cell and search for the maximum in the interval.
As always in the Fenwick tree, we need a k-minimal number such that pow (2, k)> = a.size ()
We will store the tree in an array.

The main difference from the usual Fenwick tree

We need two arrays, and not one, as in the usual Fenwick tree, let's call them left and right.
In the i-th cell of the left array, we will store a maximum on the segment [iG (i) + 1, i], in the i-th cell of the array right - maximum on the segment [i, i + G (i) -1] for i
Actually class:

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

The PreProc () function is needed to add our initial data to the tree and looks appallingly complicated:

void FenwickTree::PreProc(){
 for(int i=0;i

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

void FenwickTree::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 FenwickTree::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;
}

Вот и все.

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