×

# PRMQ - Editorial

Author: Vipul Sharma
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov

MEDIUM

Segment tree

# PROBLEM:

You are given array of $n$ integers and $q$ queries. For each query you have to sum up number of times prime numbers from $[x;y]$ occur in elements of $a$ from $[l;r]$.

# EXPLANATION:

Any number $C$ consists of at most $O(\log C)$ distinct prime divisors. We can keep all this divisors in segment tree and ask queries of kind how many numbers are there on segment $[l;r]$ such that $x \leq a[i] \leq y$. We have total of $O(n \log C)$ numbers in segment tree. Now we can answer those queries in $O((\log{(n \log C)})^2)$ per query with if we keep in each vertex of segment tree sorted array of numbers which occur on its segment.

We can answer a query in $\mathcal{O}(\log{(n \log C)})$ time by using persistent segment tree. For each prime $x$ from 2 to $max(A_i)$, we will maintain a version of segment tree, which the version $y$ can tell the answer for query (1, y) for some given $[l, r]$. We can maintain these versions of the segment trees using persistent segment tree. The answer for query $[x, y]$ and $[l, r]$ will be answer of query $[l, r]$ in $y$-th version of the segment tree subtracted by answer of the query $[l, r]$ in the $(x-1)^{th}$ version of segment tree.

# RELATED PROBLEMS:

This question is marked "community wiki".

4★melfice
811837
accept rate: 0%

19.8k350498541

 1 i found this to be more clean, detailed and understandable than the above editorial : Unofficial editorial answered 17 Jul '17, 21:28 23●2 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:

×15,639
×2,589
×1,755
×149
×13

question asked: 16 Jun '17, 10:47

question was seen: 2,511 times

last updated: 21 Nov '17, 16:31