Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Problem statement
2.
Naive Approach
2.1.
Code:
2.2.
Output:
2.3.
Time Complexity
2.4.
Space Complexity
3.
Optimized Approach
4.
Code:
4.1.
Output:
4.2.
Time Complexity
4.3.
Space Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Count of Xs in the Array for a given range of indices after array updates for Q queries

Apoorv
1 upvote

Problem statement

Given an array[] named as input of size n, the array contains n integers along with an array we are given a value of X and Q. The task is to perform some operations on the array for Q queries. The task is given below:-

• (1, S, E): If the query is of type 1, then find the count of X in the range [S, E] inclusive where S is Starting index and E is the ending index of the array for the given range.
• (2, I, K): If the query is of type 2, then update the array element at index I to K.

Example 1

Input

Input array = {4, 0, 0, 1, 2, 0, 5, 0, 3 }

Q = 5

X = 0

Queries array = { { 1, 0, 3 },

{ 2, 4, 0 },

{ 1, 0, 8 },

{ 2, 8, 0 },

{ 1, 0, 8 } };

Output

2

5

6

Explanation

Following are the values of queries performed:

Query 1: Find count of X that is 0 in the range [0, 3],  Count of Xs in the Array for a given range [0, 3] is 2

Query 2: Update input[4] to 0

Query 3: Find count of x that is 0 in the range [0, 8], Count of Xs in the Array for a given range [0, 8] is 5

Query 4: Update input[8] to 0, which will increase the count of 0 in the range [0, 8]

Query 5: Find count of x that is 0 in the range [0, 8] , Count of Xs in the Array for a given range [0, 8] is 6

Also see, Euclid GCD Algorithm

Naive Approach

The simplest brute force way to solve the problem is to modify the array element for the second type of query and traverse the array over the range [L, R] and output the count of K in it for the first type of query.

Code:

``````#include <bits/stdc++.h>
using namespace std;

// Perform all the queries
void performQueries(int size, int Q, int X ,vector<int>& input,vector<vector<int> >& queries)
{
for (int i = 1; i <= Q; i++) {

// Stores the count of Xs
int count = 0;

// Total of Count the number for query 1
if (queries[i - 1][0] == 1) {
for (int j = queries[i - 1][1];j <= queries[i - 1][2]; j++) {
if (input[j] == X)
count++;
}
cout << count << endl;
}

// Update the element for query 2
else {
input[queries[i - 1][1]] = queries[i - 1][2];
}
}
}

//Main Code
int main()
{
vector<int> input = { 4,0,0,1,2,0,5,0,3 };
int Q = 5;

vector<vector<int> > queries
= { { 1, 0,3 },
{ 2, 4, 0 },
{ 1, 0, 8 },
{ 2, 8, 0 },
{ 1, 0, 8 } };

int size = input.size();

int X = 0;

performQueries(size, Q, X, input, queries);

return 0;
}``````

Time Complexity

O(Q * N)

The time complexity to find the Count of Xs in the Array for a given range of indices after array updates for Q queries using naive approach will cost O(Q * N) time complexity where N is the size of the Array, and Q is the number of queries. Since for every query, we are iterating in the entire range and in worst case range could be from 0th index to the last index so using naive approach it will cost quadratic time complexity.

Space Complexity

O(1)

The space complexity to find the Count of Xs in the Array for a given range of indices after array updates for Q queries using a naive approach will cost no space complexity since we have not used any extra space in the entire implementation.

Optimized Approach

The time complexity can be improved using an efficient algorithm that requires segment trees. The segment tree will maintain the count of 'X' in every given range, and this will cost O(log(N)) time complexity where N is the size of the Array. Updating an element in the segment tree will also cost log(N) time complexity.

• Create a function Build tree that recursively calls itself once with either the left or right child, or twice with the left and right children (like divide and conquer).
• Find the sum of the count of Xs using a frequency function similar to the Build tree function.
• Define a function update that takes the current tree vertex and recursively calls itself with one of the two-child vertices, then recomputes the X count value, similar to how the Build tree method does it.
• To create the initial segment tree, create a vector segment_tree and use the function Build tree.
• Using the variable, I iterate through the range [1, Q] and complete the following steps:
• If the current query's type is 1, use the frequency(1, 0, size-1, left, right, segment_ tree) function to count the number of Ks.
• Otherwise, update the value in the array arr[] and update the value in the segment tree with the function update(1, 0, size-1, position, newvalue, segment_tree).

Code:

