Range GCD and why it is not invertible

Why this matters

A range GCD query asks for the greatest common divisor of the values between two positions. The greatest common divisor, or GCD, of two whole numbers is the largest whole number that divides both of them exactly. For example, 6 divides both 12 and 18, and no larger number does, so the GCD of 12 and 18 is 6.

Range GCD comes up when a group of numbers may share a common factor. One example is putting a range of fractions over one denominator. Another is checking whether all the measurements in a range are multiples of the same unit. The simple method is to loop over the range and take the GCD of the values one at a time. That is correct, but its time grows with the length of the range.

This lesson builds a segment tree for GCD. A segment tree is an array of stored answers for blocks of the input, arranged as a binary tree, so a query combines only a few stored answers. The tree is explained from scratch below, so you do not need an earlier lesson to follow it.

The lesson also answers a different question: why the trick used for range sums does not carry over. For a sum you can often find the answer for a range by subtracting two totals. That subtraction is called undo. For GCD the undo trick fails, and the reasons are shown with numbers you can run.

The GCD, one step at a time

Start with two small numbers, 12 and 18. List the numbers that divide 12: 1, 2, 3, 4, 6 and 12. List the numbers that divide 18: 1, 2, 3, 6, 9 and 18. The numbers in both lists are 1, 2, 3 and 6. The largest is 6, so the GCD is 6.

Listing divisors is slow for large numbers. The Euclid method is faster. It uses the remainder, written % in C++, which is what is left over after division. The remainder of 48 divided by 18 is 12, because 48 is 2 groups of 18 with 12 left over. Replace the pair (48, 18) with the pair (18, 12). The remainder of 18 divided by 12 is 6, so the pair becomes (12, 6). The remainder of 12 divided by 6 is 0. When the remainder reaches 0, the other number is the GCD, which is 6.

You do not have to write this method yourself. C++ has std::gcd, which is in the <numeric> header and has been part of the standard library since C++17. You call it with two integers, as in std::gcd(12, 18), and it returns 6.

Three facts about GCD matter for the rest of this lesson.

1. Zero is an identity for GCD. The GCD of x and 0 is x, and the GCD of 0 and x is x. Combining with 0 changes nothing. This is why an empty range can return 0 in the code.
2. The order does not matter. The GCD of 12 and 18 is the same as the GCD of 18 and 12.
3. The grouping does not matter. The GCD of three numbers is the same whether you combine the first two first or the last two first. A tree can therefore combine pieces in any grouping and still get the right answer.

A range GCD as a tree of pieces

Take the array 12 18 8 30 45 9. Positions run from 0 to 5. A query for positions 1 to 3 covers the values 18, 8 and 30. Their GCD is 2. The goal is to get that answer without looking at every value in the range each time.

A segment tree stores the GCD of blocks of the array. The bottom row holds the array values, one per position. Each parent holds the GCD of its two children. Each parent above that holds the GCD of its two children, and so on, up to a top node that holds the GCD of the whole array. To answer a query, the code picks the few stored blocks that exactly cover the range and combines their GCDs. A range of any length needs only a few such blocks.

The code stores the tree in one array called t. Use the following layout, which is the one the program below uses. The array has n values, so t has 2n slots. The leaves, which are the values, sit in slots n to 2n - 1. For n = 6 that is slots 6 to 11. The node in slot i has its two children in slots 2i and 2i + 1. The node in slot 1 is the top of the tree. Slot 0 is not used.

The values for the example array are:

slot   1   2   3   4   5    6    7    8    9    10   11
value  1   1   6   2   9    12   18   8    30   45   9

Check a few slots by hand. Slot 6 holds the first value, 12, and slot 7 holds the second value, 18. Their parent is slot 3, and GCD(12, 18) = 6, which matches. Slot 4 has children 8 and 9, which hold 8 and 30. Their GCD is 2. Slot 5 has children 10 and 11, which hold 45 and 9, so its GCD is 9. Slot 2 has children 4 and 5, so it holds GCD(2, 9) = 1. Slot 1 is the top, and it holds GCD(1, 6) = 1, the GCD of the whole array.

Now trace the query for positions 1 to 3. The range is half-open in the code, which means the right end is not included, so the query is positions 1, 2 and 3, or [1, 4). Add n to both ends to get leaf slots: l = 7 and r = 10. The loop does the following.

