PROBLEM LINK:Author: 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}. Note : You can go though this to learn about segment tree data structure. AUTHOR'S SOLUTIONS:Author's solution can be found here. asked 26 Aug '17, 15:17
