多くの人がフェンウィックの木について知っています。 多くの人が使用します。 ただし、フェンウィックツリーは最大/最小で見つけることができないと考えられています。
同様に、この操作には逆関数はありません。 ただし、アルゴリズムを少し変更すると、この問題も解決できます。
注意：この記事は、フェンウィックツリーが何であるかを知っている人のために書かれており、その修正について最大限説明しています。フェンウィックツリーが何であるかわからない人は、どこか、コーメン、
ハブに関する記事でも読むことをお勧めします
1.問題の声明
配列があります。 間隔の最大値を見つけるため、およびセルの1つの値を増やすために、多くの要求が行われます。
はい、増加しています。 セルの値を減らすことはできません。そうしないと、アルゴリズムが機能しません。
2.実際にアルゴリズム
クラス（FenwickTree）を作成しましょう。FenwickTreeには、Update（int i、double cost）とMax（int left、int right）の2つのメソッドがあり、それぞれi番目のセルの値を更新し、間隔の最大値を検索します。
フェンウィックツリーと同様に、pow（2、k）> = a.size（）のようなk最小数が必要です。
ツリーを配列に保存します。
通常のフェンウィックの木との主な違い
通常のフェンウィックツリーのように、1つではなく2つの配列が必要です。それらを左右に呼び出しましょう。左の配列のi番目のセルに、セグメント[iG（i）+ 1、i]の最大値を格納し、右の配列のi番目のセルに、i <powのセグメント[i、i + G（i）-1]の最大値を格納します（2、k）およびi = pow（2、k）のセグメント[i、i]上。
実際にクラス：
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); };
PreProc（）関数は、初期データをツリーに追加するために必要であり、驚くほど複雑に見えます：
void FenwickTree::PreProc(){ for(int i=0;i<a.size();i++) Update(i+1,a[i]); }
私はあなたの注意を引きます、それはi + 1です 配列G（x）= x-（x＆（x-1））の遷移関数はx> 0で機能します
それでは、更新関数を書きましょう。
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); } }
および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; }
以上です。
ご覧のとおり、最大のフェンウィックツリーは非常に簡単かつ迅速に記述できます（これは非常に重要です）。