Problem:


Range Sum Query

Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

add(i, x): add x to ai.

getSum(s, t): print the sum of as, as+1,...,at.

Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Input

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, q queries are given where com represents the type of queries. '0' denotes add(xi, yi) and '1' denotes getSum(xi, yi).

Output

For each getSum operation, print the sum in a line.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

If comi is 0, then 1 ≤ xi ≤ n, 0 ≤ yi ≤ 1000.

If comi is 1, then 1 ≤ xi ≤ n, 1 ≤ yi ≤ n.

Sample Input 1

3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

Sample Output 1

3
2



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


Sample output:
3
2

Submission status: Accepted

Solution code:
import time

class segTree:
    size = 0
    data = []
    __unitElement = 0
    __tree = []
    __totalSize = 0
    
    def __init__(self, inputData):
        self.data = inputData
        tmp = 1
        while tmp < len(inputData):
            tmp *= 2
        self.size = tmp
        self.__totalSize = 2*self.size-1
        self.__tree = [self.__unitElement]*self.__totalSize
        for i in range(len(inputData)):
            self.change(i, inputData[i])
    
    def change(self, i, x):
        self.data[i] = x
        cur = self.size-1+i
        self.__tree[cur] = x
        while True:
            cur = cur-1
            if cur < 0:
                break
            cur = cur//2
            # change this line when needed
            self.__tree[cur] = self.__tree[2*cur+1] + self.__tree[2*cur+2]
  

    def __queryBody(self, i, a, b, left, right):
        if right <= a or b <= left: # no intersection
            return self.__unitElement
        elif a <= left and right <= b:
            return self.__tree[i]
        else:
            mid = (left+right)//2
            child1 = self.__queryBody(2*i+1, a, b, left, mid)
            child2 = self.__queryBody(2*i+2, a, b, mid, right)
            return child1 + child2 # change here if needed
            
    # query about [a,b)
    def query(self, a, b):
        return self.__queryBody(0, a, b, 0, self.size)
        
## definition of segTree ended


n, q = map(int, input().split())
s = segTree([0]*n)  

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        cur = s.data[x-1]
        s.change(x-1, cur+y)
    else:
        print(s.query(x-1, y))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections,math
sys.setrecursionlimit(1000000)

INF = 2**31-1

N,Q = map(int,sys.stdin.readline().split())
COM = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param
i = 1
while i < N:
    i*=2
N = i
MAX_N = 1 << math.ceil(math.log2(N)) # 17
SEG = [0]*(2*MAX_N-1)
#print(N,Q,SEG)
def update(k,a):#0 indexed
    #print(k,a)
    k += N-1
    SEG[k] += a
    while k > 0:
        k = (k-1)//2
        SEG[k] = SEG[k*2+1]+SEG[k*2+2]

