Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        self.data.append(None)
        self.p.append(random())
        self.left.append(None)
        self.right.append(None)
        self.parent.append(None)
        return len(self.data) - 1

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False


from sys import stdin
def input():
    return stdin.readline().strip()

def order(a):
    return ord(a) - 97


def main():

    n = int(input())
    s = list(input())
    q = int(input())

    # alphabet毎に整理
    alp = [Treap() for _ in range(26)]
    from random import shuffle
    l = [i for i in range(n)]
    shuffle(l)
    for i in l:
        alp[order(s[i])].add(i)

    # クエリ処理
    ans = []
    for _ in range(q):
        a, b, c = input().split()
        b = int(b) - 1

        # type1
        if a == '1':
            alp[order(s[b])].remove(b)
            alp[order(c)].add(b)
            s[b] = c

        # type2
        else:
            c = int(c) - 1
            num = 0
            for i in alp:
                if i.search(b, c):
                    num += 1
            ans.append(num)

    for i in ans:
        print(i)

main()

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        self.data.append(None)
        self.p.append(random())
        self.left.append(None)
        self.right.append(None)
        self.parent.append(None)
        return len(self.data) - 1

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False


from sys import stdin
def input():
    return stdin.readline().strip()

def order(a):
    return ord(a) - 97


def main():

    n = int(input())
    s = list(input())
    q = int(input())

    # alphabet毎に整理
    alp = [Treap() for _ in range(26)]
    from random import shuffle
    l = [i for i in range(n)]
    shuffle(l)
    for i in l:
        alp[order(s[i])].add(i)

    # クエリ処理
    ans = []
    for _ in range(q):
        a, b, c = input().split()
        b = int(b) - 1

        # type1
        if a == '1':
            alp[order(s[b])].remove(b)
            alp[order(c)].add(b)
            s[b] = c

        # type2
        else:
            c = int(c) - 1
            num = 0
            for i in alp:
                if i.search(b, c):
                    num += 1
            ans.append(num)

    for i in ans:
        print(i)

main()

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        self.data.append(None)
        self.p.append(random())
        self.left.append(None)
        self.right.append(None)
        self.parent.append(None)
        return len(self.data) - 1

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.left[i] > self.right[i]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            else:
                print('error')
            '''
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
            '''
            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.left[i] > self.right[i]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            else:
                print('error')
            '''
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
            '''
            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.right[self.left[i]] == None or self.left[self.right[i]] == None:
                    break
                elif random() > 0.5:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.right[self.left[i]] == None or self.left[self.right[i]] == None:
                    break
                elif random() > 0.5:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                print('error')
            '''
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
            '''
            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.right[self.left[i]] == None or self.left[self.right[i]] == None:
                    break
                elif random() > 0.5:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                print('error')
            '''
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
            '''
            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
class BinarySearchTree():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
                

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)
    
    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [BinarySearchTree() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
class BinarySearchTree():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
                

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)
    
    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [BinarySearchTree() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
class BinarySearchTree():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
                

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)
    
    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [BinarySearchTree() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
# BinarySearchTreeの実装
class BinarySearchTree():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
                

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)
    
    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [BinarySearchTree() for _ in range(26)]
for i in range(n):
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(input())
q = int(input())

from collections import Counter
ans = []
for _ in range(q):
    a, b, c = input().split()
    if a == '1':
        s[int(b)-1] = c
    else:
        dic = Counter(s[int(b)-1:int(c)])
        ans.append(len(dic))

for i in ans:
    print(i)

Fixed submission:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    s = list(input())

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()