Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 p x: a_p \gets a_p + x

1 l r: Print \sum_{i = l}^{r - 1}{a_i}.

Constraints

1 \leq N, Q \leq 500,000

0 \leq a_i, x \leq 10^9

0 \leq p < N

0 \leq l_i < r_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Sample Output 1

15
7
25
6



Sample input:
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3


Sample output:
15
7
25
6

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline






def main():
    def segfunc(x, y):
        return x + y

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    # seg tree初期値 (単位元)
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    for _ in range(Q):
        q, p, x = [int(x) for x in input().split()]
        if q == 0:
            A[p] += x
            update(p, A[p])
        else:
            print(query(p, x))





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))

bit = BinaryIndexedTree(N)
res = list()

for i, a in enumerate(A):
    bit.add(i + 1, a)

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q == 0:
        bit.add(x + 1, y)
    else:
        res.append(bit.sum(y) - bit.sum(x))

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

from sys import stdin
input = stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))

bit = BinaryIndexedTree(N)
res = list()

for i, a in enumerate(A):
    bit.add(i + 1, a)

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q == 0:
        bit.add(x + 1, y)
    else:
        res.append(bit.sum(y) - bit.sum(x))

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

from sys import stdin
input = stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))

bit = BinaryIndexedTree(N)
res = list()

for i in range(N):
    bit.add(i + 1, A[i])

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q == 0:
        bit.add(x + 1, y)
    else:
        res.append(bit.sum(y) - bit.sum(x))

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=lambda self,a,b:a+b  # 関数
    def __init__(self,n,seq):
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def fold(self,l,r): # 区間[l, r)の合計を取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)

n,q=map(int,input().split())
*a,=map(int,input().split())
seg=segtree(n,a) 
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        old=seg.fold(x,x+1)
        seg.update(x, old+y)
    else:
        print(seg.fold(x, y))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=lambda self,a:a[0]+a[1]  # 関数
    def __init__(self,n,seq):
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func([self.x[i*2], self.x[i*2+1]])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func([self.x[i*2], self.x[i*2+1]])
    def fold(self,l,r): # 区間[l, r)の合計を取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func([val_l,self.x[l]])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func([val_r,self.x[r]])
            l //= 2
            r //= 2
        return self.x_func([val_l,val_r])

n,q=map(int,input().split())
*a,=map(int,input().split())
seg=segtree(n,a) 
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        old=seg.fold(x,x+1)
        seg.update(x, old+y)
    else:
        print(seg.fold(x, y))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=sum  # 関数
    def __init__(self,n,seq):
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func([self.x[i*2], self.x[i*2+1]])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func([self.x[i*2], self.x[i*2+1]])
    def fold(self,l,r): # 区間[l, r)の合計を取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func([val_l,self.x[l]])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func([val_r,self.x[r]])
            l //= 2
            r //= 2
        return self.x_func([val_l,val_r])

n,q=map(int,input().split())
*a,=map(int,input().split())
seg=segtree(n,a) 
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        old=seg.fold(x,x+1)
        seg.update(x, old+y)
    else:
        print(seg.fold(x, y))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x): # 0-indexedで[i]にxを足す
        # assert i > 0
        newi=i+1
        self.el[newi] += x
        while newi <= self.n:
            self.data[newi] += x
            newi += newi & -newi
    def get(self, i, j=None): # [i,j)の部分和
        if j is None:
            i-=1
            return self.el[i]
        return self.sum(j) - self.sum(i)

n,q=map(int,input().split())
*a,=map(int,input().split())
bit=BIT(n) # BITによる配列を作成
for i in range(n):
    bit.add(i, a[i])
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        bit.add(x, y)
    else:
        print(bit.get(x, y))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                    s += self.bit[k]
                    pos += v
            v >>= 1
        return pos

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, q = map(int, input().split())
A = list(map(int, input().split()))
bit = BIT(n)
bit.init(A)
for i in range(q):
    t, a, b = map(int, input().split())
    if t == 0:
        bit.add(a, b)
    else:
        print(bit.sum(a, b))

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree:
 
    def __init__(self,n):
        self.size=n
        self.graph=[0]*(n+1)
 
    def partially_sum(self,i):
        res=0
        while i>0:
            res+=self.graph[i]
            i-=i&-i
        return res
 
    def add_element(self,i,x):
        while self.size>=i:
            self.graph[i]+=x
            i+=i&-i
    
    def ret_sum(self,l,r):
        return self.partially_sum(r)-self.partially_sum(l)
    
