Thank you for that explanation! I apologize; I totally agree that you don't need to walk the superblocks. I don't know why I wrote that instead of what I was re

Thank you for that explanation! I apologize; I totally agree that you don't need to walk the superblocks. I don't know why I wrote that instead of what I was really thinking: - The vector represents a subset of N values, hence requires Z=N bits. - The blocks themselves require at least Z bits to store, so to be succinct the superblocks must be o(Z) in space. - Consequently, there are at most o(Z) superblocks. - It follows that there are at most o(Z) blocks (since otherwise you would have a super-constant number to walk per block). - Thus, each block takes up super-constant space (and the popcount component must increase in size as well). - Your rank lookups require at least O(popcount-size) time, which is super-constant. I think you're right though that the problem I was seeing just falls back to the general "we know it's bugged, but we promise we won't bugabuse" idea -- no function returning distinct values for N different inputs on a fixed-width register machine can execute in less than log(N) time, and I probably should have just stopped there and called it a day.