def find(a,b,i=0,l=0,r=N):#0 indexed
    #print(i,a,b,l,r)
    if r <= a or  b <= l:
        return 0
    if a <= l and r <= b:
        return SEG[i]
    vl = find(a,b,2*i+1,l,(r+l)//2)
    vr = find(a,b,2*i+2,(r+l)//2,r)
    return vl+vr

#print(N,Q)
for com,x,y in COM:
    if com == 0:
        update(x-1,y)
        #print(0,x,y,SEG)
    else:
        print(find(x-1,y))
        #print(1,x-1,y,SEG)

Submission status: Accepted

Solution code:
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 sum_range(self, x, y):
        return self.sum(y) - self.sum(x - 1)
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


if __name__ == '__main__':
    n, q = map(int, input().split())
    bit = Bit(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            bit.add(x, y)
        else:
            print(bit.sum_range(x, y))

Submission status: Accepted

Solution code:
def main():
	import sys
	input=sys.stdin.readline
	n,q=map(int,input().split())
	seg=[]
	cnt=-1
	inf=2**31-1
	while 2**cnt<=n:
		cnt+=1
		seg.append([0 for _ in range(2**cnt)])
	#seg tree 初期化
	def f(i,j):
		Range=(2**(cnt-i)*j,2**(cnt-i)*(j+1)-1)
		if Range[0]>y or Range[1]<x:
			return 0
		elif Range[0]>=x and Range[1]<=y:
			return seg[i][j]
		else:
			return f(i+1,2*j)+f(i+1,2*j+1)
	for _ in range(q):
		c,x,y=map(int,input().split())
		if c==0:
			seg[-1][x]+=y
			x//=2
			for j in range(1,cnt+1):
				seg[-j-1][x]=seg[-j][x*2]+seg[-j][x*2+1]
				x//=2
		else:
			print(f(0,0))
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
bit = [0]*(N+1)
'''
def add(a,w):
    ret = 0
    for i in range(a,0,-(i&-i)):ret += bit[i]
    return ret
'''
def add(a,w):
    x = a
    while x<=N:
        bit[x]+=w
        x+=x&-x
def bsum(a):
    ret = 0
    x = a
    while x>0:
        ret+=bit[x]
        x-=x&-x
    return ret

for i in range(Q):
    l = list(map(int,input().split()))
    if l[0] == 0:
        add(l[1],l[2])
    else:
        print(bsum(l[2])-bsum(l[1]-1))

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return x + y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n, q = [int(x) for x in input().split()]
seg = SegTree([0]*n, segfunc, ide_ele)
for _ in range(q):
    com, x, y = [int(x) for x in input().split()]
    if com:
        print(seg.query(x - 1, y))
    else:
        x -= 1
        y += seg.tree[seg.num + x]
        seg.update(x, y)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2-1)
        self.f = f

    def update(self, i, x):
        i += self.size-1
        self.dat[i] = x
        while i > 0:
            i = (i-1) >> 1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return self.f(lres, rres)

n, q = map(int, input().split())
s = SegmentTree(n)
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        i = x-1
        s.update(i, s.query(i,i+1)+y)
    else:
        print(s.query(x-1, y))

Submission status: Accepted

Solution code:
"""
Segment-Tree
    maxval:入力されるデータ以上の値
    offset:根と枝の数(n=1のときは根1つ葉2つの木)
    init_array(array):配列で初期化
    update(k,x):k番目をxに変更
    min_query(p,q):[p,q)の範囲の最小値
"""
class SegmentTree():
    def __init__(self,n):
        self.offset=self.setOffset(n)
        self.segTree=[0]*(2*self.offset+1)

    def init_array(self,array):
        for i in range(len(array)):
            self.segTree[i+self.offset]=array[i]
        for i in range(offset-1,-1,-1):
            self.segTree[i]=self.sumChild(i)

    def setOffset(self,n):
        if n==1:
            return 1
        else:
            return 2**(n-1).bit_length()-1

    def update(self,k,x):
        k+=self.offset
        self.segTree[k]+=x
        while k:
            k=(k-1)//2
            self.segTree[k]+=x

    def sum_query(self,p,q):
        if p>=q:
            return

        p+=self.offset
        q+=self.offset-1
        segsum=0

        while q-p>1:
            #p%2==0
            if not p&1:
                segsum+=self.segTree[p]
            #q%2==1
            if q&1:
                segsum+=self.segTree[q]
                q-=1
            p=p//2
            q=(q-1)//2

        if p==q:
            return segsum+self.segTree[p]
        else:
            return segsum+self.segTree[p]+self.segTree[q]

    def sumChild(self,n):
        return self.segTree[2*n+1]+self.segTree[2*n+2]

    def show(self):
        print(self.segTree)

n,q=map(int,input().split())
ST=SegmentTree(n)
for i in range(q):
    qry=list(map(int,input().split()))
    if qry[0]==0:
        ST.update(qry[1]-1,qry[2])
    else:
        print(ST.sum_query(qry[1]-1,qry[2]))

Submission status: Accepted

Solution code:
#AOJ DSL_2_B
class BIT:
    #n:要素数
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    #i番目(0-indexed)の値にxを足す
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    #0からi番目までの値の和を求める
    def acc(self, i):
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

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

for _ in range(q):
    c, x, y = map(int, input().split())
    
    if c==0:
        bit.add(x-1, y)
    else:
        print(bit.acc(y-1)-bit.acc(x-2))

Submission status: Accepted

Solution code:
class RSQ:
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.st = [0]*(2*self.n-1)
    
    def update(self,k,x):
        k+=(self.n-1)
        self.st[k] += x
        while k >0:
            k = (k-1)//2
            self.st[k] = self.st[2*k+1]+self.st[2*k+2]

    def search(self,a,b,k,l,r):
        if r<=a or b<=l :return 0
        if a<=l and r<=b:return self.st[k]
        L = self.search(a,b,k*2+1,l,(l+r)//2)
        R = self.search(a,b,k*2+2,(l+r)//2,r)
        return L+R

    def query(self,a,b):
        return self.search(a,b,0,0,self.n)

def main():
    n,q = map(int,input().split())
    ST = RSQ(n)
    for _ in range(q):
        a,b,c = map(int,input().split())
        if a == 0:ST.update(b-1,c)
        else     :print (ST.query(b-1,c))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def add(self, idx, w):
        i = idx
        while i < len(self.node) - 1:
            self.node[i] += w
            i |= (i + 1)

    def sum_(self, idx):
        ret, i = 0, idx-1
        while i >= 0:
            ret += self.node[i]
            i = (i & (i + 1)) - 1
        return ret

    def sum(self, l, r):
        return self.sum_(r) - self.sum_(l)

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

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        tree.add(x-1, y)
    if com == 1:
        print(tree.sum(x-1, y))

Submission status: Accepted

Solution code:
class SegmentTree:
    '''
    SegmentTree(arr, e)
        arr : 配列,
        e : 単位元\n
    segment_tree[i] = x で更新\n
    segment_tree[a,b] で区間[a,b)の計算結果を得る(a<bでなければ単位元が返ってくる)
    '''
    def __init__(self, arr, e):
        self.e = e
        self.len = len(arr)
        # 最下層の長さnの初期化(扱う配列の長さ以上の2冪のうち最も小さいもの)
        n = 2 ** (len(bin(self.len + 1)) - 2)
        self.n = n
        # nodeの初期化
        node = [e] * (2 * n)
        node[n: n + self.len] = arr
        for i in range(n - 1, 0, -1):
            node[i] = node[2 * i] + node[2 * i + 1]
        self.node = node


    def __setitem__(self, i, val):
        # 最下層からはじめる。それより上にはn-1個のノードがある
        i += self.n
        self.node[i] = val
        # 最上層に辿り着くまで
        while i > 1:
            # 親に移動
            i //= 2
            # 2つの子に対する計算結果
            self.node[i] = self.node[2 * i] + self.node[2 * i + 1]

    def __getitem__(self, i):
        return self.node[self.n + i]

    def query(self, a, b):
        a = self.trim(a, self.len)
        b = self.trim(b, self.len)

        # [a,b)が欲しい
        # k=0, [l=0,r=n)から始める
        # [l,r)が[a,b)の中に入るまで[l,mid), [mid,r)に分割して再帰
        def get(k, l, r):
            # そもそも[l,r)が[a,b)に入ってない時は計算に影響を与えない単位元を返す
            if r <= a or b <= l:
                return self.e
            if a <= l and r <= b:
                return self.node[k]
            m = (l + r) // 2
            return get(2 * k, l, m) + get(2 * k + 1, m, r)

        return get(1, 0, self.n)


    def getlist(self):
        return self.node[self.n:]

    def trim(self, i, n):
        i = max(i, -n)
        i = min(i, n)
        if i < 0:
            i += n
        return i



# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
n, q = map(int, input().split())
A = [0] * n
st = SegmentTree(A, 0)
for i in range(q):
    com, x, y = map(int, input().split())
    x -= 1
    if com == 0:
        st[x] += y
    else:
        y -= 1
        # print(st[x: y + 1])
        print(st.query(x, y + 1))

Submission status: Accepted

Solution code:
# operator.add(a, b)
# operator.mul(a, b)

"""
https://komiyam.hatenadiary.org/entry/20131202/1385992406
大雑把に言って、平衡二分探索木からinsert,delete,split,mergeなどができないよう制限したのがsegment treeで、
segment treeの区間[L,R)に対するクエリをL=0に制限したのがbinary indexed treeだと見なすことができます。
"""


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)
    

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
def AOJ_DSL_2_A():
    n, q = map(int, input().split())
    e = (1 << 31) - 1
    A = [e] * n
    seg = SegmentTree(A, min, e)

    for i in range(q):
        t, x, y = map(int, input().split())
        if t == 0:
            seg.update(x, y)
        else:
            print(seg.get(x, y + 1))


# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
def AOJ_DSL_2_B():
    from operator import add
    import sys
    n, q = map(int, input().split())
    e = 0
    A = [e] * n
    seg = SegmentTree(A, add, e)
    
    query = sys.stdin.readlines()
    for i in range(q):
        t, x, y = map(int, query[i].split())
        x -= 1
        if t == 0:
            A[x] += y
            seg.update(x, A[x])
        else:
            y -= 1
            print(seg.get(x, y + 1))


def ABC125_C():
    from fractions import gcd
    N = int(input())
    A = list(map(int, input().split()))
    
    seg = SegmentTree(A, gcd, 0)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.get(0, i), seg.get(i + 1, N)))
    print(ans)


# AOJ_DSL_2_A()
AOJ_DSL_2_B()
# ABC125_C()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class BIT:
  # [1,n]に値が入ってる1-indexであることに注意
  def __init__(self,size):
    self.data = [0]*(size+1)
    self.size = size
  
  # [1,n]までの総和
  def sum(self,n):
    res = 0
    while n > 0:
      res += self.data[n]
      n -= n & -n
    return res
  
  def add(self,k,x):
    while k < self.size + 1:
      self.data[k] += x
      k += k & -k

n,q = map(int,input().split())
bit = BIT(n)
for _ in range(q):
  typo,x,y = map(int,input().split())
  if  typo == 0:
    bit.add(x,y)
  else:
    print(bit.sum(y)-bit.sum(x-1))

Submission status: Accepted

Solution code:
"""Range Minimum Query (RMQ)"""
# 丁寧に実装する


# 配列のidx番目の要素の値をxに変更する, 1点更新
def update(idx, x):
    idx += size-1  # 配列のidx番目の要素に対応するseg木のノードのindex
    seg[idx] += x  # 対象のノードの値を更新する
    # 親のノードの値も更新する
    while idx > 0:
        idx = (idx-1)//2  # ノードidxの親のindex, いつか0になる
        seg[idx] = seg[2*idx+1] + seg[2*idx+2]  # 左右の子を見てminを計算する
    # 根ノードであるノード0まで修正したのでreturnする
    return


# この関数は半開区間[a, b)に対するクエリについて最小値を答えるもの
def query(a, b, k, l, r):  # 半開区間[a, b)に対するクエリについて、ノードk(担当している半開区間[l, r))が答える
    # 最初は根に質問を飛ばしている
    if r <= a or b <= l:  # ノードkの担当区間は[l, r)であり、この条件を満たすときは求めたい区間[a, b)と範囲が全く被っていない
        return INF  # 区間が被らない場合は単位元(minの単位元はINF)
    if a <= l and r <= b:
        return seg[k]  # ノードkの担当範囲が求めたい区間[a, b)に完全に含まれる場合はそのノードも持っている値をそのまま返す
    else:
        # 一部だけ範囲が被るような場合は左右の子に委託する
        c1 = query(a, b, 2*k+1, l, (l+r)//2)  # 左の子に値を聞く
        c2 = query(a, b, 2*k+2, (l+r)//2, r)  # 右の子に値を聞く
        return c1 + c2  # 左右の子のminを取る


N, Q = map(int, input().split())  # 配列のサイズ(管理したい要素の数), クエリの個数
size = 1  # seg木の葉の個数
while N > size:
    size *= 2  # seg木の葉の個数を計算する, N以上の最小の2冪数, 末端に来る葉の数が2の冪数でないと、seg木の構造がおかしくなる

# 単位元
# INF = float('inf')
INF = 0  # 今回の問題設定
# seg木を単位元で初期化する
seg = [INF]*(2*size-1)

for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        x -= 1
        update(x, y)
    else:
        x -= 1
        y -= 1
        print(query(x, y+1, 0, 0, size))  # ノード0(担当している半開区間[0, size))にクエリを投げる
        # y+1としているのは、半開区間とかの関係

Submission status: Accepted

Solution code:
# Range Sum Query
# https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B
"""
Binary Indexed Tree (Fenwick Tree)

References:
    http://hos.ac/slides/20140319_bit.pdf

Verified:
    https://judge.yosupo.jp/problem/point_add_range_sum
    https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
"""
from typing import Optional, Sequence


class BinaryIndexedTree:
    __slots__ = ["_size", "_tree", "_is_zero_indexed"]

    def __init__(self, size: int, initial_values: Optional[Sequence[int]] = None, is_zero_indexed: bool = True):
        self._size = size
        self._tree = [0] * (self._size + 1)
        self._is_zero_indexed = is_zero_indexed
        if initial_values:
            self._build(initial_values)

    def _build(self, initial_values: Sequence[int]):
        for i, a in enumerate(initial_values):
            self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self._is_zero_indexed:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index], O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right], O(logN)."""
        if not self._is_zero_indexed:
            left -= 1
        return self.sum(right) - self.sum(left)


def main():
    N, Q, *queries = map(int, open(0).read().split())
    tree = BinaryIndexedTree(N, is_zero_indexed=False)
    result = []
    for com, x, y in zip(*[iter(queries)] * 3):
        if com:
            result.append(tree.range_sum(x, y))
        else:
            tree.add(x, y)
    print(*result, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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


class SegmentTree0():
    """
    0-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n - 1)  # binary tree (0-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    def __getitem__(self, i):
        return self.data[i + self.n - 1]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]  # set data in leaf
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def update(self, i, x):
        # change i-th element to x (i : 0-indexed)
        i += self.n - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def query(self, a, b):
        # query for interval [a, b) (a, b : 0-indexed)
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            # [a, b) and [l, r) have no intersection
            return self.ele_id
        if a <= l and r <= b:
            # [a, b) includes [l, r)
            return self.data[k]
        else:
            # [a, b) and [l, r) have some overlap
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.op_func(child_l, child_r)


