algorithm - BIT 查询给定范围

Question

我们有一个数组 arr[0 。. . n-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;
   }

希望能帮到你。