• Slot 7 is odd, so take it. That is the value 18. Move l to 8.
• Move both ends up one level by halving them: l = 4 and r = 5.
• Slot 5 is odd on the right side, so step r down to 4 and take slot 4. That holds the GCD of 8 and 30, which is 2.
• Now l = 2 and r = 2, so the range is empty and the loop stops.

The answer is GCD(18, 2) = 2. The tree took two stored values instead of three raw values here. On a large array the saving is much bigger, because the number of stored values used grows with how many times the length can be halved, not with the length itself.

A version of the same program that prints each step, with a print line in the loop, shows these lines for the steps above:

take t[7] = 18, result 18
take t[4] = 2, result 2
final 2

Program 1: build the tree, query it, and change a value

The first program builds the tree for the example array, answers three range queries, changes one value and answers again. The set function writes the new value into its leaf and then recomputes each parent on the way up to the top. It does not subtract the old value. The comment above the class says the constructor needs at least one value.

#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
 
// Segment tree over gcd. The tree is stored in one array t_ of size 2n.
// Leaves are t_[n .. 2n-1]. Node i has children 2i and 2i+1.
// t_[i] holds the gcd of the leaves below node i.
// The constructor requires at least one value.
class RangeGcd {
public:
    explicit RangeGcd(const std::vector<int>& a) : n_(a.size()), t_(2 * a.size(), 0) {
        for (std::size_t i = 0; i < n_; ++i) t_[n_ + i] = a[i];
        for (std::size_t i = n_ - 1; i >= 1; --i) t_[i] = std::gcd(t_[2 * i], t_[2 * i + 1]);
    }
 
    // Gcd of values[l..r-1]. The right end is not included.
    // An empty range returns 0, which is the identity for gcd.
    int query(std::size_t l, std::size_t r) const {
        int result = 0;
        for (l += n_, r += n_; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) result = std::gcd(result, t_[l++]);
            if (r % 2 == 1) result = std::gcd(result, t_[--r]);
        }
        return result;
    }
 
    // Change one value, then recompute only the nodes above it.
    void set(std::size_t pos, int value) {
        std::size_t i = pos + n_;
        t_[i] = value;
        for (i /= 2; i >= 1; i /= 2) t_[i] = std::gcd(t_[2 * i], t_[2 * i + 1]);
    }
 
private:
    std::size_t n_;
    std::vector<int> t_;
};
 
