Problem:
 Score : 500 points    Problem Statement You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:   Type 1 : change the i_q -th character of S to c_q . (Do nothing if the i_q -th character is already c_q .)  Type 2 : answer the number of different characters occurring in the substring of S between the l_q -th and r_q -th characters (inclusive).       Constraints  N , Q , i_q , l_q , and r_q are integers.  S is a string consisting of lowercase English letters.  c_q is a lowercase English letter.  1 \leq N \leq 500000  1 \leq Q \leq 20000  |S| = N  1 \leq i_q \leq N  1 \leq l_q \leq r_q \leq N  There is at least one query of type 2 in each testcase.         Input Input is given from Standard Input in the following format:  N  S  Q  Query_1  \vdots  Query_Q   Here, Query_i in the 4 -th through (Q+3) -th lines is one of the following:  1  i_q  c_q   2  l_q  r_q       Output For each query of type 2 , print a line containing the answer.        Sample Input 1 7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7      Sample Output 1 3
1
5  In the first query, cdbb contains three kinds of letters: b , c , and d , so we print 3 .  In the second query, S is modified to abcdzbd .  In the third query, a contains one kind of letter: a , so we print 1 .  In the fourth query, S is modified to abcazbd .  In the fifth query, S does not change and is still abcazbd .  In the sixth query, abcazbd contains five kinds of letters: a , b , c , d , and z , so we print 5 .

Solution (Python):


class SegmentTree:
  arr=None
  tree=None
  n=0
  
  DEF=0

  def __init__(self,arr):
  
    self.arr=arr
    size=len(arr)
    
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    
    
    
    for i in range(size):
    
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
    
  
  def __choose__(self,a,b):
    
    return a | b
  
  
  def update(self,x,val):
    x+=self.n-1
  
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  
  
  
  def get_val(self,a,b,k=0,l=0,r=-1):
    
    if r<0:
      r=self.n
      
    
    if r<=a or b<=l:
      return self.DEF
    
    
    if a<=l and r<=b:
      return self.tree[k]
    
    
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print("----")
    print(list(map(bin,self.tree)))
    print(self.tree)
    
base=ord("a")
ALPHA="abcdefghijklmnopqrstuvwxyz"
def change_alpha_to_num(c):
  if c not in ALPHA:
    return 0
  
  return 1<<(ord(c)-base)

import sys
readline=sys.stdin.readline

N=int(readline())
S=readline()
Sarr=list(map(change_alpha_to_num,list(S)))
ST=SegmentTree(Sarr)

Q=int(readline())
for i in range(Q):
  q=list(readline().split())
  if q[0]=="1":
    
    i,c=int(q[1])-1,q[2]
    ST.update(i,change_alpha_to_num(c))
    
  elif q[0]=="2":
    l,r=int(q[1])-1,int(q[2])-1
  
    print(bin(ST.get_val(l,r+1)).count("1"))

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def string_to_number(a):
    return 1 << (ord(a) - ord("a"))

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = string_to_number(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if a & 1 == 0:
                res |= self.seg[a]
            if b & 1 == 1:
                res |= self.seg[b]
                b -= 1
            a = a // 2
            b = (b - 1) // 2
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    

    Q = int(readline())
    for _ in range(Q):
        q, a, b = map(str, readline().split())
        if q == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def string_to_number(a):
    return 1 << (ord(a) - ord("a"))

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = string_to_number(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if a & 1 == 0:
                res |= self.seg[a]
            if b & 1 == 1:
                res |= self.seg[b]
                b -= 1
            a = a // 2
            b = (b - 1) // 2
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    

    Q = int(readline())
    for _ in range(Q):
        q, a, b = map(str, readline().split())
        if q == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Solution (Python):
import bisect

def main():
    n = int(input())
    s = bytearray(input().encode())
    q = int(input())

    alpha = [ord('a')+i for i in range(26)]
    alpha_map = {c: [] for c in alpha}
    for i, c in enumerate(s):
        bisect.insort(alpha_map[c], i+1)

    for _ in range(q):
        t, a, b = [p for p in input().split()]
        t = int(t)
        a = int(a)
        if t == 1:
            char = s[a-1]
            b = ord(b)
            if char == b:
                continue
            src_lst = alpha_map[char]
            dst_lst = alpha_map[b]
            idx = bisect.bisect_left(src_lst, a)
            if idx < len(src_lst):
                src_lst.pop(idx)
            bisect.insort(dst_lst, a)
            s[a-1] = b
        else:
            b = int(b)
            cnt = 0
            for _, lst in alpha_map.items():
                idx = bisect.bisect_left(lst, a)
                if idx < len(lst) and lst[idx] <= b:
                    cnt +=1
            print(cnt)
main()

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
s = [{ord(c)-ord('a')} for c in s]

def segfunc(x, y):
    return x | y

def init(init_val):
    
    for i in range(n):
        seg[i+num-1] = init_val[i]
    
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p%2 == 0:
            res = segfunc(res, seg[p])
        if q%2 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


ide_ele = set()


num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(s)

q = int(input())
for _ in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Solution (Python):

n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2

raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp-1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp-1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      
    print(ans)

Solution (Python):

n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2

raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      
    print(ans)

Solution (Python):



class SegTree:
    
    
    
    
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        
        
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        
        
        
    
    def update(self,k,x):
        k += self.num-1 
        self.seg[k] = x
        
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 
        r += self.num-2 
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return x|y

N = int(input())
S = list(input())
Q = int(input())

A = [0]*N
atmp = ord('a')

for i in range(N):
    A[i] = 1<<(ord(S[i])-atmp)
    
seg = SegTree(N,A,segfunc,0)
popcount = lambda x: bin(x).count('1')

ans = []
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        upt = 1<<(ord(c)-atmp)
        seg.update(i,upt)
        
    else:
        l,r = int(l)-1,int(r)
        ans.append(popcount(seg.query(l,r)))

for a in ans:
    print(a)

Solution (Python):
"""segfunc"""



def segfunc(x, y):
    return x | y


def init(init_val):
    
    for i in range(N):
        seg[i-1+num] = init_val[i]

    
    for i in range(num-2, -1, -1):  
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])  



