Queries for bitwise OR in the index range [ L , R ] of the given array | C # implementation of the approach ; Array to store bit - wise prefix count ; Function to find the prefix sum ; Loop for each bit ; Loop to find prefix count ; Function to answer query ; To store the answer ; Loop for each bit ; To store the number of variables with ith bit set ; Condition for ith bit of answer to be set ; Driver code
using System ; class GFG { static int MAX = 100000 ; static int bitscount = 32 ; static int [ , ] prefix_count = new int [ bitscount , MAX ] ; static void findPrefixCount ( int [ ] arr , int n ) { for ( int i = 0 ; i < bitscount ; i ++ ) { prefix_count [ i , 0 ] = ( ( arr [ 0 ] >> i ) & 1 ) ; for ( int j = 1 ; j < n ; j ++ ) { prefix_count [ i , j ] = ( ( arr [ j ] >> i ) & 1 ) ; prefix_count [ i , j ] += prefix_count [ i , j - 1 ] ; } } } static int rangeOr ( int l , int r ) { int ans = 0 ; for ( int i = 0 ; i < bitscount ; i ++ ) { int x ; if ( l == 0 ) x = prefix_count [ i , r ] ; else x = prefix_count [ i , r ] - prefix_count [ i , l - 1 ] ; if ( x != 0 ) ans = ( ans | ( 1 << i ) ) ; } return ans ; } public static void Main ( String [ ] args ) { int [ ] arr = { 7 , 5 , 3 , 5 , 2 , 3 } ; int n = arr . Length ; findPrefixCount ( arr , n ) ; int [ , ] queries = { { 1 , 3 } , { 4 , 5 } } ; int q = queries . GetLength ( 0 ) ; for ( int i = 0 ; i < q ; i ++ ) Console . WriteLine ( rangeOr ( queries [ i , 0 ] , queries [ i , 1 ] ) ) ; } }