mango_lassi's blog

Bitwise range AND/OR with no updates in O(n) preprocessing and O(1) time per query
By mango_lassi, history, 4 years ago, In English

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?

  • Vote: I like it
  • +79
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +41 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Attaching blog on sqrt Tree for reference.

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

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

https://codeforces.net/blog/entry/78931

Edit: nvm

→ Reply