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 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].
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 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.
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 log2N , update query also takes log2N 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 106, range is divided into maximum of log2N 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.