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;
}
}
Understanding the Build Operation
The build() method recursively divides the array.
For:
[2, 3, 4, 6, 8, 16]
the first range is:
[0...5]
It is divided into:
[0...2]
[3...5]
Then these ranges are divided again.
Eventually, every individual element becomes a leaf node.
For example:
[2, 3]
has:
GCD(2, 3) = 1
and:
[8, 16]
has:
GCD(8, 16) = 8
The parent node stores:
GCD(1, 8) = 1
Understanding Range Query
The query function handles three cases.
Case 1: No Overlap
Suppose the requested range is:
[2, 5]
and the current tree node represents:
[0, 1]
There is no overlap.
Therefore:
return 0;
Why 0?
Because:
GCD(x, 0) = x
So 0 works as the identity value for GCD.
Case 2: Complete Overlap
If the current segment is completely inside the requested range, we don't need to go deeper.
For example:
Requested range = [2, 5]
Current segment = [3, 4]
Since:
[3, 4] ⊆ [2, 5]
we directly return:
tree[node]
This is one of the main reasons Segment Trees are efficient.
Case 3: Partial Overlap
If the current segment partially overlaps the query range, we divide it into two parts.
int leftGCD = queryGCD(...);
int rightGCD = queryGCD(...);
return gcd(leftGCD, rightGCD);
The final answer is:
GCD(left part, right part)
Understanding Point Update
Consider:
arr = [2, 3, 4, 6, 8, 16]
Update:
[1, 3, 8]
means:
arr[3] = 8
The array becomes:
[2, 3, 4, 8, 8, 16]
The Segment Tree does not need to be rebuilt completely.
It follows the path from the root to index 3.
Only the affected nodes are recalculated.
This makes the update:
O(log n)
instead of:
O(n)
Dry Run
Consider:
arr = [2, 3, 4, 6, 8, 16]
queries =
[
[0, 0, 2],
[1, 3, 8],
[0, 2, 5]
]
Query 1
[0, 0, 2]
Type 0 means range GCD.
Range:
[2, 3, 4]
Therefore:
GCD(2, 3) = 1
GCD(1, 4) = 1
Answer:
1
Query 2
[1, 3, 8]
Type 1 means update.
So:
arr[3] = 8
New array:
[2, 3, 4, 8, 8, 16]
Query 3
[0, 2, 5]
Range:
[4, 8, 8, 16]
Calculate:
GCD(4, 8) = 4
GCD(8, 16) = 8
GCD(4, 8) = 4
Answer:
4
Therefore the final result is:
[1, 4]
Why Do We Return 0 for No Overlap?
This is an important concept in Segment Tree problems.
For GCD:
GCD(x, 0) = x
Therefore, 0 behaves as the identity element.
For example:
GCD(12, 0) = 12
So when one side of the query has no overlap:
return 0;
does not affect the final GCD.
For example:
leftGCD = 6
rightGCD = 0
GCD(6, 0) = 6
Complexity Analysis
Let:
n = number of array elements
q = number of queries
M = maximum element value
Building the Segment Tree
The tree contains approximately 4n nodes.
The construction takes:
O(n)
with each merge requiring a GCD calculation.
Since GCD takes:
O(log M)
the bound can be expressed as:
O(n log M)
Range Query
A Segment Tree visits O(log n) relevant tree levels/nodes, with GCD calculations costing O(log M).
Therefore:
O(log n × log M)
Update
A point update travels from the root to one leaf:
O(log n)
with GCD recalculation:
O(log n × log M)
Overall
For q queries:
O((n + q) × log n × log M)
Space
The Segment Tree uses:
O(n)
space.
Important Concepts to Remember
When solving similar problems, remember these points:
1. Range Query + Point Update
This combination is a strong indication that a Segment Tree may be useful.
2. GCD is Associative
GCD satisfies:
GCD(a, GCD(b, c))
=
GCD(GCD(a, b), c)
Therefore, we can safely combine the results from different Segment Tree nodes.
3. Identity Element
For GCD:
identity = 0
because:
GCD(x, 0) = x
4. 0-Based Indexing
The problem uses:
0 <= index < n
so no conversion is required.
5. Point Update
Only one path in the Segment Tree needs to be updated.
Conclusion
The Range GCD Queries problem is a classic application of the Segment Tree data structure.
A brute-force solution can become too slow when both n and q are as large as 10^5.
The Segment Tree solves this efficiently by:
Storing GCD values for different ranges.
Answering range queries without visiting every element.
Updating only the affected path after a value changes.
Using the Euclidean Algorithm to calculate GCD efficiently.
The key pattern to remember is:
Range Query + Point Update
↓
Segment Tree
↓
GCD as merge operation
This same Segment Tree idea can also be adapted for problems involving range minimum, range maximum, range sum, LCM, and other associative operations.
Join the conversation! Your thoughts help the community grow.