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