BIT To Query Для заданного диапазона

Question

У нас есть массив arr[0 .,, н-1]. Мы должны быть в состоянии эффективно найти минимальное значение от индекса qs (начало запроса) до qe (конец запроса), где 0 <= qs <= qe <= n-1

Я знаю данные structure Segment Дерево для этого. Мне интересно, если Binary Index Tree (BIT) также может использоваться для этой операции.

Если да, пожалуйста, как я могу использовать BIT В этом сценарии и является ли массив статическим, можем ли мы изменить элемент и обновить наш BIT или дерево сегментов.

Answer 1

Да, BIT также может решить эту проблему с помощью небольшой хитрости.

Давайте использовать num [] представляет массив init, а idx[] представляет массив BIT.

Ключевым моментом является то, что мы должны использовать idx[k], представляющее минимальное значение диапазона num[k-lowbit(k)+1, 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;
   }

Надежда может помочь вам.