There was a blog on this topic that I was about to comment on, but it seems that it got deleted :(

It was asking for a solution in $$$\mathcal{O}(n)$$$ preprocessing and $$$\mathcal{O}(1)$$$ query time. There are no updates. We make the standard assumptions that input integers have $$$\mathcal{O}(\log n)$$$ bits and operations on $$$\mathcal{O}(\log n)$$$-bit integers take $$$\mathcal{O}(1)$$$ time.

The obvious solutions to range AND and range OR are to

• Count the number of times every bit appears in every prefix ($$$\mathcal{O}(n \log n)$$$ preprocessing and $$$\mathcal{O}(\log n)$$$ query time)
• Use a interval AND / OR segment tree ($$$\mathcal{O}(n)$$$ preprocessing and $$$\mathcal{O}(\log n)$$$ query time)
• Use a sparse table ($$$\mathcal{O}(n \log n)$$$ preprocessing and $$$\mathcal{O}(1)$$$ query time).

Four Russians is a standard trick to achieve $$$\mathcal{O}(n)$$$ preprocessing and $$$\mathcal{O}(1)$$$ query time. However, I don't see how it can be used here to achieve that: while we can solve all queries of length $$$\Omega(\log n)$$$ in $$$\mathcal{O}(1)$$$ time with $$$\mathcal{O}(n)$$$ preprocessing, it is not clear how to solve queries entirely inside a single block. This is because each block contains $$$\mathcal{O}(\log^2 n)$$$ bits that matter, not $$$\mathcal{O}(\log n)$$$ as is the case for the cartesian tree of the block, when computing interval minimum.

So the best complexity I could come up with is based on iterating the Four Russians trick, which achieves either

• $$$\mathcal{O}(n \log^* n)$$$ precalc and $$$\mathcal{O}(1)$$$ time per query (where $$$\log^* n$$$ is the iterated logarithm)
• $$$\mathcal{O}(n)$$$ precalc and $$$\mathcal{O}(\log \log \dots \log n)$$$ time per query (taking logarithm any fixed number of times)

This is pretty good (theoretically, of course this is pointless to do in practice), but is there some way to get $$$\mathcal{O}(n)$$$ preprocessing and $$$\mathcal{O}(1)$$$ query time? Is there even a solution that uses $$$\mathcal{O}(n)$$$ space and has $$$\mathcal{O}(1)$$$ queries?