Data Structure Set 15

Given an array of n positive integers. We are required to write a program to print the minimum product of k integers of the given array.
Examples: 
 

Input : 198 76 544 123 154 675
         k = 2
Output : 9348
We get minimum product after multiplying
76 and 123.

Input : 11 8 5 7 5 100
        k = 4
Output : 1400

Given a sorted doubly linked list containing n nodes. The problem is removing duplicate nodes from the given list.

Examples: 

Given an array of n non-negative integers. The task is to find frequency of a particular element in the arbitrary range of array[]. The range is given as positions (not 0 based indexes) in array. There can be multiple queries of given type. 
Examples: 
 

Input  : arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
         left = 2, right = 8, element = 8
         left = 2, right = 5, element = 6      
Output : 3
         1
The element 8 appears 3 times in arr[left-1..right-1]
The element 6 appears 1 time in arr[left-1..right-1]

Given an array of size N which is initialized with all zeros. We are given many ranges add queries, which should be applied to this array. We need to print the final updated array as our result. 
 

Examples: 

N = 6
Arr = [0, 0, 0, 0, 0, 0]
rangeUpdate1 [0, 2], add 100
Arr = [100, 100, 100, 0, 0, 0]
rangeUpdate1 [1, 5], add 100
Arr = [100, 200, 200, 100, 100, 100]
rangeUpdate1 [2, 3], add 100
Arr = [100, 200, 300, 200, 100, 100]
Which is the final updated array.

You are given an array of size N and Q queries. Solve the queries to find LCM for the given range alongside the queries to update the array values.

Note: 0-based indexing is used.

Example 1:

Input:
N = 6, Q = 3
arr[] = {2,3,4,6,8,16}
Queries: getLCM(0,2)
         updateValue(3,8)
         getLCM(2,5)
Output:
12
16
Explanation: There are 3 queries: 
Query 1 :  lcm(2, 3, 4) = 12
Query 2 :  6 changes to 8
Query 3 :  lcm(4, 8, 8, 16) = 16

Your Task:
Complete updateValue() and getLCM() function. The segment tree array has been prebuilt for you. You only need to use it to complete the queries.
getLCM() returns the LCM of elements in range [L,R].
updateValue() processes the point update query.

Expected Time Complexity: O(Q*Log(N)*Log(N) ).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 10⁴
1 <= Q <= 10⁵
0 <= L, R, index <= N-1
1 <= arr[i], value <= 10⁴