use segment tree

You can do it with a segment tree, but it's easier to do a prefix sum on each bit (i.e. at index i the prefix sum for each bit will be how many elements up until position i have that bit on).

This way you can check for each bit how many values have it in the interval, if it's all elements it will be 1 in your &. It takes 32 O(1) operations to reconstruct the answer in a query, and 32 O(n) operations to build the prefix sum. This is enough for this problem. Note that this value of 32 equals ceil(log2(maximum value in array)).

If you find it hard to visualize how this works, imagine you only have single-bit elements (i.e., all elements are either 0 or 1).

you can use an segment tree ( you can see my implementation ) , or you can use rmq , some guys used prefix sum to compute the AND on subbarays

Let’s break this down: every number can be thought of as 64 bits, right?

Now what exactly does AND mean? AND means that every single bit should be equal to 1 for the result to be 1, otherwise the result will be 0. Let’s say we had some number of bits: the result would be 1 if all of those bits were equal to 1, otherwise 0. See where I’m going with this?

If we have n bits stored in an array b[], then the AND will be 1 if sum[b[0]…b[n]] is equal to n.

I’m sure you’re already familiar with the concept of prefix sums, if not then read up about it on USACO guide, or wherever you want to. I think Errichto has a good video on it as well. Anyway, you can do this for all 30 bits (log2(10^9) > 29, 10^9 is the maximum number size) to get the bitwise AND of a range efficiently. Hope you understood :)

you can do o(1) query and o(nlogn) construction rmq , I heard that there is also a o(n) construction but I dont know much about it , you can see it in here