I do not think a fast/batched version will do much better. If an element is deleted inside a block/batch, then you have two options: (1) do the naive algorithm done above for the rest of the block; (2) mask just what will come after it, shift the mask, and then OR it back, but this will only work correctly if this is the last block, otherwise the next block needs to considered too, in fact, if sufficient elements are deleted an arbitrary number of next block may need to be considered by those shifts. I really would like to see the performance difference between the two approaches.