int main() {
    const std::vector<int> a = {12, 18, 8, 30, 45, 9};
    RangeGcd tree(a);
 
    std::cout << "gcd of [0, 2) = " << tree.query(0, 2) << '\n';
    std::cout << "gcd of [1, 4) = " << tree.query(1, 4) << '\n';
    std::cout << "gcd of [3, 6) = " << tree.query(3, 6) << '\n';
    std::cout << "gcd of [0, 6) = " << tree.query(0, 6) << '\n';
    std::cout << "gcd of [2, 2) = " << tree.query(2, 2) << '\n';
 
    tree.set(2, 27);  // a[2] was 8, now 27
    std::cout << "after a[2] = 27, gcd of [0, 3) = " << tree.query(0, 3) << '\n';
    std::cout << "after a[2] = 27, gcd of [0, 6) = " << tree.query(0, 6) << '\n';
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -Wextra -o gcd1 gcd1.cpp && ./gcd1

The output is:

gcd of [0, 2) = 6
gcd of [1, 4) = 2
gcd of [3, 6) = 3
gcd of [0, 6) = 1
gcd of [2, 2) = 0
after a[2] = 27, gcd of [0, 3) = 3
after a[2] = 27, gcd of [0, 6) = 3

Check the first line by hand: GCD(12, 18) is 6. The second line is the example from the trace: 2. The third line covers 30, 45 and 9. GCD(30, 45) is 15, and GCD(15, 9) is 3. The empty range [2, 2) has no values, so it returns 0, the identity. After position 2 changes to 27, the range [0, 3) holds 12, 18 and 27, whose GCD is 3.

Why undo works for sums

The lesson's central question is why a sum tree can use a shortcut that a GCD tree cannot. Start with a sum and see how the shortcut works.

Take the array 6 4 3. Build the running totals, called prefix sums. Before any values, the total is 0. After the first value it is 6. After the second it is 10. After the third it is 13. To get the sum of the third value alone, take the total after three values and subtract the total after two: 13 minus 10 is 3. Removing the first two values from the running total leaves exactly the third.

This works because every number has an opposite. For each value x there is a value -x that cancels it, so subtracting a piece from a total is always possible. Mathematicians say that addition has an inverse. Undo is the use of that inverse: you know the total and the part you do not want, so you subtract the part.

A sum tree also updates cheaply with undo. If position 1 changes from 4 to 7, the difference is 3. Every total that includes position 1 gains 3, and the tree adds that difference to the nodes above the position. It does not need the other values. The old value is subtracted and the new one added in one step.

Why GCD has no inverse

An operation has an inverse when the result and one of the inputs together determine the other input. For sums, the total 13 and the part 10 together determine the third value, 3. For GCD this fails.

Fix the first number at 6 and ask which second numbers give a GCD of 2. Check the numbers from 1 to 12. The second numbers that work are 2, 4, 8 and 10. All four give GCD(6, y) = 2. So if you know the result is 2 and the first number is 6, the second number could be any of four different values. Nothing in the result tells you which one was there. A result that can come from several inputs cannot be undone.

The same problem shows up with prefix GCDs. For 6 4 3, the running GCDs are these. Before any values, use 0, the identity. After 6 it is 6. After 6 and 4 it is 2. After all three it is 1. Suppose you want the GCD of the third value alone, which is 3. The two running values are 1 (after all three) and 2 (after two). Two tempting formulas both fail. Dividing gives 1 / 2, which is 0 with integer division. Subtracting gives 1 minus 2, which is -1, and a GCD is never negative. Neither gives 3. The value 3 cannot be recovered from the numbers 2 and 1, because many different numbers combined with 2 give a GCD of 1. For example, GCD(2, 3) and GCD(2, 5) are both 1.

Here is a table of the difference.

Program 2: random checks and the list of matching values

The second program tests the tree against the plain loop on random arrays. It also prints the list of second values from the example above. The random numbers come from a fixed seed, so the run is the same every time. Each trial builds a random array, then mixes point changes and queries, comparing every answer with a loop.

#include <cstddef>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
 
class RangeGcd {
public:
    explicit RangeGcd(const std::vector<int>& a) : n_(a.size()), t_(2 * a.size(), 0) {
        for (std::size_t i = 0; i < n_; ++i) t_[n_ + i] = a[i];
        for (std::size_t i = n_ - 1; i >= 1; --i) t_[i] = std::gcd(t_[2 * i], t_[2 * i + 1]);
    }
    int query(std::size_t l, std::size_t r) const {
        int result = 0;
        for (l += n_, r += n_; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) result = std::gcd(result, t_[l++]);
            if (r % 2 == 1) result = std::gcd(result, t_[--r]);
        }
        return result;
    }
    void set(std::size_t pos, int value) {
        std::size_t i = pos + n_;
        t_[i] = value;
        for (i /= 2; i >= 1; i /= 2) t_[i] = std::gcd(t_[2 * i], t_[2 * i + 1]);
    }
 
private:
    std::size_t n_;
    std::vector<int> t_;
};
 
int brute_gcd(const std::vector<int>& a, std::size_t l, std::size_t r) {
    int g = 0;
    for (std::size_t i = l; i < r; ++i) g = std::gcd(g, a[i]);
    return g;
}
 
int main() {
    std::mt19937 rng(2024);
    std::uniform_int_distribution<int> value(1, 60);
    int checks = 0;
    int mismatches = 0;
    for (int trial = 0; trial < 150; ++trial) {
        const std::size_t n = 1 + rng() % 30;
        std::vector<int> a(n);
        for (int& x : a) x = value(rng);
        RangeGcd tree(a);
        for (int step = 0; step < 20; ++step) {
            if (rng() % 3 == 0) {
                const std::size_t pos = rng() % n;
                a[pos] = value(rng);
                tree.set(pos, a[pos]);
            }
            const std::size_t l = rng() % (n + 1);
            const std::size_t r = l + rng() % (n + 1 - l);
            ++checks;
            if (tree.query(l, r) != brute_gcd(a, l, r)) ++mismatches;
        }
    }
    std::cout << "checks: " << checks << ", mismatches: " << mismatches << '\n';
 
    std::cout << "y with gcd(6, y) = 2:";
    for (int y = 1; y <= 12; ++y) {
        if (std::gcd(6, y) == 2) std::cout << ' ' << y;
    }
    std::cout << '\n';
    return 0;
}

