Range GCD in Python and why it is not invertible

Why it matters

A question about a range can ask for more than a sum or a minimum. A problem might ask whether every number in a block of a list shares a common factor, or what the largest number is that divides all of them. The answer to that question is the greatest common divisor of the block, usually written GCD. A segment tree can answer it, and the code is almost the same as the sum tree you already know. The part that differs is the single rule that combines two answers.

The reason this lesson exists is a trap. For range sums there is a shortcut: store running totals, and the sum of any block is one subtraction. Many people try the same shortcut for GCD, and it fails. Understanding why it fails explains why a segment tree is needed for GCD, and it explains why a point update in a GCD tree must recompute parents rather than adjust them. This lesson covers only the GCD case. The sparse table from the previous lesson handles minimum, and the later lessons handle changing ranges.

You should be able to write a Python function and use a while loop. You do not need any number theory beyond the idea of a divisor, which is explained next.

What a GCD is

A divisor of a number is a whole number that divides it with no remainder. The divisors of 12 are 1, 2, 3, 4, 6 and 12. The divisors of 18 are 1, 2, 3, 6, 9 and 18. The numbers that divide both are 1, 2, 3 and 6. The largest of them is 6, so the greatest common divisor of 12 and 18 is 6.

Listing divisors is slow for big numbers. The Euclidean algorithm is a faster method, and it is the one programs use. It depends on the remainder, which is what is left over after division. In Python the remainder is written with %, so 18 % 8 is 2, because 8 goes into 18 twice with 2 left over.

The steps for gcd(18, 8) are these. Divide 18 by 8 and keep the remainder 2. Now the problem is gcd(8, 2). Divide 8 by 2 and the remainder is 0. When the remainder is 0, the answer is the other number, which is 2. So gcd(18, 8) is 2.

Here is the method in Python. It replaces the pair (a, b) with (b, a % b) until b is 0. The line a, b = b, a % b does both replacements at once, so the right side is worked out first.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Python also has math.gcd, which does the same job and is faster. This lesson writes its own version so you can see the steps. Use math.gcd in real code.

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

First, gcd(0, x) equals x for any positive x. Every number divides 0, because 0 is 0 times that number. So the common divisors of 0 and x are exactly the divisors of x, and the largest of them is x. The number 0 therefore acts like "nothing yet" when you combine values with GCD. That makes 0 the starting value for a range GCD, just as 0 is the starting value for a sum.

Second, GCD is associative. That word means the grouping does not change the answer. gcd(gcd(12, 18), 8) is gcd(6, 8), which is 2. gcd(12, gcd(18, 8)) is gcd(12, 2), which is also 2. Because of this property, the GCD of a block can be built from the GCDs of its two halves, which is what a segment tree needs.

The range GCD

The GCD of a range is the GCD of every item in it. For the list [12, 18, 8, 27, 9, 30], the GCD of positions 0 and 1 is gcd(12, 18), which is 6. The GCD of positions 2 to 4 is gcd(8, 27, 9). It is gcd(8, 27), which is 1, and then gcd(1, 9), which is also 1. Once the GCD reaches 1, it stays 1, because 1 divides everything.

The whole list has GCD 1, because 8 and 27 share no factor except 1. The single item at position 3 has GCD 27, because the GCD of one number is the number itself.

A segment tree stores one GCD for each segment, the same way a sum tree stores one sum. The tree is built from the leaves upward. A leaf holds one item. A parent holds the GCD of its two children. The only difference from the sum tree is the rule that combines the children. Where the sum tree adds, this tree calls gcd.

Building and querying the tree

Here is the complete tree. It has a build, a query, and a point update. The point update is covered in a later section, and it matters for the reason explained there. The random test at the end checks many queries against a plain loop that computes the GCD of each range.

Python · editable

import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

class GcdTree:
    def __init__(self, a):
        self.n = len(a)
        self.tree = [0] * (4 * self.n)
        self._build(a, 1, 0, self.n - 1)

def _build(self, a, node, l, r):
        if l == r:
            self.tree[node] = a[l]
            return
        mid = (l + r) // 2
        self._build(a, 2 * node, l, mid)
        self._build(a, 2 * node + 1, mid + 1, r)
        self.tree[node] = gcd(self.tree[2 * node], self.tree[2 * node + 1])

