There is no need to walk a superblock because they all have the same structure. You can pre-compute offests, similarly to what you would do to access a field within an array of structs.
Also, at the cost of sounding like the CS equivalent of flat earthers, big-O notation is kind of broken, and specifically, it doesn't make a lot of sense to say that something is O(1). Even hashmap queries, if you think about it, can't really be O(1) for arbirarily large values of N.
The general interpretation of O(1) in theoretical CS literature is "we know it's bugged, but we promise we won't bugabuse".
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.
You can make a model where the presented algorithm runs in O(1) time, for example a transdichotomous model. However those models have very unintuitive consequences (for example, the O(n log n) bound for sorting doesn't hold any longer!), which is what I was hinting to with my "big O is broken" remark.
You are absolutely right that it can't be done on a fixed-width register machine, though.
Generally speaking, most papers assume arithmetic is O(1) time and integers fit in O(1) space because keeping track of the actual time and space of integer arithmetic gets unwieldy very quickly. But this model is super broken: if arbitrary arithmetic can be performed in O(1) then P = PSPACE. The "gentlemen's agreement" assumption is that operations that make numbers grow too big are forbidden.
I don't know much about this stuff (I'm way out of my depth as a matter of fact), but I'm glad I could be useful :)
Also, at the cost of sounding like the CS equivalent of flat earthers, big-O notation is kind of broken, and specifically, it doesn't make a lot of sense to say that something is O(1). Even hashmap queries, if you think about it, can't really be O(1) for arbirarily large values of N.
The general interpretation of O(1) in theoretical CS literature is "we know it's bugged, but we promise we won't bugabuse".