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

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;
}

Output:

2
5
6

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.