Range GCD Queries

Problem Overview

Each query either replaces one array value or asks for the GCD of a contiguous segment.

Intuition

Each query either replaces one array value or asks for the GCD of a contiguous segment. A segment tree keeps the GCD of every half of the array, so a point change touches only the nodes above that index and a range read merges a few of those nodes. The GCD of a number with 0 is the number itself, which makes 0 a safe empty result. The moment a running GCD becomes 1, the rest of the range cannot change it.

Algorithm

1Place the array in the leaves of a tree of size 2n and fill every parent with the GCD of its two children.
2On an update, write the new value into the leaf. Walk toward the root and stop when a parent GCD stays the same, because every ancestor above it stays the same too.
3On a range query, cover the inclusive segment with a logarithmic number of nodes and combine their GCDs.
4If the running GCD becomes 1, return 1 immediately.
5Append each query answer and return the list.

Example Walkthrough

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

1. The GCD of the whole array is 2.
2. Index 2 changes from 6 to 9, so the array is 2, 4, 9, 8.
3. The GCD from index 1 through 3 is 1.
4. The GCD of the first two values is still 2.

Output: [2, 1, 2]

Common Pitfalls

• A prefix structure can keep sums because subtraction reverses them. GCD has no such inverse, so a range that is not a prefix needs a segment tree.
• Query type 0 reads a range. Query type 1 writes one index.
• The query bounds are inclusive. A half open loop must add one to the right end before it starts.
• An update that does not change a parent GCD can stop. Ancestors above an unchanged node cannot change either.

Range GCD Queries.java

Java

// Approach: A segment tree stores the GCD of every range. Point updates
// recompute only the ancestors whose GCD actually changes. A range read
// merges O(log n) nodes and stops as soon as the running GCD becomes 1.
// Complexity: O(n + q log n) time, O(n) extra space.
import java.util.ArrayList;

class Solution {
    public ArrayList<Integer> processQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] tree = new int[n << 1];
        for (int i = 0; i < n; i++)
            tree[n + i] = arr[i];
        for (int i = n - 1; i > 0; i--)
            tree[i] = gcd(tree[i << 1], tree[i << 1 | 1]);

        ArrayList<Integer> ans = new ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 0)
                ans.add(query(tree, n, q[1], q[2]));
            else
                update(tree, n, q[1], q[2]);
        }
        return ans;
    }

    private void update(int[] tree, int n, int index, int value) {
        int i = n + index;
        if (tree[i] == value)
            return;
        tree[i] = value;
        for (i >>= 1; i > 0; i >>= 1) {
            int next = gcd(tree[i << 1], tree[i << 1 | 1]);
            if (tree[i] == next)
                return;
            tree[i] = next;
        }
    }

    // Inclusive [l, r]. 0 is the GCD identity, so an empty side does not change the result.
    private int query(int[] tree, int n, int l, int r) {
        int res = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if ((l & 1) == 1) {
                res = gcd(res, tree[l++]);
                if (res == 1)
                    return 1;
            }
            if ((r & 1) == 1) {
                res = gcd(res, tree[--r]);
                if (res == 1)
                    return 1;
            }
        }
        return res;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

Was this solution helpful?