Data structure representing a two-value array with 3 operations

Question

Let's have n values. All values are false and can be changed to true. I want 3 operations on these values with certain time complexities:

• val(i) -> returns value at index i. Time complexity - O(1).
• change(i) -> change value at index i to true. Time complexity - amortized O(1).
• find(i) -> return closest index to index i, that contains value false (if there is false on i then return i). Time complexity - O(log n).

I don't really care about space complexity. The structure is initialized at the beginning with fixed length. It doesn't really matter how much time the initizalization takes.

How should a data structure used for these operations look like?

Answer 1

Set up a segment tree on [0, n) and, for each elementary interval [i 2^k, (i+1) 2^k), store the AND of the boolean values in that interval.

val(i) is constant-time because it's just an array lookup.

change(i) is amortized constant-time if we alter the usual rootward propagation algorithm to exit early if there is no change at a particular level. This is because at any given time, the number of writes to intervals k levels from the root is at most half of the number of writes to intervals k+1 levels from the root (prove this by induction on k).

find(i) can be implemented in logarithmic time as follows. First observe that it suffices to find the nearest false left neighbor and the nearest false right neighbor and take the nearer of the two. To find the nearest false right neighbor for position i, decompose [i, n) into elementary intervals. Find the leftmost of these intervals that contains a false (i.e., its AND is false). Proceed leafward from this interval, checking to see at each level if the left half has a false. If it does, descend to it; otherwise, use the right half.

On a unit-cost RAM (i.e., the theoretical version of real hardware), we can get find(i) down to time O(log n / log log n) time with O(n / log n) words of storage by changing the tree fanout from 2 to the word size (Theta(log n)) and using bitwise operations.