线段树（Python）

思路：多次修改，多次查询的区间问题，要想到用线段树解决

注意：对于Python来说，print函数的时间代价很大，所以说像这种多次查询并输出的题目，我们需要用一个数组来记录每次要输出的答案，最终用一次print输出，来减少超时的风险

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

class LazySegmentTree:

    def __init__(self, arr):
        if isinstance(arr, int):
            arr = [0] * arr
        self.n = len(arr)
        self.size = 1 << (self.n - 1).bit_length()

        self.val = [0] * (2 * self.size)
        self.todo = [0] * (2 * self.size)

        for i in range(self.n):
            self.val[self.size + i] = arr[i]

        for i in range(self.size - 1, 0, -1):
            self.val[i] = self.val[2 * i] + self.val[2 * i + 1]

    def _apply(self, node, l, r, tag):
        """应用标记到节点"""
        if tag:
            self.val[node] = (r - l + 1) - self.val[node]
            self.todo[node] ^= 1

    def _push(self, node, l, r):
        """下传标记"""
        if self.todo[node]:
            mid = (l + r) // 2
            self._apply(2 * node, l, mid, self.todo[node])
            self._apply(2 * node + 1, mid + 1, r, self.todo[node])
            self.todo[node] = 0

    def update(self, ql, qr):
        """区间翻转"""
        def _update(node, l, r):
            if ql > r or qr < l:
                return
            if ql <= l and r <= qr:
                self._apply(node, l, r, 1)
                return
            self._push(node, l, r)
            mid = (l + r) // 2
            _update(2 * node, l, mid)
            _update(2 * node + 1, mid + 1, r)
            self.val[node] = self.val[2 * node] + self.val[2 * node + 1]

        _update(1, 0, self.size - 1)

    def query(self, ql, qr):
        """查询区间1的个数"""
        def _query(node, l, r):
            if ql > r or qr < l:
                return 0
            if ql <= l and r <= qr:
                return self.val[node]
            self._push(node, l, r)
            mid = (l + r) // 2
            left = _query(2 * node, l, mid)
            right = _query(2 * node + 1, mid + 1, r)
            return left + right

        return _query(1, 0, self.size - 1)

def solve():
    n, q = MII()
    s = I()

    arr = [int(c) for c in s]
    st = LazySegmentTree(arr)

    out_lines = []
    for _ in range(q):
        op, l, r = MII()
        l -= 1
        r -= 1
        if op == 1:
            st.update(l, r)
        else:
            out_lines.append(str(st.query(l, r)))

    print("\n".join(out_lines))

t = 1
# t = II()
for _ in range(t):
    solve()