n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = Binary_Indexed_Tree(n)

for i,x in enumerate(a):
    bit.add_element(i+1,x)
    
for i in range(q):
    t, L, R = map(int,input().split())
    if t == 0:
        bit.add_element(L+1,R)
    else:
        ans = bit.ret_sum(L,R)
        print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    FENWICK_TREE = []
    FENWICK_LOGN = []

    def fenwick_init(n):
        log_n = 0
        m = n
        while m:
            log_n += 1
            m >>= 1
        FENWICK_TREE.append(np.zeros(n + 1, dtype=np.int64))
        FENWICK_LOGN.append(log_n)
        return len(FENWICK_TREE) - 1

    def fenwick_add(ins, i, x):
        arr = FENWICK_TREE[ins]
        n = arr.size - 1
        while i <= n:
            arr[i] += x
            i += i & -i

    def fenwick_sum(ins, i):
        arr = FENWICK_TREE[ins]
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    def fenwick_lower_bound(ins, x):
        arr = FENWICK_TREE[ins]
        log_n = FENWICK_LOGN[ins]
        n = arr.size - 1
        sum_ = 0
        pos = 0
        for i in range(log_n, -1, -1):
            k = pos + (1 << i)
            if k < n and sum_ + arr[k] < x:
                sum_ += arr[k]
                pos += 1 << i
        return pos + 1

    n = inp[0]
    q = inp[1]
    aaa = inp[2:2 + n]
    ooo = inp[2 + n::3]
    lll = inp[3 + n::3]
    rrr = inp[4 + n::3]
    buf = []

    bid = fenwick_init(n)
    for i in range(n):
        fenwick_add(bid, i + 1, aaa[i])
    for i in range(q):
        if ooo[i] == 0:
            fenwick_add(bid, lll[i] + 1, rrr[i])
        else:
            buf.append(fenwick_sum(bid, rrr[i]) - fenwick_sum(bid, lll[i]))
    return buf


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N,Q=map(int,input().split())
bit=BIT(N)
a=list(map(int,input().split()))
for i in range(N):
    bit.add(i+1,a[i])
for _ in range(Q):
    c,A,B=map(int,input().split())
    if c==0:
        bit.add(A+1,B)
    else:
        A,B=A+1,B+1
        print(bit.cum(A,B))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        # [l,r)の和
        def sum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_
        
    N,Q=MI()
    bit=BIT(N)
    A=LI()
    for i in range(N):
        bit.add(i,A[i])
    
    for _ in range(Q):
        t,p,x=MI()
        if t==0:
            bit.add(p,x)
        else:
            print(bit.sum(p,x))
            
            

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, n: int) -> None:
        self._n = n
        self.data = [0] * n

    def add(self, p: int, x) -> None:
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def __sum__(self, r: int):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def sum(self, l: int, r: int):
        assert 0 <= l <= r <= self._n
        return self.__sum__(r) - self.__sum__(l)


n, q = map(int, input().split())

fw = FenwickTree(n)
for index, i in enumerate(map(int, input().split())):
    fw.add(index, i)

for _ in range(q):
    t, p, x = map(int, input().split())
    if t == 0:
        fw.add(p, x)
    else:
        print(fw.sum(p, x))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

class Binary_Indexed_Tree:

    def __init__(self,n):
        self.size=n
        self.graph=[0]*(n+1)

    def partially_sum(self,i):
        res=0
        while i>0:
            res+=self.graph[i]
            i-=i&-i
        return res

    def add_element(self,i,x):
        while self.size>=i:
            self.graph[i]+=x
            i+=i&-i
    
    def ret_sum(self,l,r):
        return self.partially_sum(r)-self.partially_sum(l)

n,q=map(int,input().split())
t=Binary_Indexed_Tree(n)

for i,x in enumerate(input().split(),1):
    t.add_element(i,int(x))

for _ in range(q):
    a,b,c=map(int,input().split())
    if a:
        print(t.ret_sum(b,c))
    else:
        t.add_element(b+1,c)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from operator import add
