**Problem**

Given an array ‘arr’ of length ‘N’. We have to implement two types of queries:

- 1, ‘L’, ‘R’ - Update the segment from ‘L’ to ‘R’ by replacing every number with its number of divisors in that segment.
- 2, ‘L’, ‘R’ - Find the sum of the numbers in the segment from ‘L’ to ‘R’.

**Example - **

**Input:**

N = 6

Q = 3

arr = [ 4, 12, 7, 8, 5, 9 ]

queries = [ { 2, 3, 5 }, { 1, 2, 4 }, { 2, 2, 5 } ]

**Output: **

20

17

**Explanation:**

- The first query is of type 2, which means we have to find the sum in the segment [3, 5]. The elements in the segment are - [7, 8, 5]. Hence, the sum for this segment is 20.
- The second query is of type 1, which means that we have to update the segment [2, 4] by replacing every number with its number of divisors. The elements of the segment are - [12, 7, 8]. We get - [6, 2, 4] by replacing every number with its number of divisors. The final array will be - [4, 6, 2, 4, 5, 9].
- In the third query, we have to find the sum of elements from [2, 5]. The segment elements are - [6, 2, 4, 5]. Hence, the sum for this segment is 17.

**Approach**

When we see range update and sum queries, the first thing that comes to mind is a __Segment tree__ or a __Fenwick tree__. But in this problem, the update query isn’t that simple. We have to update a segment by replacing every number with its number of divisors. The sum query can be handled easily using the Fenwick tree.

We can notice that the number of divisors of 1 and 2 is 1 and 2 respectively. This means that we can ignore the updates on 1 and 2. For the remaining numbers, we can store the indexes of these numbers in a set. We can then only iterate on the numbers greater than two and perform updates by replacing every number with its number of divisors in that segment. If the number of divisors is <=2, we remove the index of that number from the set.

But how does this help in optimizing the time complexity? The upper bound of the number of divisors of a number is considered roughly O(N^^{⅓}) in practice. This means that a number of O(10*9) will take approximately 5-6 operations to reduce to a number <= 2. Therefore, if we only iterate on the numbers greater than two and reduce them, we can effectively solve the problem.

Since we also have to find the range sum of the array, we use the Fenwick tree such that the query(i) will return the sum of the array from index 1 to i. Thus, we can find the sum of the segment [l, r] by doing query(r) - query(l-1).

Also read, __Euclid GCD Algorithm__