×

# GGSPAG - Editorial

Author: Suraj Kumar Tester: Rishabh Gupta Editorialist: Suraj Kumar

MEDIUM

# PREREQUISITES:

Data Structure, Segment tree, Sieve of Eratothenes

# PROBLEM:

You are given an array of N inegers on which you have to perform Q queries which can be of update type in which you need to change the content at index i with X. The other type of query is to count the total number of primes between a given range of indices L and R.

# QUICK EXPLANATION:

Find an efficient way to tell the no. of prime numbers between two given indices of an Array.

# EXPLANATION:

The problem is pretty straightforward. First of all we need to find all the prime numbers from 1 to 100000, which can be done using the sieve. After this is done we need to build the segment tree, which can be done in order of nlogn. After the tree is built we simply need to query the tree for each of the query of first type in order of logn. For the update query we need to change only those part of the tree which will be affected by this update. This can also be done in logn.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here. Tester's solution can be found here.

# RELATED PROBLEMS:

5
accept rate: 0%

19.8k350498541

 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,755
×1,672
×301
×48
×1

question asked: 24 Jan '17, 18:59

question was seen: 593 times

last updated: 25 Jan '17, 14:10