Problem p02763 (python)

Fixed submission:
import math


def _hasParents(i):
    return i > 1


def _isLeftChild(i):
    return i % 2 == 0


def _isRightChild(i):
    return i % 2 == 1


def _parentNode(i):
    return i // 2


def _leftChild(i):
    return 2 * i


def _rightChild(i):
    return 2 * i + 1


def _leftSibling(i):
    return i - 1


def _rightSibling(i):
    return i + 1


def _nextPowerOfTwo(n):
    ret = 1
    while ret < n:
        ret *= 2
    return ret


def ancestors(i):
    while _hasParents(i):
        i = _parentNode(i)
        yield i


"""
class Config(NamedTuple, Generic[T, A]):
    mconvert: Callable[[T], A]
    mappend: Callable[[A, A], A]
    mempty: Callable[[], A]
"""
from collections import namedtuple

Config = namedtuple("Config", ["mconvert", "mappend", "mempty"])


class SegmentTree:
    def __init__(self, arr, mconvert, mappend, mempty, minCapacity=1):
        def wrappedMconvert(x):
            if x is not None:
                return mconvert(x)
            else:
                return mempty()

        def wrappedMappend(x, y):
            xEmpty = x == mempty()
            if xEmpty:
                return y
            yEmpty = y == mempty()
            if yEmpty:
                return x
            if xEmpty and yEmpty:
                return mempty()
            return mappend(x, y)

        self.config = Config(
            mconvert=wrappedMconvert, mappend=wrappedMappend, mempty=mempty
        )

        # Init empty tree
        self.MAX_SIZE = _nextPowerOfTwo(max(len(arr), minCapacity))
        self.values = [None] * self.MAX_SIZE
        self.accumulations = [self.config.mempty()] * (2 * self.MAX_SIZE)
        self.numValues = 0

        # Init values
        self.values[: len(arr)] = arr
        self.numValues = len(arr)
        # Init leaf accumulations
        self.accumulations[self.MAX_SIZE : self.MAX_SIZE + len(arr)] = map(
            self.config.mconvert, arr
        )
        # Init parent accumulations
        for parent in range(self.MAX_SIZE - 1, -1, -1):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )

    def query(self, i, j):
        # Inclusive i, exclusive j
        if not (0 <= i <= j <= self.numValues):
            raise IndexError
        if i == j:
            return self.config.mempty()
        leftTotal = self.config.mempty()
        rightTotal = self.config.mempty()
        l = self.MAX_SIZE + i
        r = self.MAX_SIZE + j - 1  # make inclusive both endpoints for calculations
        while l <= r:
            if _isRightChild(l):
                leftTotal = self.config.mappend(leftTotal, self.accumulations[l])
                l = _rightSibling(l)
            l = _parentNode(l)

            if _isLeftChild(r):
                rightTotal = self.config.mappend(self.accumulations[r], rightTotal)
                r = _leftSibling(r)
            r = _parentNode(r)
        return self.config.mappend(leftTotal, rightTotal)

    def append(self, x):
        assert self.numValues + 1 <= self.MAX_SIZE
        self.numValues += 1
        self.__setitem__(self.numValues - 1, x)

    def pop(self, i=None):
        if i is not None:
            raise NotImplementedError
        if not self.numValues:
            raise IndexError
        ret = self.__getitem__(self.numValues - 1)
        self.__delitem__(self.numValues - 1)
        return ret

    def insert(self, i, x):
        raise NotImplementedError


    def __getitem__(self, index):
        if isinstance(index, slice):
            raise NotImplementedError
        if not 0 <= index < self.numValues:
            raise IndexError
        ret = self.values[index]
        assert ret is not None
        return ret


    def __setitem__(self, i, x):
        if isinstance(i, slice):
            raise NotImplementedError
        
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = x
        self.accumulations[index] = self.config.mconvert(x)
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
            parent = _parentNode(parent)


    def __delitem__(self, i):
        if isinstance(i, slice):
            raise NotImplementedError
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = None
        self.accumulations[index] = self.config.mempty()
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
        self.numValues -= 1

    def __len__(self):
        return self.numValues


