GFG POTD: Range LCM Queries | Segment-Tree (Java) | 12 May 2026

Welcome to today's explanation of the GFG POTD (Problem of the Day)! In this video, I break down the strategies, ideas, and core concepts you need to solve the "Range LCM Queries" problem. Understanding Segment Trees and how to efficiently combine mathematical properties like LCM and GCD over ranges will massively boost your overall problem-solving skills and help you build the solid foundation needed to tackle complex, query-based competitive programming questions next time. If you found this video helpful, please show your gratitude by liking the video, and don't forget to subscribe to the channel for more daily coding content. Happy coding! Problem Name: Range LCM Queries Difficulty: Medium Platform: GeeksforGeeks Question: Given an array and a list of sequential queries, handle two types of operations: update an element at a specific index to a new value, or compute the Least Common Multiple (LCM) of all elements in a given subarray from index L to R The Approach (Segment Trees & Number Theory) 1.Understand the Core Data Structure: Calculating the LCM manually using simple array traversal for every range query is computationally too slow O(N) per query), leading to Time Limit Exceeded (TLE) errors. Instead, the most elegant way to solve this is using a Segment Tree, which gives us a massive performance boost by breaking the array into manageable, pre-computed chunks. 2. Build the Segment Tree: First, allocate a tree array of size $4 \times N$. Using a recursive approach, each leaf node is assigned the value of a single array element. Every parent node will then store the LCM of its left and right children. To calculate this without overflow, we use the mathematical relationship: LCM (a, b) = (a / gcd(a, b)) * b 3. Process Range Queries (Type 2): When asked for the LCM from index L to R, we traverse the tree. If a node's range is completely outside our query, we return 1(since 1 doesn't affect an LCM operation). If the node is completely inside the query range, we directly return its pre-calculated value. Otherwise, we partially query both children and return the LCM of their results. 4.Process Point Updates (Type 1): To update a value, we recursively traverse down to the specific leaf node representing that index and change its value. As the recursive calls return (backtracking), we recalculate the LCM for every parent node going all the way back up to the root. This guarantees our tree always reflects the current state of the array. Complexity: Time Complexity: Building the Tree: O(N log(MAX\_VAL)) where N is the number of elements. Processing Queries : O(Q log N log(MAX\_VAL)) where Q is the number of queries. Fetching ranges and updating nodes takes O(log N) time, and each step computes the GCD/LCM which takes logarithmic time relative to the values. Given the 10^5 constraints, this logarithmic approach runs extremely fast! Space Complexity: O(N) to store the Segment Tree array (which takes up 4 times N space) and the recursive call stack overhead. Solution Code: https://github.com/Arnab-Pachal1234/GFG-POTD-SOLUTION #gfg #dsa #segmenttree #lcm #numbertheory #coding #problemoftheday #java #mediumquestion #competitiveprogramming #datastructures #math