How to compute bitwise-or on the segment fast?

Question

Given a list of integers.

I wonder if it is possible to calculate bitwise OR on the segment for O(1) per query and O(n) of the premise? (Some prefix sums) (it is Easy to do this for O(log n) per query and O(n log n) of the premise, for example, using the segment tree, but what is faster?)

Answer 1

Yes, it is possible. Just build a prefix-sum-like array for each bit position and fill it with a running total of bits set from the start of your data. The initial value for each counter would be zero: counter[0][b]=0, and the n-th counter would store a number of bits set in data items 0 through n-1.

Then you can test if the bit no b is set anywhere in the given range [m,n] just by testing if b-th counters on both ends of the range differ (counter[n+1][b] not.eq. counter[m][b]).

Finally compose an answer bit by bit from results of all (8, 16, 32...) bit positions.

Be aware this solution requires an additional integer per each bit of original data, which means you need e.g. 32 times more memory if your int is 32 bits wide.