text: Sparse Table | C # program to do range minimum query using sparse table ; lookup [ i , j ] is going to store GCD of arr [ i . . j ] . Ideally lookup table size should not be fixed and should be determined using n Log n . It is kept constant to keep code simple . ; it builds sparse table . ; GCD of single element is element itself ; Build sparse table ; Returns GCD of arr [ L . . R ] ; Find highest power of 2 that is smaller than or equal to count of elements in given range . For [ 2 , 10 ] , j = 3 ; Compute GCD of last 2 ^ j elements with first 2 ^ j elements in range . For [ 2 , 10 ] , we find GCD of arr [ lookup [ 0 , 3 ] ] and arr [ lookup [ 3 , 3 ] ] , ; Driver Code
code: using System ; class GFG { static readonly int MAX = 500 ; static int [ , ] table = new int [ MAX , MAX ] ; static void buildSparseTable ( int [ ] arr , int n ) { for ( int i = 0 ; i < n ; i ++ ) table [ i , 0 ] = arr [ i ] ; for ( int j = 1 ; j <= n ; j ++ ) for ( int i = 0 ; i <= n - ( 1 << j ) ; i ++ ) table [ i , j ] = __gcd ( table [ i , j - 1 ] , table [ i + ( 1 << ( j - 1 ) ) , j - 1 ] ) ; } static int query ( int L , int R ) { int j = ( int ) Math . Log ( R - L + 1 ) ; return __gcd ( table [ L , j ] , table [ R - ( 1 << j ) + 1 , j ] ) ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void Main ( String [ ] args ) { int [ ] a = { 7 , 2 , 3 , 0 , 5 , 10 , 3 , 12 , 18 } ; int n = a . Length ; buildSparseTable ( a , n ) ; Console . Write ( query ( 0 , 2 ) + " STRNEWLINE " ) ; Console . Write ( query ( 1 , 3 ) + " STRNEWLINE " ) ; Console . Write ( query ( 4 , 5 ) + " STRNEWLINE " ) ; } }