def update(k, x):
    k += num-1  
    seg[k] = x
    while k:
        k = (k-1)//2  
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])


def query(p, q):
    if q <= p:  
        return ide_ele
    p += num-1
    q += num-2  
    res = ide_ele
    while q-p > 1:
        if p % 2 == 0:
            res = segfunc(res, seg[p])
        if q % 2 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res



ide_ele = 0

N = int(input())
ss = list(input())
s = []
for i in range(N):
    s.append(1<<(ord(ss[i]))-97)


num = 2**(N-1).bit_length()
seg = [ide_ele]*2*num

init(s)


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


q = int(input())
for i in range(q):
    qq, xx, yy = map(str, input().split())
    if qq == '1':
        xx = int(xx)
        update(xx-1,1<<(ord(yy)-97))
    else:
        xx, yy = int(xx), int(yy)
        res = query(xx-1,yy)
        print(popcnt(res))

Solution (Python):

class SegmentTree:
    def __init__(self, base_array,n , default_value = 0, segfunc = lambda a, b: a + b): 
        self._num = 2 ** (n - 1).bit_length()
        self._seg = [default_value] * 2 * self._num
        self._segfunc = segfunc
        self._ide_ele = default_value
        for i in range(n):
            self._seg[i + self._num - 1] = base_array[i]
        for i in range(self._num - 2, -1, -1):
            self._seg[i] = segfunc(self._seg[2 * i + 1], self._seg[2 * i + 2])


    def update(self, k, x):
        k += self._num - 1
        self._seg[k] = x
        while k:
            k = (k - 1) // 2
            self._seg[k] = self._segfunc(self._seg[k * 2 + 1], self._seg[k * 2 + 2])


    def query(self, p, q):
        if q <= p:
            return self._ide_ele
        p += self._num - 1
        q += self._num - 2
        res = self._ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self._segfunc(res, self._seg[p])
            if q & 1 == 1:
                res = self._segfunc(res, self._seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self._segfunc(res, self._seg[p])
        else:
            res = self._segfunc(self._segfunc(res, self._seg[p]), self._seg[q])
        return res

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())

    A = [0 for i in range(N)]

    for i, c in enumerate(S):
        A[i] = 1 << ord(c) - ord('a')

    st = SegmentTree(A, N, 0, lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            st.update(a, 1 << ord(b) - ord('a'))

        if p == '2':
            s = st.query(a, b + 1)
            print(bin(s).count('1'))


if __name__ == '__main__':
    main()

Solution (Python):

class SegmentTree:
    def __init__(self, base_array,n , default_value = 0, segfunc = lambda a, b: a + b): 
        self._num = 2 ** (n - 1).bit_length()
        self._seg = [default_value] * 2 * self._num
        self._segfunc = segfunc
        self._ide_ele = default_value
        for i in range(n):
            self._seg[i + self._num - 1] = base_array[i]
        for i in range(self._num - 2, -1, -1):
            self._seg[i] = segfunc(self._seg[2 * i + 1], self._seg[2 * i + 2])


    def update(self, k, x):
        k += self._num - 1
        self._seg[k] = x
        while k:
            k = (k - 1) // 2
            self._seg[k] = self._segfunc(self._seg[k * 2 + 1], self._seg[k * 2 + 2])


    def query(self, p, q):
        if q <= p:
            return self._ide_ele
        p += self._num - 1
        q += self._num - 2
        res = self._ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self._segfunc(res, self._seg[p])
            if q & 1 == 1:
                res = self._segfunc(res, self._seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self._segfunc(res, self._seg[p])
        else:
            res = self._segfunc(self._segfunc(res, self._seg[p]), self._seg[q])
        return res

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())

    A = [0 for i in range(N)]

    for i, c in enumerate(S):
        A[i] = 1 << ord(c) - ord('a')

    st = SegmentTree(A, N, 0, lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            st.update(a, 1 << ord(b) - ord('a'))

        if p == '2':
            s = st.query(a, b + 1)
            print(bin(s).count('1'))


if __name__ == '__main__':
    main()

Solution (Python):
class my_segment_tree:
    def __init__(self, base_array, size, f=lambda a, b: a + b, default_value = 0):
        self.f = f
        self._seg_size = 2 ** (size.bit_length() + 1) - 1
        self._default_value = default_value
        self._array = [default_value] * (self._seg_size)
        k = 2 ** size.bit_length() - 1  

        for i in range(size):
            self._array[k + i] = base_array[i]

        while k > 0:
            for i in range((k + 1) // 2):
                self._array[(k + 2 * i) // 2] = f(self._array[k + 2 * i], self._array[k + 2 * i + 1])
            k //= 2
    def update(self, i, v):
        i += (self._seg_size // 2)
        self._array[i] = v
        while i > 0:
            i = (i - 1) >> 1
            self._array[i] = self.f(self._array[2 * i + 1], self._array[2 * i + 2])

    def get(self, left, right):
        return self._get(left, right, 0, self._seg_size // 2, 0) 

    def _get(self, left, right, l, r, i):
        if left <= l and r <= right:
            return self._array[i]

        a = 0
        if left <= (l + r) // 2:
            a = self._get(left, min(right, (l + r) // 2), l, (l + r) // 2, 2 * i + 1)
        b = 0
        if (l + r) // 2 + 1 <= right:
            b= self._get(max(left, (l + r) // 2 + 1), right, (l + r) // 2 + 1, r, 2 * i + 2)

        return self.f(a, b)

def main():
    N = int(input())
    S = input()
    M = int(input())
    A = [0 for i in range(N)]

    for i, c in enumerate(S):
        A[i] = 1 << ord(c) - ord('a')

    st = my_segment_tree(A, N, lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        if p == '1':
            st.update(a, 1 << (ord(b) - ord('a')))

        if p == '2':
            s = st.get(a, int(b) - 1)
            print(bin(s).count('1'))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left, insort
def main():
    n = int(input())
    s = list(input().rstrip())
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i, c in enumerate(s):
        al[ord(c) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = bisect_left(al[ord(s[y])-ord("a")],y)
            al[ord(s[y])-ord("a")].pop(p)
            insort(al[ord(z)-ord("a")],y)
            s[y] = z
        else:
            y = int(y) - 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Solution (Python):

from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(S, 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(tuple(S), 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(list(S), 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
 

N = int(input())
S = list(str(input()))

pos = [[] for _ in range(26)]
for x,s in enumerate(S):
    num = ord(s)-ord("a")
    pos[num].append(x)

q = int(input())
for _ in range(q):
    m,a,b = map(str,input().split())
    if m == "1":
        a = int(a)-1
        if S[a] == b:
            continue
        else:
            popind = bisect.bisect_left(pos[ord(S[a])-ord("a")],a)
            pos[ord(S[a])-ord("a")].pop(popind)
            bisect.insort(pos[ord(b)-ord("a")],a)
            S[a] = b
    else:
        a,b = int(a)-1,int(b)-1
        count = 0
        for i in range(26):
            l = bisect.bisect_left(pos[i],a)
            if l >= len(pos[i]):
                continue
            if pos[i][l] <= b:
                count += 1
        print(count)

Solution (Python):
import sys
input = sys.stdin.readline

def segfunc(x,y):
    return x | y

def init(init_val):
    
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


n = int(input())
s = list(input())[:-1]
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
s = [2 ** (ord(i) - ord('a')) for i in s]
init(s)
q = int(input())
for i in range(q):
    tmp = input()
    a,b,c = tmp[:-1].split()
    if a == "1":
        update(int(b)-1, 2 ** (ord(c) - ord('a')))
    else:
        if b == c:
            print(1)
        else:
            tmp = query(int(b)-1, int(c))
            tmp = format(tmp, 'b')
            print(tmp.count('1'))