Hello Everyone,

I hope you have gone through the “Sparse Table” before coming here. It’s really advisable to completely read part 1, then only continue with part 2.

Link: Sparse Table

Now,

**Example Problem 2 : Range GCD Query**

We have an array arr[0 . . . n-1]. We need to find the greatest common divisor in the range L and R where 0 <= L <= R <= n-1. Consider a situation when there are many range queries

Examples:

Input : arr[] = {2, 3, 5, 4, 6, 8} queries[] = {(0, 2), (3, 5), (2, 3)} Output : 1 2 1

**We use below properties of GCD:**

- GCD function is associative [ GCD(a, b, c) = GCD(GCD(a, b), c) = GCD(a, GCD(b, c))], we can compute GCD of a range using GCDs of subranges.
- If we take GCD of an overlapping range more than once, then it does not change answer. For example GCD(a, b, c) = GCD(GCD(a, b), GCD(b, c)). Therefore like minimum range query problem, we need to do only one comparison to find GCD of given range.

We build a sparse table using the same logic as above. After building the sparse table, we can find all GCDs by breaking given range in powers of 2 and add GCD of every piece to the current answer.

`// C++ program to do range minimum query`

`// using sparse table`

`#include <bits/stdc++.h>`

`using`

`namespace`

`std;`

`#define MAX 500`

`// 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.`

`int`

`table[MAX][MAX];`

`// it builds sparse table.`

`void`

`buildSparseTable(`

`int`

`arr[], `

`int`

`n)`

`{`

` `

`// GCD of single element is element itself`

` `

`for`

`(`

`int`

`i = 0; i < n; i++)`

` `

`table[i][0] = arr[i];`

` `

`// Build sparse table`

` `

`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]);`

`}`

`// Returns GCD of arr[L..R]`

`int`

`query(`

`int`

`L, `

`int`

`R)`

`{`

` `

`// Find highest power of 2 that is smaller`

` `

`// than or equal to count of elements in given`

` `

`// range.For [2, 10], j = 3`

` `

`int`

`j = (`

`int`

`)log2(R - L + 1);`

` `

`// 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]],`

` `

`return`

`__gcd(table[L][j], table[R - (1 << j) + 1][j]);`

`}`

`// Driver program`

`int`

`main()`

`{`

` `

`int`

`a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };`

` `

`int`

`n = `

`sizeof`

`(a) / `

`sizeof`

`(a[0]);`

` `

`buildSparseTable(a, n);`

` `

`cout << query(0, 2) << endl;`

` `

`cout << query(1, 3) << endl;`

` `

`cout << query(4, 5) << endl;`

` `

`return`

`0;`

`}`

**Output**

1

1

5