The output is:

checks: 3000, mismatches: 0
y with gcd(6, y) = 2: 2 4 8 10

The 3000 checks are 150 trials with 20 queries each. Zero mismatches means every answer matched the loop, both before and after the point changes. The second line is the list from the previous section: four different second values give the same result.

Program 3: the undo attempts side by side

The third program builds prefix totals for the array 6 4 3, then tries to get the value at position 2 by subtraction for sums and by division and subtraction for GCD. The sum method gives the right answer. The GCD methods do not.

#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
 
int main() {
    const std::vector<int> a = {6, 4, 3};
 
    // pre_sum[i] is the sum of a[0..i-1], so pre_sum[0] is 0.
    // pre_gcd[i] is the gcd of a[0..i-1], with 0 as the empty identity.
    std::vector<int> pre_sum(a.size() + 1, 0);
    std::vector<int> pre_gcd(a.size() + 1, 0);
    for (std::size_t i = 0; i < a.size(); ++i) {
        pre_sum[i + 1] = pre_sum[i] + a[i];
        pre_gcd[i + 1] = std::gcd(pre_gcd[i], a[i]);
    }
 
    std::cout << "value at position 2 = " << a[2] << '\n';
    std::cout << "sum of [2, 3) by subtraction = " << pre_sum[3] - pre_sum[2] << '\n';
    std::cout << "gcd of [2, 3) by division = " << pre_gcd[3] / pre_gcd[2] << '\n';
    std::cout << "gcd of [2, 3) by subtraction = " << pre_gcd[3] - pre_gcd[2] << '\n';
    return 0;
}

The output is:

value at position 2 = 3
sum of [2, 3) by subtraction = 3
gcd of [2, 3) by division = 0
gcd of [2, 3) by subtraction = -1

The sum line is right. The two GCD lines are wrong, and the correct answer, which is the value 3, appears only in the first line. Integer division of 1 by 2 gives 0, and subtraction gives -1. The program prints both as they are, so you can see that the trick fails with a plain wrong number, not a crash.

Updating a value: what the tree does instead

When the array changes, the tree does not try to undo the old value. It writes the new value into its leaf, then recomputes each parent as the GCD of its two children, going up to the top. An array with 8 values has 3 parents above each leaf: the parent, the grandparent and the top. So one change costs three GCD calls.

Program 1 shows the effect. The GCD of positions 0 to 2 in 12 18 8 is 2. After position 2 changes to 27, the same query covers 12 18 27, and its GCD is 3. The tree gets this right because it never subtracts. Each parent is rebuilt from its current children.

Because GCD(x, x) is x, a range GCD over a fixed array can also use the overlapping-blocks idea from the sparse table lesson earlier in this module. That idea does not handle changing values, which is why this lesson uses a tree.

Common mistakes

Using 1 as the identity

The identity for GCD is 0, not 1. If the running answer starts at 1, every query returns 1, because GCD with 1 is always 1. The mistake is easy to make, because multiplication starts at 1 and addition starts at 0. Here is a loop that starts at 1 by mistake, run on the array 12 18 8:

#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
 
// Same query loop as the lesson, but the identity value is 1 instead of 0.
int query_with_bad_identity(const std::vector<int>& a, std::size_t l, std::size_t r) {
    int result = 1;  // bug: 0 is the identity for gcd, not 1
    for (std::size_t i = l; i < r; ++i) result = std::gcd(result, a[i]);
    return result;
}
 
int main() {
    const std::vector<int> a = {12, 18, 8};
    std::cout << "gcd of [0, 2) = " << query_with_bad_identity(a, 0, 2) << '\n';
    std::cout << "gcd of [0, 3) = " << query_with_bad_identity(a, 0, 3) << '\n';
    std::cout << "gcd of [2, 2) (empty) = " << query_with_bad_identity(a, 2, 2) << '\n';
    return 0;
}

The output is:

gcd of [0, 2) = 1
gcd of [0, 3) = 1
gcd of [2, 2) (empty) = 1

