piggy123's blog

A problem on array bitwise-OR sums
By piggy123, history, 18 months ago, In English

We have an array of integers $$$a_{1...n}$$$, and we have $$$q$$$ updates where we change one of the elements of it. After each update, we need to output the bitwise-OR sum of the entire array. Could this be done(offline) in linear time?

Consider the bitwise operations on integers to be $$$O(1)$$$.

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

»
18 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

I think this can be dine in O(1) per query by keeping track of number of numbers that turn bit k on for all 30-something bits. If there number of numbers with bit k > 0, then the bitwise or must turn bit k on as well.

Thus creating a 30*n = O(n) solution.

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    probably not what you are looking for.

    → Reply
    • »
      »
      »
      18 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thanks, but you are right in saying that this is not what i'm looking for :(

      Getting rid of the $$$\log V$$$ in the complexity where $$$V$$$ is the range of the values is what I'm seeking to achieve here.

      → Reply
      • »
        »
        »
        »
        18 months ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        If you dont consider bitwise operations O(1), then it should be impossible to do this faster than O(nlogn), since even computing the bitwise or of all inputs initially will be O(nlogn)

        → Reply
»
18 months ago, hide # |
 
Vote: I like it -23 Vote: I do not like it

Its not easy to make constant factor of $$$O(1)$$$ solution (if it exists) significantly faster than $$$O(\log V)$$$

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This is kinda similar to what I wondered about recently: https://codeforces.me/blog/entry/138297

No one knew how to do that :(

→ Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it +32 Vote: I do not like it

This is not a solution, but is something I thought about and made me not conclude that this task is immediately impossible.

Consider replacing each element with a random submask (each bit taken away with 1/2, easily done in O(1), assuming you can generate a random number in O(1)), and replace the OR with a XOR. This now gives an O(n) solution where every '1' bit is defintiely a '1', and every '0' have 1/2 chance to be actually a '1'.

If you repeat the above enough times, then you can gurantee the answers are correct with high probability. Unfortunately, you need to repeat it $$$c \log n \log \log n$$$ times here.

But if you are for some reason working with $$$a_i$$$ lower than the allowed range of bitwise operations to be O(1), say if $$$a_i\leq 32$$$, then you can simultaneously do the above operation using the same 64-bit integers packing multiple copies of $$$a_i$$$. This means that the $$$n log n log log n$$$ can improved if not all bits are not utilised.

Again, this is not a solution and may not be useful, but it could be interesting.

→ Reply