def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

def _query(self, node, nl, nr, l, r):
        if r < nl or nr < l:
            return 0
        if l <= nl and nr <= r:
            return self.tree[node]
        mid = (nl + nr) // 2
        return gcd(self._query(2 * node, nl, mid, l, r), self._query(2 * node + 1, mid + 1, nr, l, r))

def update(self, idx, value):
        self._update(1, 0, self.n - 1, idx, value)

def _update(self, node, nl, nr, idx, value):
        if nl == nr:
            self.tree[node] = value
            return
        mid = (nl + nr) // 2
        if idx <= mid:
            self._update(2 * node, nl, mid, idx, value)
        else:
            self._update(2 * node + 1, mid + 1, nr, idx, value)
        self.tree[node] = gcd(self.tree[2 * node], self.tree[2 * node + 1])

def brute_gcd(a, l, r):
    g = 0
    for i in range(l, r + 1):
        g = gcd(g, a[i])
    return g

a = [12, 18, 8, 27, 9, 30]
t = GcdTree(a)
print("gcd[0..1] =", t.query(0, 1))
print("gcd[2..4] =", t.query(2, 4))
print("gcd[0..5] =", t.query(0, 5))
print("gcd[3..3] =", t.query(3, 3))
print("gcd(0, 14) =", gcd(0, 14))

print("-- same whole gcd, same removed value, different leftover --")
x = [4, 6, 8]
y = [2, 6, 10]
print("x whole gcd =", brute_gcd(x, 0, 2), ", gcd without the 6 =", gcd(x[0], x[2]))
print("y whole gcd =", brute_gcd(y, 0, 2), ", gcd without the 6 =", gcd(y[0], y[2]))

print("-- point update recomputes parents --")
t.update(2, 5)
a[2] = 5
print("after a[2]=5, gcd[0..5] =", t.query(0, 5), "brute =", brute_gcd(a, 0, 5))
print("after a[2]=5, gcd[2..4] =", t.query(2, 4), "brute =", brute_gcd(a, 2, 4))

rnd = random.Random(7)
checked = 0
ok = True
for trial in range(300):
    n = 1 + rnd.randrange(40)
    b = [1 + rnd.randrange(120) for _ in range(n)]
    tr = GcdTree(b)
    for step in range(30):
        if rnd.random() < 0.5:
            idx = rnd.randrange(n)
            v = 1 + rnd.randrange(120)
            b[idx] = v
            tr.update(idx, v)
        else:
            l = rnd.randrange(n)
            r = l + rnd.randrange(n - l)
            if tr.query(l, r) != brute_gcd(b, l, r):
                ok = False
            checked += 1
print("random queries checked =", checked, "all match" if ok else "MISMATCH")

The output is:

gcd[0..1] = 6
gcd[2..4] = 1
gcd[0..5] = 1
gcd[3..3] = 27
gcd(0, 14) = 14
-- same whole gcd, same removed value, different leftover --
x whole gcd = 2 , gcd without the 6 = 4
y whole gcd = 2 , gcd without the 6 = 2
-- point update recomputes parents --
after a[2]=5, gcd[0..5] = 1 brute = 1
after a[2]=5, gcd[2..4] = 1 brute = 1
random queries checked = 4474 all match

Read the query code. The method returns 0 when a node is outside the query range. That is correct, because gcd(0, x) is x, so an outside node does not change the answer. The method returns the stored value when the node is fully inside the range. Otherwise it splits the node and combines the two answers with gcd. The structure matches the sum tree exactly, with 0 as the "no answer" value.

The line gcd[3..3] = 27 shows that a query on one position returns the item itself. The line gcd(0, 14) = 14 shows the identity rule.

The random check uses random.Random(7), so the same sequence of numbers appears on every run.

Why a subtraction trick works for sums and fails for GCD

Before a segment tree, many programmers store prefix sums. A prefix sum at position i is the total of all items from the start up to i. Call the prefix sums P. The sum of the range from l to r is then P[r] - P[l - 1], because subtracting removes everything before l.

This works because addition can be undone. Subtraction is the undo. If you know the total and you know one part, you can compute the other part. The sum from l to r is the total up to r with the total up to l - 1 taken away.

