arrays of bits

[sanchez_masherano]

In the definition of NEXTWHITE(i) it should be "j>i" right?

I'll assume that and make a suggestion for the (a) question.

In addition to the X[1::n] array you need a binary search tree where all indexes corresponding to a 0 in X are stored in sorted order. Lets call it BST. Initially BST holds all indexes between 1 and n (because all index positions of X are initially set to 0).

Now for LOCKUP(i) you use X. That takes O(1).

For BLACKEN(i) you set the corresponding bit in X which takes O(1), but you also remove the i index from BST (because it no longer corresponds to a 0) and that takes O(log n). All in all that's O(log n).

Finally for NEXTWHITE(i) you make a search in BST for the smallest index bigger than i. That will be j and it takes O(log n) to find it. (If i is in BST, j is its next bigger neighbour. If i is not in BST, j is where i should be if it were in BST).

So with BST in addition to X you get LOCKUP in O(1) and BLACKEN and NEXTWHITE in O(log n) which was requested in (a).

@razzle, thank you, indeed your assumption was right; but what about the cost of constructiing the BST? isnt more than logn?