def charToBitmask(c):
    return 1 << (ord(c) - ord("a"))


def popcount(n):
    # Python doesn't have __builtin_popcount
    return bin(n).count("1")


N, = list(map(int, input().split()))
S = [charToBitmask(c) for c in input().rstrip()]
Q, = list(map(int, input().split()))
queries = []
for i in range(Q):
    queries.append(input().split())


segTree = SegmentTree(S, lambda x: x, lambda mask1, mask2: mask1 | mask2, lambda: 0)
out = []
for query in queries:
    if query[0] == "1":
        _, i, c = query
        i = int(i) - 1
        segTree[i] = charToBitmask(c)
    elif query[0] == "2":
        _, l, r = query
        l = int(l) - 1
        r = int(r) - 1
        mask = segTree.query(l, r + 1)

        out.append(str(popcount(mask)))
print("\n".join(out))

Buggy submission (verdict: Runtime Error):
import math
from typing import (
    Callable,
    cast,
    Generic,
    Iterable,
    Iterator,
    List,
    MutableSequence,
    NamedTuple,
    Optional,
    overload,
    TypeVar,
    Union,
)


def _hasParents(i: int) -> bool:
    return i > 1


def _isLeftChild(i: int) -> bool:
    return i % 2 == 0


def _isRightChild(i: int) -> bool:
    return i % 2 == 1


def _parentNode(i: int) -> int:
    return i // 2


def _leftChild(i: int) -> int:
    return 2 * i


def _rightChild(i: int) -> int:
    return 2 * i + 1


def _leftSibling(i: int) -> int:
    return i - 1


def _rightSibling(i: int) -> int:
    return i + 1


def _nextPowerOfTwo(n: int) -> int:
    ret = 1
    while ret < n:
        ret *= 2
    return ret


def ancestors(i: int) -> Iterator[int]:
    while _hasParents(i):
        i = _parentNode(i)
        yield i


T = TypeVar("T")
A = TypeVar("A")


class Config(NamedTuple, Generic[T, A]):
    mconvert: Callable[[T], A]
    mappend: Callable[[A, A], A]
    mempty: Callable[[], A]


