Table of Contents
Problem Statement
The problem “Number of elements less than or equal to a given number in a given subarray” states that you are given an integer array and q number of queries. There will be two types of queries à
- queryUpdate(i, v): There will be two integers i and v, such that update the array[i] = v.
- queryPrint(left, right, k): print the number of integers within a range that are less than equal to k.
Example
arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)1 2 1
Explanation
queryPrint(0, 2, 2) will print number of elements less than or equal to 2 from index 0 to 2 i.e., 1
queryUpdate(2, 8) will update element at index 2 with value 8 i.e., arr will be {2, 4, 8, 1, 5}
queryPrint(1, 3, 5) will print number of elements less than or equal to 5 from index 1 to 3 i.e., 2
queryUpdate(4, 3) will update element at index 4 with 3 i.e., arr will be {2, 4, 8, 1, 3}
queryUpdate(1, 3) will update element at index 1 with 3 i.e., arr will be {2, 3, 8, 1, 3}
queryPrint(1, 2, 4) will print number of elements less than or equal to 4 from index 1 to 2 i.e., 1
Algorithm for finding numbers <= given value in subarray
- Divide the array into blocks of size equal to that of the square root of n, where n is the size of the input array.
- Build a binary index tree of size one more than the maximum element present in the array in a particular block.
- Find out the block for each element of the array to where it belongs and update the block’s BIT array with the 1 at arr[i].
- For each update query. Update the value of the BIT array, relative to the block at the original value of the array for the index with -1.
- Update the same block’s BIT array with the value 1 at the new element of a particular index.
- For each print query. Make a query to the BIT array, to count the elements value less than or equal to k. And for the complete block or for the incomplete or partial block, traverse through all the elements.
Explanation
We are given an integer array and two types of queries. One query is to update the value at a given particular index. And another query is to get the count of elements less than equal to k. For the update query, we will be given an index and a value. We will update the value v at the given index of array[i]. For the print query or count query, we need to print the number of integers, that are less than or equal to k.
We are going to divide the array into some blocks. These blocks will be of a size as the square root of the array’s length. For every block, we will be maintaining a binary index tree. The size of the binary index tree will be the one more than the maximum element for a particular block of the array element. Since we have BIT array for each block, update the value bit array with the value 1 at each position of the array[i] and also find out the block for each element of the array to where it belongs and follow the same procedure as above update the bit array of that block with 1 at arr[i].
For each update query, update the BIT array. Since we have a block for each array element. Update the value of the array at a particular index with the value -1 and update the required block’s BIT array with the value 1 at the new element of the array at the given index. And for the query of print or count the values, just traverse through the loop. There will be two cases that are for the complete block or for the partial complete block. At last return the value.
Code
C++ code for finding numbers <= given value in subarray
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX = 10001;
void update(int index, int block, int val, int bit[][MAX])
{
for (; index < MAX ; index += (index&-index))
bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
int sum = 0;
while (left<right && left%blockSize!=0 && left!=0)
{
if (arr[left] <= k)
sum++;
left++;
}
while (left + blockSize <= right)
{
int index = k;
for (; index > 0 ; index -= index&-index)
sum += bit[left/blockSize][index];
left += blockSize;
}
while (left <= right)
{
if (arr[left] <= k)
sum++;
left++;
}
return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
for (int i=0; i<n; i++)
update(arr[i], i/blockSize, 1, bit);
}
void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
update(arr[i], i/blockSize, -1, bit);
update(v, i/blockSize, 1, bit);
arr[i] = v;
}
int main()
{
int arr[] = {2,4,6,1,5};
int n = sizeof(arr)/sizeof(arr[0]);
int blockSize = sqrt(n);
int bit[blockSize+1][MAX];
memset(bit, 0, sizeof(bit));
preprocess(arr, blockSize, n, bit);
cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;
queryUpdate(2, 8, blockSize, arr, bit);
cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;
queryUpdate(4, 3, blockSize, arr, bit);
queryUpdate(1, 3, blockSize, arr, bit);
cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
return 0;
}
1 2 1
Java code for finding numbers <= given value in subarray
class NumberElements
{
static final int MAX = 10001;
static void update(int index, int block, int val, int bit[][])
{
for ( ; index < MAX ; index += (index&-index))
bit[block][index] += val;
}
static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
{
int sum = 0;
while (left < right && left % blockSize != 0 && left != 0)
{
if (arr[left] <= k)
sum++;
left++;
}
while (left + blockSize <= right)
{
int index = k;
for (; index > 0 ; index -= index&-index)
sum += bit[left/blockSize][index];
left += blockSize;
}
while (left <= right)
{
if (arr[left] <= k)
sum++;
left++;
}
return sum;
}
static void buildArray(int arr[], int blockSize, int n, int bit[][])
{
for (int i=0; i<n; i++)
update(arr[i], i/blockSize, 1, bit);
}
static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
{
update(arr[i], i/blockSize, -1, bit);
update(v, i/blockSize, 1, bit);
arr[i] = v;
}
public static void main(String args[])
{
int arr[] = {2,4,6,1,5};
int blockSize = (int) Math.sqrt(arr.length);
int bit[][] = new int[blockSize+1][MAX];
buildArray(arr, blockSize, arr.length, bit);
System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));
queryUpdate(2, 8, blockSize, arr, bit);
System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));
queryUpdate(4, 3, blockSize, arr, bit);
queryUpdate(1, 3, blockSize, arr, bit);
System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));
}
}
1 2 1
Complexity Analysis
Time Complexity
O(1) for updating the array and O(n) for printing the array.
Space Complexity
O(n) where “n” is the number of elements in the array. The problem “Number of elements less than or equal to a given number in a given subarray” has linear space.