×

# M71PNP - Editorial

Author: vinod10
Tester: nmalviya1929
Editorialist: vinod10

Medium

# 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.

6★vinod10
513
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,726
×301
×14
×1

question asked: 26 Aug '17, 15:17

question was seen: 191 times

last updated: 26 Aug '17, 15:17