Find lexographically largest character in a substring in range [l,r] for q queries| Segment Tree| OA

https://practice.geeksforgeeks.org/problems/c928f229cc972671d91c5e9f6b222414912cc88a/1

Given a string s whose length is n and array queries of length q where each elements of queries is either of type 1 query or type 2 query which is explained ahead.

There are two types of query.

Query type 1 : ["1",ind,char]  "1" denotes this is type 1 query. In this query you have to change the character at index ind in s to character char.(Data type of ind,char is string in input)

Query Type 2: ["2",left,right,k]  "2" denotes this is type 2 query. In this query you have to return kth lexographically largest character  in the subtring of s (it is the kth largest character in sorted order , not the kth distinct character) starting from index left and ending at index right both left and right are inclusive. (Data type of left,right,k is string in input)

You have to perform each query in the same order as given in  queries and return an array res such that res array contains the answer for each type2 query in same order as it appeared in queries.

Note : 0 based indexing is used.

Example 1:

Input:
n=4
s="abab"
q=2
queries={{"1","2","d"},{"2","1","3","1"}}
Output:
{"d"}
Explanation:
First query is of type 1 so after changing character at index 2
to d  s becomes abdb . Now Second query is of type 2 in which
the 1st(k=1) lexographically largest character is "d" in substring "bdb"(s[1:3]). So we
returned a array with result of type 2 query {"d"}.
Example 2:

Input:
n=3
s="aaa"
q=3
queries={{"1","1","e"},{"1","2","c"},{"2","1","2","2"}}
Output:
{"c"}
Explanation:
After applying first two queries s becomes aec. Now for
the last query which is a type 2 second largest character
in subtring s starting from index 1 to ending at index 2 is "c".
Your Task:
You don't need to read input or print anything. Your task is to complete the function easyTask() which takes an integer n,string s,an integer q and an array queries which contains  queries of type1 and type2  respectively and returns an array res such that res array contains the answer for each type2 query in same order as it appeared in queries.

Expected Time Complexity: O(N+(Q*logN))
Expected Space Complexity: O(N)


Constraints:
1<=n<=5*10^4
1<=q<=10^5
0<=int(left)<=int(right)<=n-1
0<=int(index)<=n-1
1<=int(k)<=right-left+1
s and char contains lowercase english letters
The sum of n over all test cases won't exceed 5*10^4.

------------------------------------------------------------------------------------------------------------------------------------

class Solution{
public:
    vector<vector<int>> tree;

    vector<int> merge(vector<int> &left, vector<int> &right){
        vector<int> freq(26,0);
        for(int i=0;i<26;i++){
            freq[i]=left[i]+right[i];
        }
        return freq;
    }

    void buildTree(string &s, int start, int end, int parent){
        if(start==end){
            tree[parent][s[start]-'a']++;
            return;
        }
        int mid=(start+end)/2;
        buildTree(s,start,mid,2*parent+1);
        buildTree(s,mid+1,end,2*parent+2);
        tree[parent]=merge(tree[2*parent+1],tree[2*parent+2]);
        return;
    }

    void update(int start, int end, int parent, int index, char c){
        if(start>end){
            return;
        }
        if(start==end){
            vector<int> freq(26,0);
            freq[c-'a']++;
            tree[parent]=freq;
            return;
        }
        int mid=(start+end)/2;
        if(index>mid){
            update(mid+1,end,2*parent+2,index,c);
        }
        else{
            update(start,mid,2*parent+1,index,c);
        }
        tree[parent]=merge(tree[2*parent+1],tree[2*parent+2]);
        return;
    }

    vector<int> querySolver(int start, int end, int qstart, int qend, int parent){
        if(qstart>end || qend<start){
            return vector<int>(26,0);
        }
        if(qstart<=start && qend>=end){
            return tree[parent];
        }
        int mid=(start+end)/2;
        auto L=querySolver(start,mid,qstart,qend,2*parent+1);
        auto R=querySolver(mid+1,end,qstart,qend,2*parent+2);
        return merge(L,R);
    }

    vector<char> easyTask(int n,string s,int q,vector<vector<string>> &queries){
        tree.resize(4*n+1,vector<int>(26,0));
        buildTree(s,0,n-1,0);
        vector<char> res;
        for(auto query: queries){
            int type=stoi(query[0]);
            if(type==1){
                int index=stoi(query[1]);
                char c=query[2][0];
                update(0,n-1,0,index,c);
            }
            else{
                int left=stoi(query[1]);
                int right=stoi(query[2]);
                int k=stoi(query[3]);
                auto freq=querySolver(0,n-1,left,right,0);
                for(int i=25;i>=0;i--){
                    k-=freq[i];
                    if(k<=0){
                        res.push_back(i+'a');
                        break;
                    }
                }
            }
        }
        return res;
    }
};