BITのプリフィックスサムMを持つ位置を見つける方法は？

Question

長さNの接頭辞の合計を持つバイナリインデックスツリーを作成したとします。メイン配列には0と1が含まれています。今私はどのインデックスが接頭辞の合計Mを持っているかを見たいと思っています（つまり、正確にはM 1です）。私の配列のように

はa[]={1,0,0,1,1};

プレフィックス合計は{1,1,1,2,3};

今第三インデックスiはBITでこのインデックスを見つけることができますどのように2

の（0ベース）は、プレフィックス和のようになりますか？

ありがとうございます。

Answer 1

なぜインデックスをバイナリ検索できないのですか？それはO(log n * log n)時間かかるでしょう。ここには簡単な実装があります -

int findIndex(int sum) { 
    int l = 1, r = n; 
    while(l <= r) { 
     int mid = l + r >> 1; 
     int This = read(mid); 
     if(This == sum) return mid; 
     else if(This < sum) l = mid+1; 
     else r = mid-1; 
    } return -1; 
} 

私はread(x)関数を使用しました。それはO(log n)時間に[1,x]の間隔の合計を返します。全体の複雑さはO(log^2 n)になります。
希望します。

Answer 2

配列a[n]の要素が非負である（プレフィックス和アレイp[n]が非減少である）場合は、BITからインデックスによってクエリプレフィックス合計としてプレフィックス和で要素を見つけることができ、O（LOGN）時間をとります。唯一の違いは、後で検索する必要のあるサブツリーを決定するために、各レベルで得られる接頭辞の合計を入力と比較する必要があることです。接頭辞の合計が入力よりも小さい場合は、それ以外の場合は、右のサブツリーを検索します。目的の接頭辞の合計を集計するノードに到達するまでこのプロセスを繰り返します。この場合、ノードのインデックスが返されます。プレフィックスの合計がBITで自然にソートされるため、この考え方はバイナリ検索に似ています。 a[n]に負の値がある場合、BITの接頭辞の合計はこの場合ソートされないため、このメソッドは機能しません。