提出 #26325029

---

ソースコード 拡げる

import sys
input = sys.stdin.readline
import logging

logger = logging.getLogger(__name__)
import numpy as np
from numba import njit, jitclass, i8


@jitclass([("n", i8), ("tree", i8[:])])
class FenwickTree:
    def __init__(self, n: i8) -> None:
        """Fenwick Treeを初期化します。

        Parameters
        ----------
        n : i8
            要素数
        """
        self.n = n
        self.tree = np.zeros(n + 1, dtype=np.int64)
    
    def _rsum(self, r):
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r
        return s

    def sum(self, l: i8, r: i8) -> i8:
        """区間[l, r) の総和を返します。

        Parameters
        ----------
        l : i8
            区間の左端
        r : i8
            区間の右端

        Returns
        -------
        i8
            区間[l, r) の総和
        """
        return self._rsum(r) - self._rsum(l)

    def add(self, i: i8, x: i8) -> None:
        """添字iにxを加算します。

        Parameters
        ----------
        i : i8
            添字
        x : i8
            加数
        """
        i += 1
        while i <= self.n:
            self.tree[i] += x
            i += i & -i


def read():
    N, Q = map(int, input().strip().split())
    A = np.fromstring(input().strip(), sep=" ", dtype=np.int64)
    queries = np.empty((Q, 3), dtype=np.int64)
    for i in range(Q):
        queries[i, :] = np.fromstring(input().strip(), sep=" ", dtype=np.int64)
    return N, Q, A, queries


@njit((i8, i8, i8[:], i8[:, :]), cache=True)
def solve(N, Q, A, queries):
    ft = FenwickTree(N)
    for i in range(N):
        ft.add(i, A[i])
    for i in range(Q):
        query = queries[i, :]
        if query[0] == 0:
            p, x = query[1:]
            ft.add(p, x)
        elif query[0] == 1:
            l, r = query[1:]
            print(ft.sum(l, r))


if __name__ == '__main__':
    logging.basicConfig(level=logging.ERROR)
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

提出情報

ジャッジ結果