Fenwick tree for maximum

Many people know about the Fenwick tree. Many use it. However, it is believed that the Fenwick tree cannot find the maximum / minimum.
Like, this operation has no reverse. However, small changes in the algorithm allow us to solve this problem too.
NB: The article is written for those who know what the Fenwick tree is and describes its modification for the maximum. Those who do not know what the Fenwick tree is, it is recommended to read about it somewhere, even in Kormen, at least in an article on Habré .

1. Task setting

There is an array. There are many many requests for it, both for finding the maximum in the interval, and for increasing the value in one of the cells.
Yes, it is to increase. The value in the cell can not 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, updating the value in the i-th cell and searching 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 wood Fenwick

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

class FenwickTree { 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); }; 

The PreProc () function is needed to add our initial data to the tree and it looks terribly difficult:

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

I pay attention, namely i + 1, since our transition function in arrays G (x) = x- (x & (x-1)) works for x> 0
Now we write the Update function:

 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=iG(i); } } 

and 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(iG(i)>=l) { res=max(res,left[i]); i=iG(i); } return res; } 

That's all.

As you can see, the Fenwick tree for the maximum can be written very simply and very quickly (which is sometimes critical).