Many programmers try the same idea with GCD. Store the prefix GCDs, and then divide to undo the earlier part. Look at the list [12, 18, 8]. The prefix GCDs are 12, then gcd(12, 18) which is 6, then gcd(6, 8) which is 2. So P is 12, 6, 2. The true GCD of the range from position 1 to 2 is gcd(18, 8), which is 2. The trick would compute P[2] // P[0], which is 2 // 12. That is 0, which is not 2. Dividing does not undo the GCD either.

A small test program prints the numbers:

Python · editable

The output is:

prefix gcds: 12 6 2
true gcd of [18, 8] = 2
P[2] // P[0] = 0

The reason is deeper than a wrong choice of operation. GCD is not invertible. To say that an operation is invertible means you can undo it: given the combined result and one of the parts, you can always compute the other part. For sums, that holds. For GCD, it does not, and the proof is short.

Take two lists of three items. Both have the same whole GCD, and both contain the same middle value, 6. Remove the 6 from each one and see what remains.

The list [4, 6, 8] has whole GCD 2. Remove the 6, and the rest is [4, 8], whose GCD is 4.
The list [2, 6, 10] has whole GCD 2. Remove the 6, and the rest is [2, 10], whose GCD is 2.

The program printed exactly these values: x whole gcd = 2 , gcd without the 6 = 4 and y whole gcd = 2 , gcd without the 6 = 2. The whole GCD is 2 in both cases, and the removed value is 6 in both cases. The leftover is 4 in one case and 2 in the other. So no formula can take the whole GCD and the removed value and return the leftover, because the same inputs give two different leftovers. The information about the leftover was lost when the GCD was computed.

This is the difference from addition. A sum keeps every bit of the total, so you can subtract a part and get the rest. A GCD keeps only the largest common factor, which throws away the details that would let you recover the parts. The loss is permanent.

What this means for a segment tree

The consequence matters for updates. In a sum tree, a point update can be done with subtraction. If item 2 changes from 8 to 5, the change is 5 - 8, which is minus 3. You can add minus 3 to every ancestor's stored sum. You never need to look at the other children.

That shortcut is not available for GCD. When item 2 changes, each ancestor of that leaf must be recomputed from its two children. The update in the program does exactly this. It walks down to the leaf, stores the new value, and then on the way back up it sets each parent to gcd(left child, right child). Each step on the path uses the children's current values, not an adjustment.

Here is the path for the example, with a[2] changed to 5. In this tree the root splits into positions 0 to 2 and positions 3 to 5, and positions 0 to 2 split again into 0 to 1 and 2. The leaf for position 2 is set to 5. Its parent, covering 0 to 2, becomes gcd(6, 5), which is 1, because 6 is the stored GCD of positions 0 and 1. The root becomes gcd(1, 3), which is also 1, because 3 is the stored GCD of positions 3 to 5. The number of GCD calls is the height of the tree, which grows with log2(n). The program printed after a[2]=5, gcd[0..5] = 1 brute = 1, so the recomputed root matches the loop.

Each GCD call runs the Euclidean method, and that method takes a number of steps that grows slowly with the size of the numbers. Together, one update costs about log2(n) GCD calls.

Negative numbers

The Euclidean method is written for positive numbers. Python's % gives a result with the same sign as the divisor, so negative inputs can give a negative answer. Run the method on the pairs below and look at the signs.

Python · editable

The output is:

gcd(-12, 18) = 6
gcd(12, -18) = -6
gcd(0, 0) = 0
math.gcd(12, -18) = 6

The result gcd(0, 0) = 0 is correct by convention, because no number is required to divide 0. The result -6 is a sign problem, not a different divisor. If the problem allows negative numbers, use abs on each value before the loop, or use math.gcd, which always returns a non-negative answer.

Common mistakes

Using 1 as the starting value. The starting value for an empty answer must be 0, because gcd(0, x) is x. A starting value of 1 looks like a natural choice, since 1 is the multiplicative identity. But gcd(1, x) is always 1, so the answer is stuck at 1 for every range. Here is the difference on the range from 0 to 1 of [12, 18]:

Python · editable

start 1 over [12, 18] = 1
start 0 over [12, 18] = 6

The correct answer for [12, 18] is 6. The wrong start gives 1. The program does not crash. It returns a plausible small number, which is why it is easy to miss.

