Given an array arr[] of the size of N followed by an array of Q queries, of the following two types:
- Query Type 1: Given two integers L and R, find the sum of prime elements from index L to R where 0 <= L <= R <= N-1.
- Query Type 2: Given two integers i and X, change arr[i] = X where 0 <= i <= n-1.
Note: Every first index of the subquery determines the type of query to be answered.
Example:
Input: arr[] = {1, 3, 5, 7, 9, 11}, Q = { { 1, 1, 3}, {2, 1, 10}, {1, 1, 3 } }
Output:
15
12
Explanation:
First query is of type 1, so answer is (3 + 5 + 7), = 15
Second query is of type 2, so arr[1] = 10
Third query is of type 1, where arr[1] = 10, which is not prime hence answer is (5 + 7) = 12Input: arr[] = {1, 2, 35, 7, 14, 11}, Q = { {2, 4, 3}, {1, 4, 5 } }
Output: 14
Explanation:
First query is of type 2, So update arr[4] = 3
Second query is of type 1, since arr[4] = 3, which is prime. So answer is (3 + 11) = 14
Naive Approach: The idea is to iterate for each query between L to R and perform the required operation on the given array.
Time Complexity: O(Q * N * (O(sqrt(max(arr[i]))
Approach: To optimize the problem use Segment tree and Sieve Of Eratosthenes.
- First, create a boolean array that will mark the prime numbers.
- Now while making the segment tree only add those array elements as leaf nodes which are prime.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int const MAX = 1000001;bool prime[MAX];// Function to find the prime numbersvoid SieveOfEratosthenes(){ // Create a boolean array prime[] // and initialize all entries it as true // A value in prime[i] will // finally be false if i is Not a prime memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= MAX; p++) { // Check if prime[p] is not // changed, then it is a prime if (prime[p] == true) { // Update all multiples of p // greater than or equal to // the square of it numbers // which are multiple of p // and are less than p^2 are // already been marked for (int i = p * p; i <= MAX; i += p) prime[i] = false; } }}// Function to get the middle// index from corner indexesint getMid(int s, int e){ return s + (e - s) / 2;}// Function to get the sum of// values in the given range// of the arrayint getSumUtil(int* st, int ss, int se, int qs, int qe, int si){ // If segment of this node is a // part of given range, then // return the sum of the segment if (qs <= ss && qe >= se) return st[si]; // If segment of this node is // outside the given range if (se < qs || ss > qe) return 0; // If a part of this segment // overlaps with the given range int mid = getMid(ss, se); return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);}// Function to update the nodes which// have the given index in their rangevoid updateValueUtil(int* st, int ss, int se, int i, int diff, int si){ // If the input index lies // outside the range of // this segment if (i < ss || i > se) return; // If the input index is in // range of this node, then update // the value of the node and its children st[si] = st[si] + diff; if (se != ss) { int mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, diff, 2 * si + 1); updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2); }}// Function to update a value in// input array and segment treevoid updateValue(int arr[], int* st, int n, int i, int new_val){ // Check for erroneous input index if (i < 0 || i > n - 1) { cout << "-1"; return; } // Get the difference between // new value and old value int diff = new_val - arr[i]; int prev_val = arr[i]; // Update the value in array arr[i] = new_val; // Update the values of // nodes in segment tree // only if either previous // value or new value // or both are prime if (prime[new_val] || prime[prev_val]) { // If only new value is prime if (!prime[prev_val]) updateValueUtil(st, 0, n - 1, i, new_val, 0); // If only new value is prime else if (!prime[new_val]) updateValueUtil(st, 0, n - 1, i, -prev_val, 0); // If both are prime else updateValueUtil(st, 0, n - 1, i, diff, 0); }}// Return sum of elements in range// from index qs (query start) to qe// (query end). It mainly uses getSumUtil()int getSum(int* st, int n, int qs, int qe){ // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { cout << "-1"; return -1; } return getSumUtil(st, 0, n - 1, qs, qe, 0);}// Function that constructs Segment Treeint constructSTUtil(int arr[], int ss, int se, int* st, int si){ // If there is one element in // array, store it in current node of // segment tree and return if (ss == se) { // Only add those elements in segment // tree which are prime if (prime[arr[ss]]) st[si] = arr[ss]; else st[si] = 0; return st[si]; } // If there are more than one // elements, then recur for left and // right subtrees and store the // sum of values in this node int mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2); return st[si];}// Function to construct segment// tree from given arrayint* constructST(int arr[], int n){ // Allocate memory for the segment tree // Height of segment tree int x = (int)(ceil(log2(n))); // Maximum size of segment tree int max_size = 2 * (int)pow(2, x) - 1; // Allocate memory int* st = new int[max_size]; // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st;}// Driver codeint main(){ int arr[] = { 1, 3, 5, 7, 9, 11 }; int n = sizeof(arr) / sizeof(arr[0]); int Q[3][3] = { { 1, 1, 3 }, { 2, 1, 10 }, { 1, 1, 3 } }; // Function call SieveOfEratosthenes(); // Build segment tree from given array int* st = constructST(arr, n); // Print sum of values in // array from index 1 to 3 cout << getSum(st, n, 1, 3) << endl; // Update: set arr[1] = 10 // and update corresponding // segment tree nodes updateValue(arr, st, n, 1, 10); // Find sum after the value is updated cout << getSum(st, n, 1, 3) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ static int MAX = 1000001; static int prime[] = new int[MAX]; // Function to find the prime numbers static void SieveOfEratosthenes() { // Create a boolean array prime[] // and initialize all entries it as true // A value in prime[i] will // finally be false if i is Not a prime Arrays.fill(prime, 1); for (int p = 2; p * p <= MAX; p++) { // Check if prime[p] is not // changed, then it is a prime if (prime[p] == 1) { // Update all multiples of p // greater than or equal to // the square of it numbers // which are multiple of p // and are less than p^2 are // already been marked for (int i = p * p; i <= MAX - 1; i += p) prime[i] = 0; } } } // Function to get the middle // index from corner indexes static int getMid(int s, int e) { return s + (e - s) / 2; } // Function to get the sum of // values in the given range // of the array static int getSumUtil(int[] st, int ss, int se, int qs, int qe, int si) { // If segment of this node is a // part of given range, then // return the sum of the segment if (qs <= ss && qe >= se) return st[si]; // If segment of this node is // outside the given range if (se < qs || ss > qe) return 0; // If a part of this segment // overlaps with the given range int mid = getMid(ss, se); return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2); } // Function to update the nodes which // have the given index in their range static void updateValueUtil(int[] st, int ss, int se, int i, int diff, int si) { // If the input index lies // outside the range of // this segment if (i < ss || i > se) return; // If the input index is in // range of this node, then update // the value of the node and its children st[si] = st[si] + diff; if (se != ss) { int mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, diff, 2 * si + 1); updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2); } } // Function to update a value in // input array and segment tree static void updateValue(int arr[], int[] st, int n, int i, int new_val) { // Check for erroneous input index if (i < 0 || i > n - 1) { System.out.print("-1"); return; } // Get the difference between // new value and old value int diff = new_val - arr[i]; int prev_val = arr[i]; // Update the value in array arr[i] = new_val; // Update the values of // nodes in segment tree // only if either previous // value or new value // or both are prime if ((prime[new_val] | prime[prev_val]) != 0) { // If only new value is prime if (prime[prev_val] == 0) updateValueUtil(st, 0, n - 1, i, new_val, 0); // If only new value is prime else if (prime[new_val] == 0) updateValueUtil(st, 0, n - 1, i, -prev_val, 0); // If both are prime else updateValueUtil(st, 0, n - 1, i, diff, 0); } } // Return sum of elements in range // from index qs (query start) to qe // (query end). It mainly uses getSumUtil() static int getSum(int[] st, int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { System.out.println( "-1"); return -1; } return getSumUtil(st, 0, n - 1, qs, qe, 0); } // Function that constructs Segment Tree static int constructSTUtil(int arr[], int ss, int se, int[] st, int si) { // If there is one element in // array, store it in current node of // segment tree and return if (ss == se) { // Only add those elements in segment // tree which are prime if (prime[arr[ss]] != 0) st[si] = arr[ss]; else st[si] = 0; return st[si]; } // If there are more than one // elements, then recur for left and // right subtrees and store the // sum of values in this node int mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2); return st[si]; } // Function to construct segment // tree from given array static int[] constructST(int arr[], int n) { // Allocate memory for the segment tree // Height of segment tree int x = (int)(Math.ceil(Math.log(n)/Math.log(2))); // Maximum size of segment tree int max_size = 2 * (int)Math.pow(2, x) - 1; // Allocate memory int[] st = new int[max_size]; // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 3, 5, 7, 9, 11 }; int n = arr.length; int Q[][] = { { 1, 1, 3 }, { 2, 1, 10 }, { 1, 1, 3 } }; // Function call SieveOfEratosthenes(); // Build segment tree from given array int[] st = constructST(arr, n); // Print sum of values in // array from index 1 to 3 System.out.println(getSum(st, n, 1, 3)); // Update: set arr[1] = 10 // and update corresponding // segment tree nodes updateValue(arr, st, n, 1, 10); // Find sum after the value is updated System.out.println(getSum(st, n, 1, 3)); }}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approachimport mathMAX = 1000001# Create a boolean array prime[]# and initialize all entries it as true# A value in prime[i] will # finally be false if i is Not a primeprime = [True] * MAX# Function to find prime numbersdef SieveOfEratosthenes(): p = 2 while p * p <= MAX: # Check if prime[p] is not # changed, then it is a prime if prime[p] == True: # Update all multiples of p # greater than or equal to # the square of it numbers # which are multiple of p # and are less than p^2 are # already been marked for i in range(p * p, MAX, p): prime[i] = False p += 1 # Function to get the middle # index from corner indexes def getMid(s, e): return s + (e - s) // 2# Function to get the sum of # values in the given range # of the array def getSumUtil(st, ss, se, qs, qe, si): # If segment of this node is a # part of given range, then # return the sum of the segment if qs <= ss and qe >= se: return st[si] # If segment of this node is # outside the given range if se < qs or ss > qe: return 0 # If a part of this segment # overlaps with the given range mid = getMid(ss, se) return (getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2))# Function to update the nodes which # have the given index in their range def updateValueUtil(st, ss, se, i, diff, si): # If the input index lies # outside the range of # this segment if i < ss or i > se: return # If the input index is in # range of this node, then update # the value of the node and its children st[si] = st[si] + diff if se != ss: mid = getMid(ss, se) updateValueUtil(st, ss, mid, i, diff, 2 * si + 1) updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2) # Function to update a value in # input array and segment tree def updateValue(arr, st, n, i, new_val): # Check for erroneous input index if i < 0 or i > n - 1: print(-1) return # Get the difference between # new value and old value diff = new_val - arr[i] prev_val = arr[i] # Update the value in array arr[i] = new_val # Update the values of nodes # in segment tree only if # either previous value or # new value or both are prime if prime[new_val] or prime[prev_val]: # If only new value is prime if not prime[prev_val]: updateValueUtil(st, 0, n - 1, i, new_val, 0) # If only old value is prime elif not prime[new_val]: updateValueUtil(st, 0, n - 1, i, -prev_val, 0) # If both are prime else: updateValueUtil(st, 0, n - 1, i, diff, 0) # Return sum of elements in range # from index qs (query start) to qe # (query end). It mainly uses getSumUtil() def getSum(st, n, qs, qe): # Check for erroneous input values if qs < 0 or qe > n-1 or qs > qe: return -1 return getSumUtil(st, 0, n - 1, qs, qe, 0)# Function that constructs the Segment Treedef constructSTUtil(arr, ss, se, st, si): # If there is one element in # array, store it in current # node of segment tree and return if ss == se: # Only add those elements in segment # tree which are prime if prime[arr[ss]]: st[si] = arr[ss] else: st[si] = 0 return st[si] # If there are more than one # elements, then recur for left and # right subtrees and store the # sum of values in this node mid = getMid(ss, se) st[si] = (constructSTUtil(arr, ss, mid, st, 2 * si + 1) + constructSTUtil(arr, mid + 1, se, st, 2 * si + 2)) return st[si]# Function to construct segment # tree from given array def constructST(arr, n): # Allocate memory for the segment tree # Height of segment tree x = int(math.ceil(math.log2(n))) # Maximum size of segment tree max_size = 2 * int(pow(2, x)) - 1 # Allocate memory st = [0] * max_size # Fill the allocated memory st constructSTUtil(arr, 0, n - 1, st, 0) # Return the constructed segment tree return st# Driver codearr = [ 1, 3, 5, 7, 9, 11 ]n = len(arr)Q = [ [ 1, 1, 3 ], [ 2, 1, 10 ], [ 1, 1, 3 ] ]# Function callSieveOfEratosthenes()# Build segment tree from given arrayst = constructST(arr, n)# Print sum of values in # array from index 1 to 3 print(getSum(st, n, 1, 3))# Update: set arr[1] = 10 # and update corresponding # segment tree nodes updateValue(arr, st, n, 1, 10)# Find sum after value is updatedprint(getSum(st, n, 1, 3))# This code is contributed by Stuti Pathak |
C#
// C# program for the above approachusing System;class GFG { static int MAX = 1000001; static int[] prime = new int[MAX]; // Function to find the prime numbers static void SieveOfEratosthenes() { // Create a boolean array prime[] // and initialize all entries it as true // A value in prime[i] will // finally be false if i is Not a prime Array.Fill(prime, 1); for (int p = 2; p * p <= MAX; p++) { // Check if prime[p] is not // changed, then it is a prime if (prime[p] == 1) { // Update all multiples of p // greater than or equal to // the square of it numbers // which are multiple of p // and are less than p^2 are // already been marked for (int i = p * p; i <= MAX - 1; i += p) prime[i] = 0; } } } // Function to get the middle // index from corner indexes static int getMid(int s, int e) { return s + (e - s) / 2; } // Function to get the sum of // values in the given range // of the array static int getSumUtil(int[] st, int ss, int se, int qs, int qe, int si) { // If segment of this node is a // part of given range, then // return the sum of the segment if (qs <= ss && qe >= se) return st[si]; // If segment of this node is // outside the given range if (se < qs || ss > qe) return 0; // If a part of this segment // overlaps with the given range int mid = getMid(ss, se); return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2); } // Function to update the nodes which // have the given index in their range static void updateValueUtil(int[] st, int ss, int se, int i, int diff, int si) { // If the input index lies // outside the range of // this segment if (i < ss || i > se) return; // If the input index is in // range of this node, then update // the value of the node and its children st[si] = st[si] + diff; if (se != ss) { int mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, diff, 2 * si + 1); updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2); } } // Function to update a value in // input array and segment tree static void updateValue(int[] arr, int[] st, int n, int i, int new_val) { // Check for erroneous input index if (i < 0 || i > n - 1) { Console.Write("-1"); return; } // Get the difference between // new value and old value int diff = new_val - arr[i]; int prev_val = arr[i]; // Update the value in array arr[i] = new_val; // Update the values of // nodes in segment tree // only if either previous // value or new value // or both are prime if ((prime[new_val] | prime[prev_val]) != 0) { // If only new value is prime if (prime[prev_val] == 0) updateValueUtil(st, 0, n - 1, i, new_val, 0); // If only new value is prime else if (prime[new_val] == 0) updateValueUtil(st, 0, n - 1, i, -prev_val, 0); // If both are prime else updateValueUtil(st, 0, n - 1, i, diff, 0); } } // Return sum of elements in range // from index qs (query start) to qe // (query end). It mainly uses getSumUtil() static int getSum(int[] st, int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { Console.WriteLine( "-1"); return -1; } return getSumUtil(st, 0, n - 1, qs, qe, 0); } // Function that constructs Segment Tree static int constructSTUtil(int[] arr, int ss, int se, int[] st, int si) { // If there is one element in // array, store it in current node of // segment tree and return if (ss == se) { // Only add those elements in segment // tree which are prime if (prime[arr[ss]] != 0) st[si] = arr[ss]; else st[si] = 0; return st[si]; } // If there are more than one // elements, then recur for left and // right subtrees and store the // sum of values in this node int mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2); return st[si]; } // Function to construct segment // tree from given array static int[] constructST(int[] arr, int n) { // Allocate memory for the segment tree // Height of segment tree int x = (int)(Math.Ceiling(Math.Log(n,2))); // Maximum size of segment tree int max_size = 2 * (int)Math.Pow(2, x) - 1; // Allocate memory int[] st = new int[max_size]; // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st; } // Driver code static void Main() { int[] arr = { 1, 3, 5, 7, 9, 11 }; int n = arr.Length; // Function call SieveOfEratosthenes(); // Build segment tree from given array int[] st = constructST(arr, n); // Print sum of values in // array from index 1 to 3 Console.WriteLine(getSum(st, n, 1, 3)); // Update: set arr[1] = 10 // and update corresponding // segment tree nodes updateValue(arr, st, n, 1, 10); // Find sum after the value is updated Console.WriteLine(getSum(st, n, 1, 3)); }}// This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach let MAX = 1000001; let prime = new Array(MAX); // Function to find the prime numbers function SieveOfEratosthenes() { // Create a boolean array prime[] // and initialize all entries it as true // A value in prime[i] will // finally be false if i is Not a prime prime.fill(1); for (let p = 2; p * p <= MAX; p++) { // Check if prime[p] is not // changed, then it is a prime if (prime[p] == 1) { // Update all multiples of p // greater than or equal to // the square of it numbers // which are multiple of p // and are less than p^2 are // already been marked for (let i = p * p; i <= MAX - 1; i += p) prime[i] = 0; } } } // Function to get the middle // index from corner indexes function getMid(s, e) { return s + parseInt((e - s) / 2, 10); } // Function to get the sum of // values in the given range // of the array function getSumUtil(st, ss, se, qs, qe, si) { // If segment of this node is a // part of given range, then // return the sum of the segment if (qs <= ss && qe >= se) return st[si]; // If segment of this node is // outside the given range if (se < qs || ss > qe) return 0; // If a part of this segment // overlaps with the given range let mid = getMid(ss, se); return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2); } // Function to update the nodes which // have the given index in their range function updateValueUtil(st, ss, se, i, diff, si) { // If the input index lies // outside the range of // this segment if (i < ss || i > se) return; // If the input index is in // range of this node, then update // the value of the node and its children st[si] = st[si] + diff; if (se != ss) { let mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, diff, 2 * si + 1); updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2); } } // Function to update a value in // input array and segment tree function updateValue(arr, st, n, i, new_val) { // Check for erroneous input index if (i < 0 || i > n - 1) { document.write("-1"); return; } // Get the difference between // new value and old value let diff = new_val - arr[i]; let prev_val = arr[i]; // Update the value in array arr[i] = new_val; // Update the values of // nodes in segment tree // only if either previous // value or new value // or both are prime if ((prime[new_val] | prime[prev_val]) != 0) { // If only new value is prime if (prime[prev_val] == 0) updateValueUtil(st, 0, n - 1, i, new_val, 0); // If only new value is prime else if (prime[new_val] == 0) updateValueUtil(st, 0, n - 1, i, -prev_val, 0); // If both are prime else updateValueUtil(st, 0, n - 1, i, diff, 0); } } // Return sum of elements in range // from index qs (query start) to qe // (query end). It mainly uses getSumUtil() function getSum(st, n, qs, qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { document.write( "-1"); return -1; } return getSumUtil(st, 0, n - 1, qs, qe, 0); } // Function that constructs Segment Tree function constructSTUtil(arr, ss, se, st, si) { // If there is one element in // array, store it in current node of // segment tree and return if (ss == se) { // Only add those elements in segment // tree which are prime if (prime[arr[ss]] != 0) st[si] = arr[ss]; else st[si] = 0; return st[si]; } // If there are more than one // elements, then recur for left and // right subtrees and store the // sum of values in this node let mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2); return st[si]; } // Function to construct segment // tree from given array function constructST(arr, n) { // Allocate memory for the segment tree // Height of segment tree let x = parseInt((Math.ceil(Math.log(n)/Math.log(2))), 10); // Maximum size of segment tree let max_size = 2 * Math.pow(2, x) - 1; // Allocate memory let st = new Array(max_size); // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st; } let arr = [ 1, 3, 5, 7, 9, 11 ]; let n = arr.length; let Q = [ [ 1, 1, 3 ], [ 2, 1, 10 ], [ 1, 1, 3 ] ]; // Function call SieveOfEratosthenes(); // Build segment tree from given array let st = constructST(arr, n); // Print sum of values in // array from index 1 to 3 document.write(getSum(st, n, 1, 3) + "</br>"); // Update: set arr[1] = 10 // and update corresponding // segment tree nodes updateValue(arr, st, n, 1, 10); // Find sum after the value is updated document.write(getSum(st, n, 1, 3) + "</br>"); // This code is contributed by mukesh07.</script> |
Output:
15 12
Time Complexity: O(MAX*log(log(MAX))+Q * log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
