Given an array of N integer. Calculate how many contiguos sub-array that have the OR-sum larger or equal to K.
For each position i we will find the smallest j ≥ i such that the OR-sum of A[i…j] larger than or equal to K then we would know that there is N - j + 1 valid sub-array starting at i. Notice that with i fixed OR-sum of A[i…j] increses when j increases (OR-sum increases when we add more numbers). With that we can use binary search with each i to find j If we can calculate OR-sum of A[i…j] efficiently (one way to calculate OR-sum of any A[i…j] is building the segment tree).
The mentioned solution seems to be overkill with this easy problem not to say that it doesn’t give the best run time. We can avoid binary search and use the two pointer technique where one pointer is the position of i and the other one is j. With each i we try to increase j until we got the OR-sum of A[i…j] larger than or equal to K. The OR-sum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the sub-array A[i…j]. Basically we maintain an array cnt[0…31] where cnt* is the the numbers of numbers in A[i…j] that hava 1 at the ith bit.
All we do is increase i or j, update the cnt array and calculate the OR-sum. Update the cnt or calculate OR-sum from cnt both take O(32) (which is corresponding to the number of bits the max value of A*). So the total complexity would be O(N×log(max A*)).