You are not logged in. Please login at www.codechef.com to post your questions!

×

M71PNP - Editorial

PROBLEM LINK:

Practice
Contest

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.

asked 26 Aug '17, 15:17

vinod10's gravatar image

6★vinod10
513
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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