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.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Segment trees revisited

Starter code: from typing import List





class Solution:

    def easyTask(self,n,s,q,queries) -> List[int]:

        # code here

        



Solutions:
from typing import List
from typing import List
from collections import Counter

class Fenwick:

	def __init__(self, n):
		self.T = [[0] * 26 for _ in range(n)]
		self.n = n
		self.F = lambda x: x & x + 1
		self.H = lambda x: x | x + 1

	def update(self, ind, c, delta):
		c = ord(c) - ord('a')
		while ind < self.n:
			self.T[ind][c] += delta
			ind = self.H(ind)

	def query(self, ind):
		result = [0] * 26
		while ind >= 0:
			for c in range(26):
				result[c] += self.T[ind][c]
			ind = self.F(ind) - 1
		return result

	def range_query(self, left, right):
		return [r - l for (r, l) in zip(self.query(right), self.query(left - 1))]

class Solution:

	def easyTask(self, n, s, q, queries) -> List[int]:
		tree = Fenwick(n)
		s = list(s)
		for (ind, c) in enumerate(s):
			tree.update(ind, c, 1)
		res = []
		for query in queries:
			if query[0] == '1':
				(ind, char) = (int(query[1]), query[2])
				tree.update(ind, s[ind], -1)
				s[ind] = char
				tree.update(ind, s[ind], 1)
			else:
				(left, right, k) = (int(query[1]), int(query[2]), int(query[3]))
				counter = tree.range_query(left, right)
				for c in range(25, -1, -1):
					if k > counter[c]:
						k -= counter[c]
					else:
						res.append(chr(c + ord('a')))
						break
		return res


from typing import List

def merge(a, b):
	return [a[i] + b[i] for i in range(len(a))]

class SegmentTree:

	def __init__(self, s):
		n = len(s)
		self.tree = [[0] * 26 for _ in range(2 * n)]
		self.n = n
		for i in range(n):
			idx = ord(s[i]) - ord('a')
			self.tree[i + n][idx] += 1
		for i in range(n - 1, 0, -1):
			self.tree[i] = merge(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, c):
		i = i + self.n
		self.tree[i] = [0] * 26
		self.tree[i][ord(c) - ord('a')] = 1
		while i > 1:
			i //= 2
			self.tree[i] = merge(self.tree[i * 2], self.tree[i * 2 + 1])

	def query(self, l, r):
		ans = [0] * 26
		l += self.n
		r += self.n
		while l <= r:
			if l % 2 == 1:
				ans = merge(ans, self.tree[l])
				l += 1
			if r % 2 == 0:
				ans = merge(ans, self.tree[r])
				r -= 1
			l //= 2
			r //= 2
		return ans

class Solution:

	def easyTask(self, n, s, q, queries) -> List[int]:
		ans = []
		st = SegmentTree(s)
		for (t, *q) in queries:
			if t == '1':
				st.update(int(q[0]), q[1])
			else:
				(l, r, k) = map(int, q)
				freq = st.query(l, r)
				for c in range(25, -1, -1):
					k -= freq[c]
					if k <= 0:
						ans.append(chr(97 + c))
						break
		return ans


from typing import List
from collections import defaultdict
import copy
from typing import List
from collections import defaultdict
import copy

class SegmentTree:

	def __init__(self, a):
		self.a = list(a)
		self.tree = list((defaultdict(int) for _ in range(len(a) * 4)))
		self.build(1, 0, len(a) - 1)

	def build(self, t, left, right):
		if left == right:
			self.tree[t][self.a[left]] += 1
		else:
			mid = (left + right) // 2
			self.build(2 * t, left, mid)
			self.build(2 * t + 1, mid + 1, right)
			s = copy.copy(self.tree[2 * t])
			for (k, v) in self.tree[2 * t + 1].items():
				s[k] += v
			self.tree[t] = s

	def update(self, i, new_value):
		self._update(1, 0, len(self.a) - 1, i, new_value)

	def _update(self, t, left, right, i, new_value):
		self.tree[t][self.a[i]] -= 1
		self.tree[t][new_value] += 1
		if left == right:
			self.a[i] = new_value
		else:
			mid = (left + right) // 2
			if i <= mid:
				self._update(2 * t, left, mid, i, new_value)
			else:
				self._update(2 * t + 1, mid + 1, right, i, new_value)

	def sum(self, qleft, qright):
		return self._sum(1, 0, len(self.a) - 1, qleft, qright)

	def _sum(self, t, left, right, qleft, qright):
		if qleft > qright:
			return defaultdict(int)
		if left == qleft and right == qright:
			return self.tree[t]
		mid = (left + right) // 2
		s1 = self._sum(t * 2, left, mid, qleft, min(qright, mid))
		s2 = self._sum(t * 2 + 1, mid + 1, right, max(qleft, mid + 1), qright)
		r = copy.copy(s1)
		for (k, v) in s2.items():
			r[k] += v
		return r