The correct answers are 6, 2 and 0. The program does not crash, so the only sign is the wrong numbers. Check the identity with a small case whenever you write a combine function.

Forgetting the header for std::gcd

std::gcd is declared in <numeric>. A file that uses it without that include fails to compile. Compiling this file with g++ 15.2.0 gives the first error below.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> a = {12, 18, 8};
    std::cout << std::gcd(a[0], a[1]) << '\n';
    return 0;
}

mistake4.cpp: In function ‘int main()’:
mistake4.cpp:6:23: error: ‘gcd’ is not a member of ‘std’

The fix is to add #include <numeric> at the top of the file. Compilers print more lines after the first error, and the first one is the one to read first.

Building a tree for an empty array

The constructor starts its build loop at n_ - 1. For an array of length 0, n_ - 1 wraps around to the largest value a std::size_t can hold, because unsigned numbers do not go below zero. The loop then reads a slot far past the end of t_. The lesson's constructor therefore needs at least one value, as its comment says. Build the tree with -D_GLIBCXX_ASSERTIONS while testing, and the mistake stops the program with this message, shown with g++ 15.2.0:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The fix is to return early when the array is empty, before the build loop. Empty ranges in queries are fine, because the query loop never runs for them.

Trying to undo a GCD

The prefix trick from Program 3 is the most common wrong idea in this topic. Subtracting or dividing two prefix GCDs does not give the GCD of the range between them. The output of Program 3 shows the wrong numbers, 0 and -1, from the two attempts. If you need to remove a value from a GCD, rebuild the affected part of the tree with set or rebuild the tree from the array.

Practice

Exercise 1

What is the GCD of 36, 48 and 60? Use the Euclid method for each pair.

Show the answer

Start with 36 and 48. The remainder of 48 divided by 36 is 12, and the remainder of 36 divided by 12 is 0, so GCD(36, 48) is 12. Then GCD(12, 60): the remainder of 60 divided by 12 is 0, so the result is 12. The answer is 12.

Exercise 2

What does query(3, 3) return on the tree in Program 1, and why?

Show the answer

It returns 0. The range [3, 3) contains no positions, because the right end is not included. The loop in query never runs, and the result starts at 0, which is the identity for GCD.

Exercise 3

Which values b from 1 to 12 give GCD(9, b) = 3?

Show the answer

Check each value. GCD(9, 3) is 3, GCD(9, 6) is 3, and GCD(9, 12) is 3. Every other value from 1 to 12 gives 1, except 9 itself, which gives 9. The answer is 3, 6 and 12, so three different second values give the same result, as with the 6 example above.

Exercise 4

For an array of 8 values, how many stored parents are recomputed when one value changes? Name the slots, assuming the leaf for position 5 changes. Leaves for 8 values are slots 8 to 15.

Show the answer

The leaf for position 5 is slot 8 + 5 = 13. Its parents are slot 13 divided by 2, which is 6, then 3, then 1. The slots recomputed are 6, 3 and 1, so there are 3 parents. In general, an array of length 8 has 3 levels above the leaves, which is log2(8).

Exercise 5

Write a loop that prints every pair (a, b) with 1 <= a, b <= 6 whose GCD is 1, and count them. Use std::gcd.

Show the answer

The loop is for (int a = 1; a <= 6; ++a) for (int b = 1; b <= 6; ++b) if (std::gcd(a, b) == 1) ++count;. The pairs with GCD 1 are the pairs with no common factor other than 1. Count them by hand for a check: for a = 1 there are 6 pairs, for a = 2 there are 3 (b = 1, 3, 5), for a = 3 there are 4 (b = 1, 2, 4, 5), for a = 4 there are 3 (b = 1, 3, 5), for a = 5 there are 5 (b = 1, 2, 3, 4, 6), and for a = 6 there are 2 (b = 1, 5). The total is 6 + 3 + 4 + 3 + 5 + 2 = 23.

Summary

• GCD is the greatest common divisor, and its identity is 0, because the GCD of any value with 0 is that value.
• A GCD segment tree stores the GCD of each block, and a query combines a few stored blocks.
• A sum can be undone by subtracting prefix totals, because every number has an opposite.
• A GCD cannot be undone, because the result does not say which value was removed.
• A point change in the GCD tree rebuilds only the parents of the changed leaf, so it never needs to subtract.