Set(i) sets the ith bit O(1)
Unset(j) unsets the jth bit Set(i,j) O(1)
sets the bits b/w i and j Unset(i,j) o(logn)..??
unsets the bits b/w i and j O(logn) ???
Design a data structure for this problem with minimum time and space complexity.
#include
int set(int N,int i){
N = N | (1<=j;k--){
N = set(N,k);
}
return N;
}
int main(){
int N=7;
int i=3,j=2;
N=set(N,i);
printf("%d\n",N);
N=unset(N,j);
printf("%d\n",N);
N=set_range(0,3,1);
printf("%d\n",N);
/*unset(N,i,j);*/
return 0;
}
Time Complexity O(n)
Space Complexity O(1)
Optmization O(logn)
Yes we can use RMQ mechenism to do this , Segment Tree is Awesome Option to set upper bound for set(i,j,) & unset(i,j) will be O(logn)
No comments :
Post a Comment