Bitwise range AND/OR with no updates in O(n) preprocessing and O(1) time per query

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

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)

Solution with iterated Four Russians

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?

History