### PROBLEM LINK:

*Author:* vinod10

*Tester:* nmalviya1929

*Editorialist:* vinod10

### DIFFICULTY:

Medium

### PREREQUISITES:

Sieve of Eratosthenes, Segment tree.

### PROBLEM:

Array of N elements and Q queries are given. Query type 1 updates x^{th} element to y. Query type 2 asks to find difference between sum of primes and sum of composites for a given range of numbers [l,r].

### QUICK EXPLANATION:

Using Sieve of Eratosthene, precomputation is done to find a number is prime or not. A segment tree is built to keep track of required answer. Leaf node stores positive value if the number is prime or negative of the value is stored.

### EXPLANATION:

Array elements can be as large as 10^{6}, so sieve is used to precompute primality of every number from 1 to 10^{6}.

Problem requires direct implementation of segment tree, so segment tree is built in which every node stores difference between sum of prime and sum of non-prime for corresponding range.

For update query, in constant time it can be checked whether updated number (y) is prime or not. If it is prime then we store sum[node]=y, else sum[node] stores -y. As height of tree can log_{2}N , update query also takes log_{2}N time as we traverse down to leaf once.

For answer query, sum for given range is calculated using recursion. (As r-l+1 can be as large as 10^{6}, range is divided into maximum of log_{2}N ranges. And sum for each range is computed in constant time. Segment tree code takes care of these things. :P)

Note : You can go though this to learn about segment tree data structure.

### AUTHORâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.