class SegmentTree(Generic[T, A], MutableSequence[T]):
    """A complete binary tree of n leaves stored in a contiguous array of length 2n.

    The children of index i are found at 2*i and 2*i+1, with root starting at index 1
    Example:
      |---------------|
      | 1             |
      |---------------|
      | 2     | 3     |
      |---------------|
      | 4 | 5 | 6 | 7 |
      |---------------|
    """

    MAX_SIZE: int
    values: List[Optional[T]]
    accumulations: List[A]
    numValues: int
    config: Config

    def __init__(
        self,
        arr: List[T],
        mconvert: Callable[[T], A],
        mappend: Callable[[A, A], A],
        mempty: Callable[[], A],
        minCapacity: int = 1,
    ):
        def wrappedMconvert(x: T) -> A:
            if x is not None:
                return mconvert(x)
            else:
                return mempty()

        def wrappedMappend(x: A, y: A) -> A:
            xEmpty = x == mempty()
            if xEmpty:
                return y
            yEmpty = y == mempty()
            if yEmpty:
                return x
            if xEmpty and yEmpty:
                return mempty()
            return mappend(x, y)

        self.config = Config(
            mconvert=wrappedMconvert, mappend=wrappedMappend, mempty=mempty
        )

        # Init empty tree
        self.MAX_SIZE = _nextPowerOfTwo(max(len(arr), minCapacity))
        self.values = [None] * self.MAX_SIZE
        self.accumulations = [self.config.mempty()] * (2 * self.MAX_SIZE)
        self.numValues = 0

        # Init values
        self.values[: len(arr)] = arr
        self.numValues = len(arr)
        # Init leaf accumulations
        self.accumulations[self.MAX_SIZE : self.MAX_SIZE + len(arr)] = map(
            self.config.mconvert, arr
        )
        # Init parent accumulations
        for parent in range(self.MAX_SIZE - 1, -1, -1):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )

    def query(self, i: int, j: int) -> A:
        # Inclusive i, exclusive j
        if not (0 <= i <= j <= self.numValues):
            raise IndexError
        if i == j:
            return self.config.mempty()
        leftTotal = self.config.mempty()
        rightTotal = self.config.mempty()
        l = self.MAX_SIZE + i
        r = self.MAX_SIZE + j - 1  # make inclusive both endpoints for calculations
        while l <= r:
            if _isRightChild(l):
                leftTotal = self.config.mappend(leftTotal, self.accumulations[l])
                l = _rightSibling(l)
            l = _parentNode(l)

            if _isLeftChild(r):
                rightTotal = self.config.mappend(self.accumulations[r], rightTotal)
                r = _leftSibling(r)
            r = _parentNode(r)
        return self.config.mappend(leftTotal, rightTotal)

    def append(self, x: T) -> None:
        assert self.numValues + 1 <= self.MAX_SIZE
        self.numValues += 1
        self.__setitem__(self.numValues - 1, x)

    def pop(self, i: Optional[int] = None) -> T:
        if i is not None:
            raise NotImplementedError
        if not self.numValues:
            raise IndexError
        ret = self.__getitem__(self.numValues - 1)
        self.__delitem__(self.numValues - 1)
        return ret

    def insert(self, i: int, x: T) -> None:
        raise NotImplementedError

    @overload
    def __getitem__(self, index: int) -> T:
        pass

    @overload
    def __getitem__(self, index: slice) -> MutableSequence[T]:
        pass

    def __getitem__(self, index: Union[int, slice]) -> Union[T, MutableSequence[T]]:
        if isinstance(index, slice):
            raise NotImplementedError
        if not 0 <= index < self.numValues:
            raise IndexError
        ret = self.values[index]
        assert ret is not None
        return ret

    @overload
    def __setitem__(self, i: int, x: T) -> None:
        pass

    @overload
    def __setitem__(self, i: slice, x: Iterable[T]) -> None:
        pass

    def __setitem__(self, i: Union[int, slice], x: Union[T, Iterable[T]]) -> None:
        if isinstance(i, slice):
            raise NotImplementedError
        # int index always correspond with T x
        # Can't just check `isinstance(x, Iterable)` because x can be stuff like str
        x = cast(T, x)
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = x
        self.accumulations[index] = self.config.mconvert(x)
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
            parent = _parentNode(parent)

    @overload
    def __delitem__(self, i: int) -> None:
        pass

    @overload
    def __delitem__(self, i: slice) -> None:
        pass

    def __delitem__(self, i: Union[int, slice]) -> None:
        if isinstance(i, slice):
            raise NotImplementedError
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = None
        self.accumulations[index] = self.config.mempty()
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
        self.numValues -= 1

    def __len__(self) -> int:
        return self.numValues


def charToBitmask(c):
    return 1 << (ord(c) - ord("a"))


def popcount(n):
    # Python doesn't have __builtin_popcount
    return bin(n).count("1")


N, = list(map(int, input().split()))
S = [charToBitmask(c) for c in input().rstrip()]
Q, = list(map(int, input().split()))
queries = []
for i in range(Q):
    queries.append(input().split())


segTree = SegmentTree(S, lambda x: x, lambda mask1, mask2: mask1 | mask2, lambda: 0)
out = []
for query in queries:
    if query[0] == "1":
        _, i, c = query
        i = int(i) - 1
        segTree[i] = charToBitmask(c)
    elif query[0] == "2":
        _, l, r = query
        l = int(l) - 1
        r = int(r) - 1
        mask = segTree.query(l, r + 1)

        out.append(str(popcount(mask)))
print("\n".join(out))