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?

Divide into $$$\sqrt N$$$ blocks, compute AND/OR on each prefix and suffix of each block and compute AND/OR on each range of blocks as $$$dp[i][j]$$$. That gives us $$$O(N)$$$ preprocessing and $$$O(1)$$$ query with $$$O(N)$$$ total memory.

How do you answer a query fully contained in a block?

Good question :) Well, repeat that 3 times :)

(Iterative square root times)

Upd: Ok, box is right, it's $$$O(n \log \log n)$$$ preprocessing and memory.

What about queries that fit entirely in one block?

edit: sniped, to contribute something semi-useful:

Another, slightly worse in complexity but usable in practice, is to iterate MrDindows's solution on each block. Afaik this data structure is know as a "square root tree" and it's possible to accomplish $$$O(n\log\log n)$$$ preprocessing $$$O(1)$$$ queries with such a method.

Attaching blog on sqrt Tree for reference.

As mentioned, it can also handle updates in $$$O(\sqrt N)$$$ time if needed.

https://mirror.codeforces.com/blog/entry/78931

Edit: nvm