BIT To Query For a given range

Question

We have an array arr[0 . . . n-1]. We should be able to efficiently find the minimum value from index qs (query start) to qe (query end) where 0 <= qs <= qe <= n-1

I know the data structure Segment Tree for this. I am wondering if Binary Index Tree (BIT) can also be used for this operation.

If Yes, please How can i use BIT in this scenario and Is the array is to static , can we change the element and update our BIT or Segment Tree.

Answer 1

Yes, BIT also can solve this problem just with a little trick.

Let's use num[] represents the init array, and idx[] represents the BIT array.

The keypoint is we should use idx[k] represent the min value of range num[k-lowbit(k)+1, k], k is start from 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;
   }

Hope can help you.