class Solution:

	def easyTask(self, n, s, q, queries) -> List[int]:
		s = list(s)
		ss = SegmentTree(s)
		r = []
		for qq in queries:
			if qq[0] == '1':
				(t, i, c) = qq
				ss.update(int(i), c)
			elif qq[0] == '2':
				(t, start, end, k) = map(int, qq)
				d = ss.sum(start, end)
				top = 0
				for c in reversed(range(26)):
					C = chr(ord('a') + c)
					top += d[C]
					if top >= k:
						r.append(C)
						break
		return r


from typing import List
from sortedcontainers import SortedSet
from collections import defaultdict

class Solution:

	def easyTask(self, n, s, q, queries) -> List[int]:
		s = list(s)
		pos = defaultdict(SortedSet)
		for (ind, c) in enumerate(s):
			pos[c].add(ind)
		res = []
		for query in queries:
			if query[0] == '1':
				(ind, char) = (int(query[1]), query[2])
				pos[s[ind]].remove(ind)
				s[ind] = char
				pos[s[ind]].add(ind)
			else:
				(left, right, k) = (int(query[1]), int(query[2]), int(query[3]))
				for c in sorted(pos, reverse=True):
					count = pos[c].bisect_right(right) - pos[c].bisect_left(left)
					if k > count:
						k -= count
					else:
						res.append(c)
						break
		return res


class SegmentTree:

	def __init__(self, s):
		n = len(s)
		self.tree = [[0] * 26 for _ in range(4 * n)]
		self.buildTree(s, 0, n - 1, 0)

	def buildTree(self, s, left, right, index=0):
		if left == right:
			self.tree[index][ord(s[left]) - ord('a')] += 1
			return
		mid = (left + right) // 2
		self.buildTree(s, left, mid, 2 * index + 1)
		self.buildTree(s, mid + 1, right, 2 * index + 2)
		for c in range(26):
			self.tree[index][c] = self.tree[2 * index + 1][c] + self.tree[2 * index + 2][c]

	def update(self, s, left, right, pos, char, index=0):
		if pos < left or pos > right:
			return
		if left == right:
			self.tree[index][ord(s[pos]) - ord('a')] -= 1
			s[pos] = char
			self.tree[index][ord(s[pos]) - ord('a')] += 1
			return
		mid = (left + right) // 2
		if pos <= mid:
			self.update(s, left, mid, pos, char, 2 * index + 1)
		else:
			self.update(s, mid + 1, right, pos, char, 2 * index + 2)
		for c in range(26):
			self.tree[index][c] = self.tree[2 * index + 1][c] + self.tree[2 * index + 2][c]

	def query(self, left, right, i, j, index=0):
		if right < i or left > j:
			return [0] * 26
		if i <= left and right <= j:
			return self.tree[index]
		mid = (left + right) // 2
		temp = [0] * 26
		res1 = self.query(left, mid, i, j, 2 * index + 1)
		res2 = self.query(mid + 1, right, i, j, 2 * index + 2)
		for c in range(26):
			temp[c] = res1[c] + res2[c]
		return temp

class Solution:

	def easyTask(self, n, s, q, queries):
		s = [el for el in s]
		seg = SegmentTree(s)
		res = []
		for quer in queries:
			if quer[0] == '1':
				seg.update(s, 0, n - 1, int(quer[1]), quer[2])
			else:
				char_freq = seg.query(0, n - 1, int(quer[1]), int(quer[2]))
				k = int(quer[3])
				for c in range(25, -1, -1):
					k -= min(k, char_freq[c])
					if k == 0:
						res.append(chr(ord('a') + c))
						break
		return res


from typing import List
from sortedcontainers import SortedSet
from collections import defaultdict

class Solution:

	def easyTask(self, n, s, q, queries) -> List[int]:
		(s, mp, ans) = (list(s), defaultdict(SortedSet), [])
		for (i, c) in enumerate(s):
			mp[c].add(i)
		for q in queries:
			if q[0] == '1':
				(i, ch) = (int(q[1]), q[2])
				mp[s[i]].remove(i)
				s[i] = ch
				mp[s[i]].add(i)
			else:
				(left, right, k) = (int(q[1]), int(q[2]), int(q[3]))
				for c in sorted(mp, reverse=True):
					cnt = mp[c].bisect_right(right) - mp[c].bisect_left(left)
					if k > cnt:
						k -= cnt
					else:
						ans.append(c)
						break
		return ans


