木の形の配列は区間の最も値を求めます(転載)

ツリー配列(Binary Index Tree)はバイナリのいくつかの性質の巧みな区分区間を利用して、1種のプログラミングで、時間と空間の上ですべてとても理想的な区間和を求めるアルゴリズムで、同様に私達はツリー配列の優美な区間区分方法を利用して1つのシーケンスの最値を求めることができます
規則はnum[]で元の配列を表し、idx[]でインデックス配列を表し、Lowbit(x)=x&(-x)
ツリー配列の和は配列idx[]を構築することによってidx[k]=sum(num[tk]),tk[k-Lowbit(k)+1,k]となり,同様の方法で最値インデックス配列を構築する.
最大値を例にとると,まずクエリ中に配列を変更しない場合について議論し,idx[k]で[k-Lowbit(k)+1,k]区間内の最大値を記録し,和を求める方法を模倣して得る.

void Init(int n){
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=Lowbit(j)){
			idx[j]=MAX(idx[j],num[i]);
		}
	}
}

 
この方法は、関数を呼び出すたびに配列を初期化する必要があります.これにより、データ範囲が大きい場合には美しくありません.これにより、次のように変更できます.

void Init(int n){
     for(int i=1;i<=n;i++){
          idx[i]=num[i];
          for(int j=1;j<Lowbit(i);j<<=1){
               idx[i]=MAX(idx[i],idx[i-j]);
          }
     }
}

このようにk番目の数に更新すると、すべてのt(t次にクエリの問題を見て、区間[l,r]がその区間を複数のセル間に変換して最値を求める方法は、後から各インデックス数の範囲を判断することであり、第k項まで行った場合、その数制御の範囲は[k-Lowbit(k)+1,k]であり、k-Lowbit(k)+1が求めた範囲内であればその区間の最値を最値の判断に加えて、地k-Lowbit(k)に移行し、そうでなければk番目の数のみを最値判定してk-1に移動し,具体的には以下のように実現する.

int Query(int l,int r){
     int ans=num[r];
     while(true){
          ans=MAX(ans,num[r]);
          if(r==l) break;
          for(r-=1;r-l>=Lowbit(r);r-=Lowbit(r)){
               ans=MAX(ans,idx[r]);
          }
     }
     return ans;
}

 
このクエリの複雑さはlog(n)
stアルゴリズムの複雑度O(nlog(n)/O(1),線分ツリーO(nlog(n))/(log(n)),樹状配列O(空間複雑度stはO(nlog(n)),線分樹O(n),定数が大きく,樹状配列はO(n)である
プログラミング上stとツリー配列は比較的容易に実現でき,セグメントツリーコードは長い
また、線分ツリーは柔軟性が高い
PKU 3264題:
st　  　Memory: 6372K　 Time: 1250MS　　964B
BIT　　Memory: 716K　　Time: 1282MS　　933B
SegTreeは未測定でstより大きい
 
さらに、クエリーしながら変更する場合に拡張できます.
親ノードを直接更新するたびに、インデックス配列の正確性を維持するために、各親ノードを更新するときに、すべての息子ノードをクエリーし、最適値を取得します.コードは次のとおりです.

void Modify(int p,int v,int n){
    num[p]=v;
    for(int i=p;i<=n;i+=Lowbit(i)){
        idx[i]=MAX(idx[i],v);
        for(int j=1;j<Lowbit(i);j<<=1){
            idx[i]=MAX(idx[i],idx[i-j]);
        }
    }
}

 
複雑度O(log^2(n),HDU 1754 I hate it 437 MS 1776 K
また,この手法には,最大値を求める際に,ある値が更新された値が元の値より大きい場合には,子ノードを問い合わせる必要がないことが容易に考えられるので,内部ループに,子ノードをスキャンする必要があるか否かを判断する判断を加えることができ,データの問題である可能性があり,この問題の時間に大きな変化はない.
変換元:http://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html