n, q = map(int, input().split())
ele_id = 0
op_func = lambda a, b: a + b
st_rsq = SegmentTree0(n, ele_id, op_func)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        x -= 1
        st_rsq.update(x, st_rsq[x] + y)
    elif com == 1:
        x -= 1
        y -= 1
        ans = st_rsq.query(x, y + 1)
        print(ans)

Submission status: Accepted

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()
    A = [0] * (N+1)
    la = N + 1

    def add(i, x):
        while i < la:
            A[i] += x
            i += i & -i

    def getSum(i):
        ans = 0

        while i:
            ans += A[i]
            i -= i & -i

        return ans

    ans = []
    for com, *arg in (map(int, line.split()) for line in sys.stdin):
        if com == 0:
            add(*arg)
        else:
            #print("+", *arg)
            ans.append(getSum(arg[1]) - getSum(arg[0]-1))
        #print(A)
    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class SegTreeSum:
    '''
    0-indexedで実装していることに注意
    '''

    def __init__(self, V):
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2

        self.N = N
        self.node = [0] * (2 * self.N - 1)
        
        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]
        
        for i in range(self.N - 2, 0, -1):
            # 親から子ノードへアクセスする
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]
    
    def add(self,i,x):
        i += (self.N - 1)
        self.node[i] += x

        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]

    def getsum(self,a,b,k=0,l=0,r=-1):
        if r < 0:
            r = self.N
        
        if b <= l or a >= r:
            return 0
        
        if a <= l and b >= r:
            return self.node[k]

        vl = self.getsum(a,b, 2*k+1, l, (l+r)//2)
        vr = self.getsum(a,b, 2*k+2, (l+r)//2, r)
        return vl + vr

def main():
    n,q = map(int, input().split())
    V = [0] * n
    seg = SegTreeSum(V)
    for _ in range(q):
        com, x, y = map(int, input().split())
        x -= 1
        if com:
            print(seg.getsum(x,y))
        else:
            seg.add(x,y)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


N,Q = map(int,input().split())
BIT = [0]*(N+1)

def add(loc,value):
    global N
    BIT[loc] += value

    loc += loc & -loc

    while loc <= N:
        BIT[loc] += value
        loc += loc & -loc


def getSum(loc):
    ret = BIT[loc]
    loc -= loc & -loc

    while loc > 0:
        ret += BIT[loc]
        loc -= loc & -loc

    return ret


def calc(left,right):
    return getSum(right)-getSum(left-1)


for _ in range(Q):
    command,left,right = map(int,input().split())

    if command == 0:
        add(left,right)
    else:
        print("%d"%(calc(left,right)))

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_B
import sys
input = sys.stdin.readline

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

class RMQ:
    def __init__(self, n, e):
        # 単位元
        self.e = e
        # num_min:n以上の最小の2のべき乗
        self.num_min =2**(n-1).bit_length()
        self.seg=[self.e]*2*self.num_min

    def initialize(self, init):
        #初期値が指定されている場合
        #set_val
        for i in range(n):
            self.seg[i+self.num_min-1]=init[i]
        #built
        for i in range(self.num_min-2,-1,-1) :
            self.seg[i]=min(self.seg[2*i+1],self.seg[2*i+2])

    def update(self, k, x):
        k += self.num_min-1
        self.seg[k] += x
        while k:
            k = (k-1)//2
            self.seg[k] = self.seg[k*2+1] + self.seg[k*2+2]

    def query(self, p, q):
        q += 1
        if q<=p:
            return self.e
        p += self.num_min-1
        q += self.num_min-2
        res=self.e
        while q-p>1:
            if p&1 == 0:
                res += self.seg[p]
            if q&1 == 1:
                res += self.seg[q]
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res += self.seg[p]
        else:
            res += self.seg[p] + self.seg[q]
        return res

e = 0
rmq = RMQ(n, e)

for i in range(q):
    com, x, y = map(int, input().split())
    x -= 1
    if com == 0:
        rmq.update(x, y)
    else:
        y -= 1
        ans = rmq.query(x, y)
        print(ans)

Submission status: Accepted

Solution code:
SEG_LEN = 1 << 18

seg = [0 for i in range(2*SEG_LEN)]

def add(ind, v):
    ind += SEG_LEN
    seg[ind] += v
    while True:
        ind //= 2
        if ind == 0:
            break
        seg[ind] = seg[ind*2] + seg[ind*2+1]

def sum(l, r):
    l += SEG_LEN
    r += SEG_LEN
    ans = 0
    while l < r:
        if (l % 2 == 1):
            ans += seg[l]
            l += 1
        l //= 2
        if r % 2 == 1:
            ans += seg[r-1]
            r -= 1
        r //= 2
    return ans


def main():
    n, q = map(int, input().split())
    ans = []
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            add(x, y)
        elif com == 1:
            ans.append(sum(x, y+1))
    for i in range(len(ans)):
        print(ans[i])

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class segmentTreeSum():
    initValue = 0
    dat = []
    lenData = -1

    def __init__(self):
        pass

    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenData = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.dat = [self.initValue] * (self.lenData * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenData - 1 + i] = l[i]
        self.build()

    def build(self):
        for i in range(self.lenData - 2, -1, -1):
            self.dat[i] = self.dat[2 * i + 1] + self.dat[2 * i + 2]

    # 若干無駄なインストラクションあるのでコードレベルでマージしたほうがいいかも
    def addValue(self, i, a):
        nodeId = (self.lenData - 1) + i
        self.dat[nodeId] += a
        self.setValue(i, self.dat[nodeId])

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        #print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenData - 1) + i
        #print(" first nodeId: {0}".format(nodeId))
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            #print(" next nodeId: {0}".format(nodeId))
            self.dat[nodeId] = self.dat[nodeId * 2 + 1] + self.dat[nodeId * 2 + 2]

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        if (r <= a or b <= l):
            return self.initValue
        if a <= l and r <= b:
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        return resLeft + resRight

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenData)

initVal = 0
n, q = map(int, input().split())
dat = [initVal] * n
st = segmentTreeSum()
st.load(dat)
st.build()
#print(st.dat)
for _ in range(q):
    # indexの入力が1 originなので注意 (以下で-1しているのはそのため)
    cmd, a, b = map(int, input().split())
    if cmd == 0: # update
        st.addValue(a - 1, b)
    else:
        print(st.query(a - 1 , b + 1 -1))