Array of N elements and Q queries are given. Query type 1 updates xth 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].
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.
Array elements can be as large as 106, so sieve is used to precompute primality of every number from 1 to 106.
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.
Note : You can go though this to learn about segment tree data structure.
Author’s solution can be found here.