``````#include <bits/stdc++.h>
using namespace std;

// Function to build the segment tree recursively
void build_segment_tree(vector<int>& input,vector<int>& segment_tree,int v, int left, int right)
{

// Base case
if (left == right) {

// At leaf node count is 1
if (input[left] == 0)segment_tree[v] = 1;

// If the value is not x means is not 0 hence the count is 0
else segment_tree[v] = 0;
}

else {

// Find the mid
int mid = (left + right) / 2;

// Recursively build left subtree
build_segment_tree(input, segment_tree,v * 2, left, mid);

// Recursively build right subtree
build_segment_tree(input, segment_tree, v * 2 + 1,mid + 1, right);

// Parent nodes contains count of both left and right subtree
segment_tree[v] = segment_tree[v * 2]+ segment_tree[v * 2 + 1];
}
}

// Count of 0s in range left to right
int Count_zero(int v, int tl,int tr, int left, int right,vector<int>& segment_tree)
{
// Base Case
if (left > right)
return 0;

// When no two subtrees are combining
if (left == tl && right == tr) {
return segment_tree[v];
}

// Finding the mid
int tm = (tl + tr) / 2;

return Count_zero(v * 2, tl, tm,left, min(right, tm),segment_tree)
+ Count_zero(v * 2 + 1,tm + 1, tr,max(left, tm + 1),right, segment_tree);
}

// Updation of segment tree
void update(int v, int left, int right,int position, int newvalue,vector<int>& segment_tree)
{

// Base Case
if (left == right) {

// At leaf node count is 1
if (newvalue == 0)segment_tree[v] = 1;

// If the value is not x means is not 0 hence the count is 0
else segment_tree[v] = 0;
}

else {

// Find the mid
int mid = (left + right) / 2;
if (position <= mid)
update(v * 2, left, mid,position, newvalue,segment_tree);
else
update(v * 2 + 1, mid + 1,right, position, newvalue,segment_tree);

// Update the parent node
segment_tree[v] = segment_tree[v * 2]+ segment_tree[v * 2 + 1];
}
}

// Count of Xs in the Array for a given range
void rangeCount(int size, int Q, vector<int>& input,vector<vector<int> >& queries)
{
vector<int> segment_tree(4 * size + 1, 0);

// Build segment tree recursively
build_segment_tree(input, segment_tree, 1, 0, size - 1);

for (int i = 1; i <= Q; i++) {

// When query type is 1
if (queries[i - 1][0] == 1) {
int left = queries[i - 1][1];
int right = queries[i - 1][2];

cout << Count_zero(1, 0, size - 1, left,right, segment_tree)<<endl;
}

// When query type is 2
else {
input[queries[i - 1][1]] = queries[i - 1][2];
int position = queries[i - 1][1];
int newValue = queries[i - 1][2];

update(1, 0, size - 1, position ,newValue, segment_tree);
}
}
}

// Main Code
int main()
{
vector<int> input = { 4,0,0,1,2,0,5,0,3 };
int Q = 5;

vector<vector<int> > queries
= { { 1, 0,3 },
{ 2, 4, 0 },
{ 1, 0, 8 },
{ 2, 8, 0 },
{ 1, 0, 8 } };

int size = input.size();

int X = 0;

// Count of Xs in the Array for a given range
rangeCount(size, Q, input, queries);

return 0;
}``````

Time Complexity

O(Q * log(N))

The time complexity to find the Count of Xs in the Array for a given range of indices after array updates for Q queries using an efficient approach will cost O(Q * log(N)) time complexity since for every query we are iterating in the tree of size N which will cost only logarithmic time complexity.

Space Complexity

O(N)

The space complexity to find the Count of Xs in the Array for a given range of indices after array updates for Q queries using an efficient approach will cost linear space complexity since we are using an extra Array to store the segment tree.

FAQs

1. What are segment trees?
A Segment Tree is a data structure that can successfully answer range queries over an array while also allowing the Array to be modified.

2. Where are segment trees used?
When there are several range queries on an array and changes to the same Array's elements, a Segment Tree is employed. A segment tree can solve the problem in less time compared to the brute force approach.

Key Takeaways

In this article, we discussed the solution for the problem statement 'Count of Xs in the Array for a given range of indices after array updates for Q queries'.The article also discusses both naive and optimized approaches along with the time and space complexity of both solutions.

If you want to learn more about segment trees and want to practice some quality questions which may excel your preparation on these topics a notch higher, then you can visit our Guided Path for segment trees on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass