-1

配列 arr[0 があります。. . n-1]。0 <= qs <= qe <= n-1 のインデックス qs (クエリ開始) から qe (クエリ終了) までの最小値を効率的に見つけることができるはずです。

structure Segmentこのためのデータツリーを知っています。Binary Index Tree (BIT)この操作にも使用できるかどうか疑問に思っています。

はいの場合BIT、このシナリオでどのように使用できますか、配列は静的ですか、要素を変更して BIT またはセグメント ツリーを更新できますか。

4

1 に答える 1

0

はい、BIT でもちょっとしたコツでこの問題を解決できます。

num[] は init 配列を表し、idx[] は BIT 配列を表します。

キーポイントは、範囲 num[k-lowbit(k)+1, k] の最小値を表す idx[k] を使用する必要があることです。k は 1 から始まります。

   #define MAX_VALUE 10000
   #define lowbit(x) (x&(-x))
   int num[MAX_VALUE];
   int idx[MAX_VALUE];
   void update(int pos, int val, int max_index) {
       num[pos] = val;
       while (pos < max_index) {
            idx[pos] = min(idx[pos], val);
            pos += lowbit(pos);
       }
   } 

   int getMin(int left, int right) {
        int res = num[right];
        while (true) {
            res = min(res,num[right]); 
            if(left == right)break; 
            for(right-=1;right-left>=lowbit(right);right-=lowbit(right)){ 
                res=min(res,idx[right]); 
            } 
        }
        return res;
   }

希望はあなたを助けることができます。

于 2015-01-09T16:11:42.633 に答える