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.
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.