from typing import List

class SegmentTree:

	def __init__(self, st):
		n = len(st)
		self.tree = [[0 for j in range(26)] for i in range(4 * n)]
		self.maketree(0, 0, n - 1, st)

	def maketree(self, index, left, right, st):
		if left == right:
			self.tree[index][ord(st[right]) - ord('a')] = 1
			return
		mid = (left + right) // 2
		self.maketree(2 * index + 1, left, mid, st)
		self.maketree(2 * index + 2, mid + 1, right, st)
		for i in range(26):
			self.tree[index][i] = self.tree[2 * index + 1][i] + self.tree[2 * index + 2][i]

	def update(self, index, left, right, pos, ch, st):
		if pos < left or pos > right:
			return
		self.tree[index][ord(st[pos]) - ord('a')] -= 1
		self.tree[index][ord(ch) - ord('a')] += 1
		if left == right:
			return
		mid = (left + right) // 2
		self.update(2 * index + 1, left, mid, pos, ch, st)
		self.update(2 * index + 2, mid + 1, right, pos, ch, st)

	def query(self, index, left, right, s, e, st, temp):
		if left > e or s > right:
			return
		if left >= s and right <= e:
			for i in range(26):
				temp[i] += self.tree[index][i]
			return
		mid = (left + right) // 2
		self.query(2 * index + 1, left, mid, s, e, st, temp)
		self.query(2 * index + 2, mid + 1, right, s, e, st, temp)

class Solution:

	def easyTask(self, n, s, q, queries) -> List[int]:
		st = list(s)
		res = []
		seg = SegmentTree(s)
		for q in range(len(queries)):
			if queries[q][0] == '1':
				uind = int(queries[q][1])
				ch = queries[q][2]
				seg.update(0, 0, n - 1, uind, ch, st)
				st[uind] = ch
			else:
				s = int(queries[q][1])
				e = int(queries[q][2])
				k = int(queries[q][3])
				temp = [0] * 26
				seg.query(0, 0, n - 1, s, e, st, temp)
				for i in range(25, -1, -1):
					k -= temp[i]
					if k <= 0:
						res.append(chr(i + 97))
						break
		return res


from typing import List
from itertools import islice
from operator import add
ORD_A = ord('a')

def ctoi(c):
	return ord(c) - ORD_A

def itoc(i):
	return chr(i + ORD_A)

class Solution:
	segments = None
	arr = None

	def build_segments(self):
		self._build_segments(0, 0, len(self.arr) - 1)

	def _build_segments(self, idx, left, right):
		segment = self.segments[idx]
		if left == right:
			segment[self.arr[left]] = 1
		if left >= right:
			return segment
		child_idx = 2 * idx
		mid = left + (right - left) // 2
		child_segment_left = self._build_segments(child_idx + 1, left, mid)
		child_segment_right = self._build_segments(child_idx + 2, mid + 1, right)
		for i in range(26):
			segment[i] = child_segment_left[i] + child_segment_right[i]
		return segment

	def update_segments(self, arr_i, new_c_ord):
		self._update_segments(0, 0, len(self.arr) - 1, arr_i, self.arr[arr_i], new_c_ord)
		self.arr[arr_i] = new_c_ord

	def _update_segments(self, idx, left, right, arr_i, old_c_ord, new_c_ord):
		if left <= arr_i <= right:
			segment = self.segments[idx]
			segment[old_c_ord] -= 1
			segment[new_c_ord] += 1
			if left < right:
				child_idx = 2 * idx
				mid = left + (right - left) // 2
				self._update_segments(child_idx + 1, left, mid, arr_i, old_c_ord, new_c_ord)
				self._update_segments(child_idx + 2, mid + 1, right, arr_i, old_c_ord, new_c_ord)

	def query_segments(self, start, end):
		acc = [0] * 26
		return self._query_segments(0, 0, len(self.arr) - 1, start, end, acc)

	def _query_segments(self, idx, left, right, start, end, acc):
		if end < left or right < start:
			return acc
		if start <= left and right <= end:
			segment = self.segments[idx]
			for i in range(26):
				acc[i] += segment[i]
			return acc
		if left < right:
			child_idx = 2 * idx
			mid = left + (right - left) // 2
			acc = self._query_segments(child_idx + 1, left, mid, start, end, acc)
			acc = self._query_segments(child_idx + 2, mid + 1, right, start, end, acc)
		return acc

	def easyTask(self, s_length, s, q_count, queries) -> List[int]:
		self.segments = [[0] * 26 for _ in range(4 * s_length)]
		self.arr = [ctoi(c) for c in s]
		self.build_segments()
		q_type2_results = []
		for q in queries:
			if q[0] == '1':
				(arr_i, new_c_ord) = (int(q[1]), ctoi(q[2]))
				self.update_segments(arr_i, new_c_ord)
			else:
				(q_type, start, end, k) = map(int, q)
				segment = self.query_segments(start, end)
				count = 0
				for i in reversed(range(26)):
					count += segment[i]
					if count >= k:
						q_type2_results.append(itoc(i))
						break
		return q_type2_results


