最大のフェンウィックツリー

多くの人がフェンウィックの木について知っています。 多くの人が使用します。 ただし、フェンウィックツリーは最大/最小で見つけることができないと考えられています。

同様に、この操作には逆関数はありません。 ただし、アルゴリズムを少し変更すると、この問題も解決できます。

注意：この記事は、フェンウィックツリーが何であるかを知っている人のために書かれており、その修正について最大限説明しています。フェンウィックツリーが何であるかわからない人は、どこか、コーメン、 ハブに関する記事でも読むことをお勧めします

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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以上です。



ご覧のとおり、最大のフェンウィックツリーは非常に簡単かつ迅速に記述できます（これは非常に重要です）。