Problem: 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).

Submission attempts (in order):
class SegmentTree:
  """Segmant Tree for query process.

  Args:
    a (List[int]): array.
    identity (int): identity element with f.
  """
  def __init__(self, a, identity=0):
    self.a = a
    self.n = len(a)
    self.identity = identity
    self.depth = (self.n - 1).bit_length()
    self.segment = (1 << self.depth) - 1
    self.tree = [identity] * (self.segment * 2 + 1)
    self.tree[self.segment : self.n + self.segment] = a
    for i in range(self.segment - 1, -1, -1):
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def update(self, i: int, x: int):
    i += self.segment
    self.tree[i] = x
    while i:
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def query(self, l: int, r: int) -> int:
    """Query at [l, r]

    Args:
      l (int): left
      r (int): right

    Returns:
      int: result
    """
    if l > r:
      return self.identity
    l += self.segment
    r += self.segment
    res = self.identity
    while l <= r:
      if not l & 1:
        res = self.f(self.tree[l], res)
      if r & 1:
        res = self.f(res, self.tree[r])
      l = l // 2
      r = (r - 2) // 2
    return res

  def f(self, x: int, y: int) -> int:
    return x | y

n = int(input())
s = input()
q = int(input())
a = ord('a')
segment_tree = [SegmentTree([0] * n) for _ in range(26)]
for i in range(n):
  segment_tree[ord(s[i]) - a].update(i, 1)
for _ in range(q):
  query = input().split()
  if query[0] == '1':
    i = int(query[1])
    c = query[2]
    num_c = ord(c) - a
    for alph in range(26):
      segment_tree[alph].update(i, int(alph == num_c))
  else:
    l = int(query[1])
    r = int(query[2])
    kind = 0
    for alph in range(26):
      kind += segment_tree[alph].query(l, r)
    print(kind)

from typing import List


class SegmentTree:
    def __init__(self, a: List[bool], identity: bool = False):
        self.a = a
        self.n = len(a)
        self.identity = identity
        self.depth = (self.n - 1).bit_length
        self.segment = 1 << self.depth - 1
        self.tree = [identity] * (self.segment * 2 + 1)
        self.tree[self.segment : self.n + self.segment] = a
        for i in range(self.segment - 1, -1, -1):
            self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i: int, x: bool):
        i += self.segment
        self.tree[i] = x
        while i:
            i = (i - 1) // 2
            self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, l: int, r: int) -> int:
        """Query at [l, r]

        Args:
            l (int): left
            r (int): right

        Returns:
            int: result
        """
        if l > r:
            return self.identity
        l += self.segment
        r += self.segment
        res = self.identity
        while l <= r:
            if not l & 1:
                res = self.f(self.tree[l], res)
            if r & 1:
                res = self.f(res, self.tree[r])
            l = l // 2
            r = (r - 2) // 2
        return res

    def f(self, x: bool, y: bool) -> bool:
        return x or y
      

n = int(input())
s = input()
q = int(input())
a = ord('a')
alph = [[c == chr(a + i) for c in s] for i in range(26)]
st_list = [SegmentTree(alph[i]) for i in range(26)]

for _ in range(q):
  query = input()
  if query[0] == '1':
    _, i, c = map(int, query.split())
    j = ord(c) - a
    for k, st in enumerate(st_list):
      st.update(i, j == k)
  else:
    _, l, r = map(int, query.split())
    ans = [st.query(l, r) for st in st_list]
    print(sum(ans))

class SegmentTree:
  """Segmant Tree for query process.

  Args:
    a (List[int]): array.
    identity (int): identity element with f.
  """
  def __init__(self, a, identity=0):
    self.a = a
    self.n = len(a)
    self.identity = identity
    self.depth = (self.n - 1).bit_length()
    self.segment = (1 << self.depth) - 1
    self.tree = [identity] * (self.segment * 2 + 1)
    self.tree[self.segment : self.n + self.segment] = a
    for i in range(self.segment - 1, -1, -1):
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def update(self, i: int, x: int):
    i += self.segment
    self.tree[i] = x
    while i:
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def query(self, l: int, r: int) -> int:
    """Query at [l, r]

    Args:
      l (int): left
      r (int): right

    Returns:
      int: result
    """
    if l > r:
      return self.identity
    l += self.segment
    r += self.segment
    res = self.identity
    while l <= r:
      if not l & 1:
        res = self.f(self.tree[l], res)
      if r & 1:
        res = self.f(res, self.tree[r])
      l = l // 2
      r = (r - 2) // 2
    return res

  def f(self, x: int, y: int) -> int:
    return x | y

n = int(input())
s = input()
q = int(input())
a = ord('a')
segment_tree = SegmentTree([1 << (ord(c) - a) for c in s])
for _ in range(q):
  query = input().split()
  if query[0] == '1':
    i = int(query[1]) - 1
    c = query[2]
    segment_tree.update(i, 1 << (ord(c) - a))
  else:
    l = int(query[1]) - 1
    r = int(query[2]) - 1
    bit = segment_tree.query(l, r)
    print(format(bit, 'b').count('1'))

Verdicts: Runtime Error

Runtime Error

Accepted