from typing import List

class Solution:

	def combine(self, v, v1, v2):
		for i in range(26):
			self.freq[v][i] = self.freq[v1][i] + self.freq[v2][i]

	def build(self, a, v, tl, tr):
		if tl == tr:
			self.freq[v][ord(a[tl]) - 97] = 1
		else:
			tm = (tl + tr) // 2
			self.build(a, v * 2, tl, tm)
			self.build(a, v * 2 + 1, tm + 1, tr)
			self.combine(v, v * 2, v * 2 + 1)

	def update(self, a, v, tl, tr, pos, val):
		if tl == tr:
			self.freq[v][ord(a[tl]) - 97] -= 1
			self.freq[v][ord(val) - 97] += 1
			a[pos] = val
		else:
			tm = (tl + tr) // 2
			if pos <= tm:
				self.update(a, v * 2, tl, tm, pos, val)
			else:
				self.update(a, v * 2 + 1, tm + 1, tr, pos, val)
			self.combine(v, v * 2, v * 2 + 1)

	def query(self, v, tl, tr, l, r):
		if l > r:
			return [0 for i in range(26)]
		if l == tl and tr == r:
			return self.freq[v].copy()
		tm = (tl + tr) // 2
		f1 = self.query(v * 2, tl, tm, l, min(r, tm))
		f2 = self.query(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r)
		for i in range(26):
			f1[i] += f2[i]
		return f1

	def easyTask(self, n, s, q, queries) -> List[int]:
		ans = []
		a = list(s)
		self.freq = [[0 for _ in range(26)] for _ in range(4 * n)]
		self.build(a, 1, 0, n - 1)
		for query in queries:
			if query[0] == '1':
				self.update(a, 1, 0, n - 1, int(query[1]), query[2])
			else:
				cnt = self.query(1, 0, n - 1, int(query[1]), int(query[2]))
				k = int(query[3])
				for i in range(25, -1, -1):
					if cnt[i] >= k:
						ans.append(chr(97 + i))
						break
					else:
						k -= cnt[i]
		return ans


from typing import List

class Solution:

	def maketree(self, index, left, right, st, segment):
		if left == right:
			segment[index][ord(st[right]) - ord('a')] = 1
			return
		mid = (left + right) // 2
		self.maketree(2 * index + 1, left, mid, st, segment)
		self.maketree(2 * index + 2, mid + 1, right, st, segment)
		for i in range(26):
			segment[index][i] = segment[2 * index + 1][i] + segment[2 * index + 2][i]

	def update(self, index, left, right, uin, c, st, segment):
		if uin < left or uin > right:
			return
		segment[index][ord(st[uin]) - ord('a')] -= 1
		segment[index][ord(c) - ord('a')] += 1
		if left == right:
			return
		mid = (left + right) // 2
		self.update(2 * index + 1, left, mid, uin, c, st, segment)
		self.update(2 * index + 2, mid + 1, right, uin, c, st, segment)

	def find(self, index, left, right, s, e, st, segment, temp):
		if left > e or s > right:
			return
		if left >= s and right <= e:
			for i in range(26):
				temp[i] += segment[index][i]
			return
		mid = (left + right) // 2
		self.find(2 * index + 1, left, mid, s, e, st, segment, temp)
		self.find(2 * index + 2, mid + 1, right, s, e, st, segment, temp)

	def easyTask(self, n, s, q, queries) -> List[int]:
		st = list(s)
		res = []
		segment = [[0 for j in range(26)] for i in range(4 * n)]
		self.maketree(0, 0, n - 1, st, segment)
		for q in range(len(queries)):
			if queries[q][0] == '1':
				uind = int(queries[q][1])
				ch = queries[q][2]
				self.update(0, 0, n - 1, uind, ch, st, segment)
				st[uind] = ch
			else:
				s = int(queries[q][1])
				e = int(queries[q][2])
				k = int(queries[q][3])
				temp = [0] * 26
				self.find(0, 0, n - 1, s, e, st, segment, temp)
				for i in range(25, -1, -1):
					k -= temp[i]
					if k <= 0:
						res.append(chr(i + 97))
						break
		return res