Queries for Composite numbers in subarray (With Point Updates)

Given an array of N integers, the task is to perform the following two operations on the given array:

query(start, end) : Print the number of Composite numbers in the subarray from start to end 
update(i, x) : update the value at index i to x, i.e arr[i] = x 

Examples: 

Input : arr = {1, 12, 3, 5, 17, 9}
        Query 1: query(start = 0, end = 4)
        Query 2: update(i = 3, x = 6)
        Query 3: query(start = 0, end = 4)
Output :1
        2
Explanation
In Query 1, the subarray [0...4]
has 1 Composite number viz. {12}

In Query 2, the value at index 3 
is updated to 6, the array arr now is, {1, 12, 3, 
6, 7, 9}
In Query 3, the subarray [0...4]
has 2 Composite Numbers viz. {12, 6}

Since we need to handle both range queries and point updates, an efficient method is to use a segment tree to solve the problem. A segment tree is best suited for this purpose. 
We can use Sieve of Eratosthenes to preprocess all the primes till the maximum value that arr_i can take, say MAX. The time complexity for this operation will be O(MAX log(log(MAX))).

Building the segment tree: 
The problem can be reduced to subarray sum using segment tree.
Now, we can build the segment tree where a leaf node is represented as either 0 (if it is a prime number) or 1 (if it is a composite number).
The internal nodes of the segment tree equal to the sum of its child nodes, thus a node represents the total composite numbers in the range from L to R where the range L to R falls under this node and the sub-tree below it.

Handling Queries and Point Updates: 
Whenever we get a query from start to end, then we can query the segment tree for the sum of nodes in the range start to end, which in turn represents the number of composites in the range start to end.
If we need to perform a point update and update the value at index i to x, then we check for the following cases: 

Let the old value of arr_i be y and the new value be x.

• Case 1: If x and y both are composites. 
  Count of composites in the subarray does not change, so we just update array and donot 
  modify the segment tree
• Case 2: If x and y both are primes. 
  Count of composites in the subarray does not change, so we just update array and donot 
  modify the segment tree
• Case 3: If y is composite but x is prime. 
  Count of composite numbers in the subarray decreases, so we update array and add -1 to every 
  range, the index i which is to be updated, is a part of in the segment tree
• Case 4: If y is prime but x is composite. 
  Count of composite numbers in the subarray increases, so we update array and add 1 to every 
  range, the index i which is to be updated, is a part of in the segment tree  

Below is the implementation of the above approach: 

Number of Composites in subarray from 0 to 4 = 1
Number of Composites in subarray from 0 to 4 = 2

The time complexity of each query and update is O(logn) and that of building the segment tree is O(n)

Note: Here, the time complexity of pre-processing primes till MAX using the sieve of Eratosthenes is O(MAX log(log(MAX))) where MAX is the maximum value arr_i can take.

Auxiliary Space: O(n)