def resolve():
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    tree = SegmentTree(A, add, 0)

    for _ in range(q):
        t, l, r = map(int, input().split())
        if t == 0:
            tree.add(l, r)
        else:
            print(tree.sum(l, r))
resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class BIT:
    """ 1-indexで使用しないと無限ループするので注意 """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, idx, x):
        """ idx番目にxをO(logN)で加算する """
        while idx <= self.n:
            self.bit[idx] += x
            idx += idx & (-idx)

    def query(self, idx):
        """ 1 ~ idx番目までの区間和をO(logN)で返す """
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def sec_sum(self, left, right):
        """ left ~ right番目までの区間和をO(logN)で返す """
        return self.query(right) - self.query(left - 1)

    def lower_bound(self, w):
        """ 区間和がw以上になる最小のindexをO(logN)で返す """
        if w <= 0:
            return 0
        x = 0
        k = 1 << self.n.bit_length()
        while k:
            if x + k <= self.n and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

    def debug(self):
        """ bitの状態を出力する """
        print(*[self.sec_sum(i, i) for i in range(1, self.n + 1)])


def resolve():
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    bit = BIT(n)
    for i in range(1, n + 1):
        bit.update(i, A[i - 1])

    for _ in range(q):
        t, *query = map(int, input().split())
        if t == 0:
            p, x = query
            bit.update(p + 1, x)
        else:
            l, r = query
            print(bit.sec_sum(l + 1, r))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def __getitem__(self, key):
        return self.__tree[key + self.__size]
@mt
def slv(N, A, Q):
    st = SegmentTree(A, add, 0)
    ans = []
    for q in Q:
        if q[0] == 0:
            _, p, x = q
            st.update(p, st[p]+x)
        else:
            _, l, r = q
            ans.append(st.query(l, r))

    return ans


def main():
    N, Q = read_int_n()
    A = read_int_n()
    Q = [read_int_n() for _ in range(Q)]
    print(*slv(N, A, Q), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
    
    def make(self, list):
        self.tree[1:] = list.copy()
        for i in range(self.size+1):
            j = i + (i & (-i))
            if j < self.size+1:
                self.tree[j] += self.tree[i]
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = BIT(n)
bit.make(a)
for i in range(q):
    t,l,r = map(int,input().split())
    if t == 0:
        bit.add(l,r)
    else:
        print(bit.sum(r)-bit.sum(l))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
    
    def make(self, list):
        self.tree[1:] = list.copy()
        for i in range(self.size+1):
            j = i + (i & (-i))
            if j < self.size+1:
                self.tree[j] += self.tree[i]
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = BIT(n)
bit.make(a)
for i in range(q):
    t,l,r = map(int,input().split())
    if t == 0:
        bit.add(l,r)
    else:
        print(bit.sum(r)-bit.sum(l))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

# UnionFind
class FenwickTree:
  def __init__(self,n):
    self.n=n
    self.bit=[0]*(n+1)
  def add(self,i,x):
    i+=1
    while i<=n:
      self.bit[i]+=x
      i+=i&-i
  def sumsub(self,r):
    ans=0
    while r:
      ans+=self.bit[r]
      r-=r&-r
    return ans
  def sum(self,l,r):
    ans=self.sumsub(r)
    if l!=0:ans-=self.sumsub(l)
    return ans

n,q=map(int,input().split())
a=list(map(int,input().split()))
ft=FenwickTree(n)
for i in range(n):ft.add(i,a[i])
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    ft.add(a,b)
  else:
    print(ft.sum(a,b))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
n, q = map(int, input().split())
bit = Bit(n)
alst = list(map(int, input().split()))
for i, a in enumerate(alst, start = 1):
    bit.add(i, a)
for _ in range(q):
    qq = list(map(int, input().split()))
    if qq[0] == 0:
        bit.add(qq[1] + 1, qq[2])
    else:
        print(bit.sum(qq[2]) - bit.sum(qq[1]))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = BIT(n)
for i,x in enumerate(a):
    bit.add(i,x)
for i in range(q):
    t,l,r = map(int,input().split())
    if t == 0:
        bit.add(l,r)
    else:
        print(bit.sum(r)-bit.sum(l))