Count number of smallest elements in given range

Given an array of N numbers and Q queries, each query consists of L and R. We need to write a program that prints the number of occurrence of the smallest element in the range L-R. 

Examples:

Input: a[] = {1, 1, 2, 4, 3, 3}
        Q = 2 
        L = 1 R = 4 
        L = 3 R = 6
Output: 2 
        1 
Explanation: The smallest element in range 1-4 
is 1 which occurs 2 times. The smallest element
in the range 3-6 is 2 which occurs once.  
Input : a[] = {1, 2, 3, 3, 1}
        Q = 2 
        L = 1 R = 5 
        L = 3 R = 4
Output : 2
         2

A normal approach will be to iterate from L-R and find out the smallest element in the range. Iterate again in the range L-R and count the number of times the smallest element occurs in the range L-R. In the worst case, the complexity will be O(N) if L=1 and R=N. 

An efficient approach will be to use Segment Trees to solve the above problem. At each node of the segment tree, smallest element and count of smallest element is stored. At leaf nodes, the array element is stored in the minimum and count stores 1. For all other nodes except the leaf nodes, we merge the right and left nodes following the given conditions:

1. min(left_subtree) < min(right_subtree): node.min=min(left_subtree), node.count = left_subtree.count 
2. min(left_subtree) > min(right_subtree): node.min=min(right_subtree), node.count=right_subtree.count 
3. min(left_subtree) = min(right_subtree): node.min=min(left_subtree) or min(right_subtree), node.count=left_subtree.count + right_subtree.count

Given below is the implementation of the above approach: 

2
1

Time Complexity: O(n) for the construction of tree. O(log n) for every query.

Auxiliary Space: O(N) where N=100005

Approach:

In this approach, we first precompute the minimum and count arrays for the given array. The minimum array stores the minimum value seen so far from the left and right ends of the array, and the count array stores the count of the minimum value seen so far. We then answer each query by first finding the minimum value in the given range, and then iterating over the range again to count the occurrences of the minimum value using the count array.

Note that this approach has a time complexity of O(n) for preprocessing and O(q * k) for answering q queries, where k is the maximum range size in the queries. This is less efficient than the segment tree approach, which has a time complexity of O(n log n) for preprocessing and O(q log n) for answering q queries. However, this approach is simpler and easier to understand, and may be sufficient for small problem sizes or simpler applications.

4
2

Time complexity: O(nlog(n))

Auxiliary Space: O(n*log(n))