Introduction
The Range GCD Queries problem involves performing two different operations on an integer array:
Find the GCD (Greatest Common Divisor) of all elements in a given range.
Update a particular element of the array with a new value.
For example, consider:
arr = [2, 3, 4, 6, 8, 16]If we have the query:
[0, 0, 2]it means we need to find the GCD of:
[2, 3, 4]The answer is:
GCD(2, 3, 4) = 1Another query:
[1, 3, 8]means:
arr[3] = 8
The array becomes:
[2, 3, 4, 8, 8, 16]
When the array size and number of queries can both be as large as 10^5, checking every element for every query would be too slow. Therefore, we use a Segment Tree.
What is GCD?
GCD stands for Greatest Common Divisor.
It is the largest number that divides two or more numbers without leaving a remainder.
For example:
GCD(12, 18) = 6
because:
12 = 6 × 2
18 = 6 × 3
The GCD can be efficiently calculated using the Euclidean Algorithm.
Euclidean Algorithm
The basic rule is:
GCD(a, b) = GCD(b, a % b)
For example:
GCD(18, 12)
18 % 12 = 6
12 % 6 = 0
Answer = 6
In Java:
private int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
Why Do We Need a Segment Tree?
Suppose:
n = 100000
q = 100000
A simple approach would calculate the GCD by traversing every element in the requested range.
For example:
Query: GCD(0, 99999)
This could require O(n) operations.
If there are 100000 queries, the worst-case complexity becomes approximately:
O(n × q)
which is too slow.
A Segment Tree allows us to process range queries efficiently.
With a Segment Tree:
Range GCD Query →
O(log n)Point Update →
O(log n)
Each GCD calculation itself takes O(log(maxElement)).
Therefore, the expected complexity is:
O((n + q) × log n × log(maxElement))
Segment Tree Concept
A Segment Tree divides the array into smaller ranges.
Consider:
arr = [2, 3, 4, 6, 8, 16]
The tree represents ranges such as:
[0...5]
/ \
[0...2] [3...5]
/ \ / \
[0...1] [2] [3...4] [5]
/ \ / \
[0] [1] [3] [4]
Each node stores the GCD of its range.
For example:
GCD(2, 3) = 1
GCD(4) = 4
Therefore:
GCD(0...2) = GCD(1, 4) = 1
Structure of the Solution
We use three main operations:
1. build()
2. queryGCD()
3. update()
1. build()
Builds the Segment Tree from the original array.
2. queryGCD()
Finds the GCD of a requested range.
3. update()
Updates one array element and recalculates the affected Segment Tree nodes.
Complete Java 21 Solution
import java.util.*;
class Solution {
int[] tree;
int n;
public ArrayList<Integer> processQueries(int[] arr, int[][] queries) {
n = arr.length;
// Segment Tree requires approximately 4*n space
tree = new int[4 * n];
// Build the tree
build(arr, 1, 0, n - 1);
ArrayList<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int type = query[0];
// Type 0 -> Range GCD Query
if (type == 0) {
int l = query[1];
int r = query[2];
result.add(
queryGCD(1, 0, n - 1, l, r)
);
}
// Type 1 -> Update
else {
int index = query[1];
int value = query[2];
update(
1,
0,
n - 1,
index,
value
);
}
}
return result;
}
// Build Segment Tree
private void build(
int[] arr,
int node,
int start,
int end
) {
// Leaf node
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = start + (end - start) / 2;
// Build left subtree
build(
arr,
2 * node,
start,
mid
);
// Build right subtree
build(
arr,
2 * node + 1,
mid + 1,
end
);
// Store GCD of both children
tree[node] = gcd(
tree[2 * node],
tree[2 * node + 1]
);
}
// Range GCD Query
private int queryGCD(
int node,
int start,
int end,
int l,
int r
) {
// No overlap
if (r < start || end < l) {
return 0;
}
// Complete overlap
if (l <= start && end <= r) {
return tree[node];
}
int mid = start + (end - start) / 2;
int leftGCD = queryGCD(
2 * node,
start,
mid,
l,
r
);
int rightGCD = queryGCD(
2 * node + 1,
mid + 1,
end,
l,
r
);
return gcd(leftGCD, rightGCD);
}
// Point Update
private void update(
int node,
int start,
int end,
int index,
int value
) {
// Reached the required index
if (start == end) {
tree[node] = value;
return;
}
int mid = start + (end - start) / 2;
// Search in left subtree
if (index <= mid) {
update(
2 * node,
start,
mid,
index,
value
);
}
// Search in right subtree
else {
update(
2 * node + 1,
mid + 1,
end,
index,
value
);
}
// Recalculate current node
tree[node] = gcd(
tree[2 * node],
tree[2 * node + 1]
);
}
// Euclidean Algorithm
private int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}

Join the conversation! Your thoughts help the community grow.