In the Country of Unlearned Lessons#4481

In the Country of Unlearned Lessons (Editorial)

To solve the problem, we need to process queries of two types:

computing the greatest common divisor (GCD) of the elements on a segment;
changing one element of the array.

The key property of the GCD is its associativity: the GCD of several numbers can be computed in parts. If the segment $[l, r]$ [l, r] is split into two parts $[l, k]$ [l, k] and $[k + 1, r]$ [k + 1, r], then

GCD (a_{l}, \dots, a_{r}) = GCD (GCD (a_{l}, \dots, a_{k}), GCD (a_{k + 1}, \dots, a_{r}))

\mathrm{GCD}(a_l, \ldots, a_r) = \mathrm{GCD}(\mathrm{GCD}(a_l, \ldots, a_k), \mathrm{GCD}(a_{k+1}, \ldots, a_r))

This is exactly the kind of operation a segment tree is designed for. Each vertex stores the GCD of the elements of its segment, and the value in an internal vertex equals the GCD of the values of its two children. The segment tree allows both computing the GCD on a segment and changing an array element using $O (lo g n)$ O(\log n) GCD operations.

Example

Let us consider how the algorithm works on the example. The left figure shows the segment tree for the initial array $(2, 4, 6, 10, 8)$ (2, 4, 6, 10, 8). Each vertex shows its segment and the GCD of the elements on it. The right figure shows the tree after both update queries have been executed; vertices whose values changed are highlighted.

Let us process the queries one by one:

$115$ : the segment $[1, 5]$ coincides with the segment of the root, so the answer is stored in the root and equals $2$ ;
$123$ : the segment $[2, 3]$ is split into the parts $[2]$ and $[3]$ , the answer is $GCD (4, 6) = 2$ \mathrm{GCD}(4, 6) = 2;
$2515$ : the element $a_{5}$ a_5 becomes $15$ . The vertices on the path from the leaf $[5]$ to the root are recomputed: in the vertex $[4, 5]$ we get $GCD (10, 15) = 5$ \mathrm{GCD}(10, 15) = 5, in the root — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1;
$2310$ : the element $a_{3}$ a_3 becomes $10$ . In the vertex $[1, 3]$ we get $GCD (2, 10) = 2$ \mathrm{GCD}(2, 10) = 2, in the root — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1;
$135$ : the segment $[3, 5]$ is split into the parts $[3]$ and $[4, 5]$ , the answer is $GCD (10, 5) = 5$ \mathrm{GCD}(10, 5) = 5;
$115$ : the answer is stored in the root and equals $1$ .

We get the answers $2, 2, 5, 1$ 2, 2, 5, 1, which coincide with the answer from the example.

Algorithm implementation

Declare the array $S e g T r ee$ SegTree to store the segment tree and the array $v$ to store the input sequence of numbers. Each vertex of the tree stores the GCD of the elements of its segment. Since $a_{i} \leq 1 0^{9}$ a_i \le 10^9 and the GCD does not exceed its arguments, the values in the cells of $S e g T r ee$ SegTree do not exceed the limits of the int type.

vector<int> SegTree, v;

The function BuildTree builds the segment tree from the array $a$ . Vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos]. The standard function $g c d$ is used to compute the GCD of two numbers.

void BuildTree(vector<int> &a, int v, int lpos, int rpos)
{
  if (lpos == rpos) SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(a, 2 * v, lpos, mid);
    BuildTree(a, 2 * v + 1, mid + 1, rpos);
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

The function GetGCD returns the GCD of the elements on the segment $[l e f t, r i g h t]$ [left, right]. Vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos].

If the query segment is empty ( $l e f t > r i g h t$ left > right), return $0$ — the neutral element for the GCD operation. If the query segment coincides with the segment of the vertex, the answer is stored in $S e g T r ee [v]$ SegTree[v]. Otherwise, split the query into the parts that fall into the left and right children, and return the GCD of the results.

int GetGCD(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;
  if ((left == lpos) && (right == rpos)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),
         GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

C++

The function update assigns the value $v a l$ to the element with index $p os$ . Vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos].

Descend to the leaf corresponding to position $p os$ and write the new value into it. When returning from the recursion, recompute the GCD in all vertices on the path from the leaf to the root.

void update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos) SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) update(2 * v, lpos, mid, pos, val);
    else update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

The main part of the program. Read the input sequence of numbers into the array $v$ , starting from index $1$ .

scanf("%d", &n);
v.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &v[i]);

Build the segment tree from the elements of the array $v [1 \dots n]$ v[1 \ldots n]. A segment tree on $n$ elements needs at most $4 n$ cells.

SegTree.resize(4 * n);
BuildTree(v,1,1,n);

Process the queries one by one. If $q = 1$ q = 1, print the GCD on the segment $[l, r]$ [l, r]. If $q = 2$ q = 2, assign the value $r$ to the element with index $l$ .

scanf("%d",&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d %d",&q,&l,&r);
  if (q == 1) printf("%d\n",GetGCD(1,1,n,l,r));
  else update(1,1,n,l,r);
}

C++

Python implementation

The list $S e g T r ee$ SegTree stores the segment tree; each of its vertices contains the GCD of the elements of its segment. Import the $ma t h$ module, which contains a function for computing the GCD.

import math

Declare the function gcd, which computes the GCD of two numbers.

def gcd(a, b):
  return math.gcd(a, b)

The function BuildTree builds the segment tree from the list $a$ . Vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos].

def BuildTree(a, v, lpos, rpos):
  if lpos == rpos:
    SegTree[v] = a[lpos]
  else:
    mid = (lpos + rpos) // 2
    BuildTree(a, 2 * v, lpos, mid)
    BuildTree(a, 2 * v + 1, mid + 1, rpos)
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

Python

The function GetGCD returns the GCD of the elements on the segment $[l e f t, r i g h t]$ [left, right]. Vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos].

def GetGCD(v, lpos, rpos, left, right):
  if left > right:
    return 0
  if left == lpos and right == rpos:
    return SegTree[v]
  mid = (lpos + rpos) // 2
  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),
      GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1),right))

Python

The function Update assigns the value $v a l$ to the element with index $p os$ . Vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos].

Descend to the leaf corresponding to position $p os$ and write the new value into it. When returning from the recursion, recompute the GCD in all vertices on the path from the leaf to the root.

def Update(v, lpos, rpos, pos, val):
  if lpos == rpos:
    SegTree[v] = val
  else:
    mid = (lpos + rpos) // 2
    if pos <= mid:
      Update(2 * v, lpos, mid, pos, val)
    else:
      Update(2 * v + 1, mid + 1, rpos, pos, val)
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

Python

The main part of the program. Read the input sequence of numbers into the list $v$ , starting from index $1$ .

n = int(input())
v = [0] + list(map(int, input().split()))

Build the segment tree from the elements of the list $v [1 \dots n]$ v[1 \ldots n]. A segment tree on $n$ elements needs at most $4 n$ cells.

SegTree = [0] * (4 * n)
BuildTree(v, 1, 1, n)

Process the queries one by one. If $q = 1$ q = 1, print the GCD on the segment $[l, r]$ [l, r]; if $q = 2$ q = 2, assign the value $r$ to the element with index $l$ .

m = int(input())
for _ in range(m):
  q, l, r = map(int, input().split())
  if q == 1:
    print(GetGCD(1, 1, n, l, r))
  else:
    Update(1, 1, n, l, r)

Python