Trying to subtract or divide to undo a value. As shown above, the prefix trick fails. A query built on P[r] // P[l - 1] returns 0 or a wrong number, and a program that adds or removes values in a GCD tree by "adjusting" a parent gives wrong results after the first update. Recompute parents from both children instead.

Returning the wrong value for a node outside the range. A query that falls outside a node must return 0, which is the empty value. If it returns 1 instead, the 1 is combined into every answer that passes through that node, and each result becomes 1 or a small wrong number. The return 0 line in the query code is required.

Calling gcd with more than two arguments. The method takes two numbers. gcd(a, b, c) raises an error, because the function was written for two arguments:

TypeError: gcd() takes 2 positional arguments but 3 were given

To combine three numbers, nest the calls: gcd(gcd(a, b), c). The order does not matter, because GCD is associative.

A second example with updates

The first example used one fixed list. The next example adds changes in between queries, to show that the tree stays correct without any undo step. Take the list [6, 10, 15]. The whole GCD is gcd(6, gcd(10, 15)). The inner gcd is 5, and gcd(6, 5) is 1. The GCD of the range from 0 to 1 is gcd(6, 10), which is 2.

Now change position 2 from 15 to 4. The new list is [6, 10, 4]. The GCD of the range from 1 to 2 is gcd(10, 4), which is 2. The whole GCD is gcd(6, gcd(10, 4)), which is gcd(6, 2), which is 2. A tree for three items has a left child covering 0 to 1, which stores 2 and does not change, and a leaf for position 2. The update sets the leaf to 4 and recomputes the root as gcd(2, 4), which is 2. The stored values agree with the direct calculation, and no subtraction was needed. This is the pattern the random test in the program checks, with many queries across 300 trees that receive updates between queries.

Practice

Use the Euclidean method to compute gcd(48, 36). Write each step.

Show the answer

48 % 36 is 12, so the problem becomes gcd(36, 12). 36 % 12 is 0, so the answer is 12. The method returns 12.

For the list [10, 15, 25], find the GCD of positions 1 to 2, and the GCD of the whole list.

Show the answer

The GCD of 15 and 25 is 5, because 5 is the largest number that divides both. The whole list is gcd(10, 5), which is 5. Both answers are 5.

Give two lists of two items each that have the same whole GCD and the same removed value, but different leftover GCDs.

Show the answer

The lists [4, 6] and [2, 6] both have whole GCD 2. Remove the 6 from each one, and the leftovers are 4 and 2. The two inputs to any "undo" formula are the same, but the outputs differ, so no formula can undo the GCD.

Explain why the starting value for an empty range GCD is 0, not 1, and state what the query returns for a range with no items.

Show the answer

The starting value must be a value s where gcd(s, x) is x for every x. That is 0, because gcd(0, x) is x. A value of 1 would make every result 1. An empty range has no items, so the query returns the starting value, 0.

The tree stores the GCD of each segment. Change the program so that it answers the range LCM, the least common multiple, instead. Name the line that changes the combine rule, and say whether the tree still needs the 0 start value.

Show the answer

The least common multiple of two numbers is a * b // gcd(a, b). The combine rule in _build, update and _query changes from gcd(left, right) to a function that returns left * right // gcd(left, right). The start value changes too, because lcm(0, x) is 0, not x, so an empty range needs the start value 1 instead. Because lcm(1, x) equals x, the value 1 is the right empty value for LCM, and the change is sound.

Summary

The GCD of a range is the largest number that divides every item in it, and the Euclidean method finds it quickly.
A segment tree answers range GCD queries using the same build and query shape as a sum tree, with gcd as the combine rule and 0 as the empty value.
Prefix subtraction works for sums because addition can be undone, but GCD cannot be undone, as the example with two lists shows.
A point update in a GCD tree recomputes each ancestor from its two children, which costs about log2(n) GCD calls.
Two common errors are starting from 1 instead of 0, and passing negative numbers into the Euclidean method without a sign check.

Range GCD in Python and why it is not invertible

Why it matters

What a GCD is

The range GCD

Building and querying the tree

Why a subtraction trick works for sums and fails for GCD

What this means for a segment tree

Negative numbers

Common mistakes

A second example with updates

Practice

Summary

Stuck? Ask the tutor