Range LCM Queries

Intuition

A segment tree is perfect for range queries and point updates when the operation is associative. LCM is associative, so merging LCM(left) and LCM(right) at parent nodes builds the tree correctly. Neutral element for LCM is 1; returning 1 for out-of-range queries ensures correctness.

Algorithm

1Build phase: recursively fill tree bottom-up. Leaf nodes = array elements. Internal nodes = LCM of two children.
2Query phase: if range is outside [l,r], return 1. If inside [ql,qr], return tree[idx]. Otherwise, split and merge child LCMs.
3Update phase: find the leaf position, set its value, then propagate LCM changes up to root.

Example Walkthrough

Input: arr = [4, 6, 8], queries = [[2, 1, 2], [1, 0, 2], [2, 0, 2]]

1.Build tree: leaves = 4, 6, 8. parent(4,6)=LCM(4,6)=12. parent(12,8)=LCM(12,8)=24.
2.Query [2, 1, 2]: ask LCM of range [1,2] = LCM(6,8) = 24.
3.Update [1, 0, 2]: set arr[0]=2. Update tree: leaf=2, parent(2,6)=6, parent(6,8)=24.
4.Query [2, 0, 2]: ask LCM of range [0,2] with arr=[2,6,8] → LCM=24.

Output: [24, 24]

Common Pitfalls

•Returning 1 for out-of-range queries (neutral element for LCM) is essential; 0 would wrongly zero out all results.
•After update, make sure to propagate the change up the tree, not just update the leaf.
•Index mapping: segment tree uses 1-based indexing for simplicity; be consistent with 0-based array and 1-based tree indices.

Range LCM Queries.java

Java


import java.util.*;

// Approach: Segment tree where each node stores the LCM of its range.
// Build tree bottom-up: leaf = array element, internal node = LCM of children.
// Point update: modify leaf and propagate LCM up to root.
// Range query: recursively merge LCMs of overlapping child ranges; 1 is neutral element.
// Time: O(n) build, O(log n) update/query Space: O(n)

class Solution {

    public ArrayList<Long> RangeLCMQuery(int[] arr, int[][] queries) {
        SegmentTree st = new SegmentTree(arr);
        ArrayList<Long> result = new ArrayList<>();

        for (int[] q : queries) {
            if (q[0] == 1) {
                // Update query
                st.update(q[1], q[2], 0, arr.length - 1, 1);
            } else {
                // Range query
                result.add(st.query(q[1], q[2], 0, arr.length - 1, 1));
            }
        }
        return result;
    }
}

class SegmentTree {

    int n;
    long[] tree;

    SegmentTree(int[] arr) {
        n = arr.length;
        tree = new long[4 * n];
        build(arr, 0, n - 1, 1);
    }

    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) {
            return Math.max(a, b);
        }
        return (a / gcd(a, b)) * b;
    }

    private void build(int[] arr, int l, int r, int idx) {
        if (l == r) {
            tree[idx] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(arr, l, mid, 2 * idx);
        build(arr, mid + 1, r, 2 * idx + 1);
        tree[idx] = lcm(tree[2 * idx], tree[2 * idx + 1]);
    }

    public void update(int pos, int val, int l, int r, int idx) {
        if (l == r) {
            tree[idx] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(pos, val, l, mid, 2 * idx);
        } else {
            update(pos, val, mid + 1, r, 2 * idx + 1);
        }
        tree[idx] = lcm(tree[2 * idx], tree[2 * idx + 1]);
    }

    public long query(int ql, int qr, int l, int r, int idx) {
        if (qr < l || ql > r) {
            return 1; // neutral element for LCM

        }
        if (ql <= l && r <= qr) {
            return tree[idx];
        }
        int mid = (l + r) / 2;
        long left = query(ql, qr, l, mid, 2 * idx);
        long right = query(ql, qr, mid + 1, r, 2 * idx + 1);
        return lcm(left, right);
    }
}

Was this solution helpful?