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 sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class BIT(object):
    def __init__(self, size: int):
        self.bitree = [0]*(size+1)
        
    def setval(self, idx:int, val:int):
        tree = self.bitree
        nex_idx = idx+1
        
        while nex_idx < len(tree):
            tree[nex_idx] += val
            nex_idx += nex_idx & -nex_idx
            
    def getsum(self, idx: int):
        tree, result = self.bitree, 0
        nex_idx = idx+1
        
        while nex_idx:
            result += tree[nex_idx]
            nex_idx -= nex_idx & -nex_idx
            
        return result
    
n,q = li()
bitree = BIT(n)

for _ in range(q):
    com, x, y = li()
    if com == 0:
        bitree.setval(x-1, y)
    else:
        print(bitree.getsum(y-1) - bitree.getsum(x-2))

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i: int):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i: int, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

N, Q = map(int, input().split())
bit = Bit(N+1)
for i in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        bit.add(x, y)
    else:
        print(bit.sum(y+1) - bit.sum(x))

Submission status: Accepted

Solution code:
from array import array
import bisect
import collections
import heapq
import itertools
import operator
import sys


class BIT:
    def __init__(self, n):
        self.n = n
        self.arr = array("l", [0] * (n + 1))

    def __str__(self):
        return str(self.arr.tolist())

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

    def sum(self, i, j=None):
        if j is None:
            s = 0
            while i > 0:
                s += self.arr[i]
                i -= i & -i
            return s

        if i > j:
            raise ValueError

        return self.sum(j) - self.sum(i - 1)


def main():
    n, q = map(int, sys.stdin.readline().split())
    bit = BIT(n)

    for _ in range(q):
        query, x, y = map(int, sys.stdin.readline().split())
        if query == 0:
            bit.add(x, y)
        elif query == 1:
            print(bit.sum(x, y))
        else:
            raise ValueError


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))
b = []
ss = 1
f = 0
for i in range(a[0]):
	k = int(input())
	ss*= k
	b.append(ss)
	if k == 0:
		print(a[0])
		f = 1
		break

k = 0
ss = 0
if f == 0:
	for i in range(a[0]):
		for j in range(a[0]-i):
			k = b[a[0]-1-j] / b[i]
			if k <= a[1]:
				if a[0]-j-i >= ss:
					ss = a[0]-i-j

print(ss)

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))
b = [0]*a[0]

for i in range(a[1]):
	c = list(map(int,input().split()))
	if c[0] == 0:
		for j in range(a[0]-c[1]):
			b[c[1]+j] += c[2]

	else:
		if c[1] == 1:
			print(b[c[2]])
		else:
			print(b[c[2]]-b[c[1]-1])

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())

answer = []
# create segtree
size = 1

while size < n :
    size *= 2
    
size = size * 2 - 1
segtree = [0 for x in range(size)]

# update query
def update(i, x) :
    ind = size // 2 + i
    segtree[ind] += x
    
    while ind :
        ind = (ind - 1) // 2 # parent
        ch1 = segtree[ind * 2 + 1]
        ch2 = segtree[ind * 2 + 2]
        segtree[ind] = ch1 + ch2
    
def query(s, t, l, r, p) :
    if s > r or t < l :
        return 0
    if s <= l and t >= r :
        return segtree[p]
    else :
        vl = query(s, t, l, (l + r) // 2, p * 2 + 1)
        vr = query(s, t, (l + r) // 2 + 1, r, p * 2 + 2)
        
        return vl + vr
    
for i in range(q) :
    # print("DBG : ", segtree)
    com, x, y = map(int, input().split())
     
    if com == 0 :
        update(x, y)
    else :
        answer.append(query(x, y, 0, size // 2, 0))

for a in answer :
    print(a)

Submission status: Runtime Error

Solution code:
import sys


class BinaryIndexedTree(object):
    __slots__ = ["tree"]

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

    def add(self, index: int, value: int) -> None:
        tree = self.tree
        next_index = index + 1

        while next_index < len(tree):
            tree[next_index] += value
            next_index += next_index & -next_index

    def sum(self, index: int):
        tree, result = self.tree, 0
        next_index = index + 1

        while next_index:
            result += tree[next_index]
            next_index -= next_index & -next_index

        return result


if __name__ == "__main__":
    n, q = map(int, input().split())
    bit = BinaryIndexedTree(n)
    result = []
    for com, x, y in (map(int, l.split()) for l in sys.stdin):
        if not com:
            bit.add(x, y)
        else:
            result.append(bit.sum(y) - bit.sum(x-1))

    print(*result, sep="\n")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=2**31-1

class BIT:
    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    # [0, i]を合計する
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

N,Q=MAP()
bit=BIT(N)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        bit.add(x, y)
    else:
        print(bit.get(x, y+1))

Submission status: Runtime Error

Solution code:
import sys
import itertools

class RSQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz < n: self.sz = self.sz << 1
        self.dat = [0] * (2 * self.sz - 1)
    
    def update(self, idx, x):
        idx += self.sz - 1
        self.dat[idx] += x
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] += x
            
    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)
            
    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return self.query_help(a, b, 2 * k + 1, l, (l + r)>>1) + \
                    self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r)
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    n, q = line.split()
    n, q = int(n), int(q)
    rmq = RSQ(n)
    
    for i in range(q):
        line = sys.stdin.readline()
        op, a, b = line.split()
        op, a, b = int(op), int(a), int(b)
        if op == 0: 
            rmq.update(a, b)
        else: 
            sys.stdout.write(str(rmq.query(a, b + 1)) + '\n')

Submission status: Runtime Error

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

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

    # sum [i, j)
    def sum_sec(self, i, j):
        return self.sum(j) - self.sum(j)

    def add(self, i, x):
        i += 1
        while (i <= self.size):
            self.bit[i] += x
            i += i & -i

n, q = map(int, raw_input().split())
bit = BIT(n)
for i in xrange(q):
    c, x, y = map(int, raw_input().split())
    if c == 0: bit.add(x - 1, y)
    else: print bit.sum(x - 1, y)

Submission status: Runtime Error

Solution code:
from math import sqrt, ceil

n, q = map(int, input().split())
unit = ceil(sqrt(n))

l = [(0, [0] * unit) for _ in range(unit)]

while q:
    op, s, t = map(int, input().split())
    sd, sm = s // unit, s % unit
    if op:
        td, tm = t // unit, t % unit
        if sd == td:
            print(sum(l[sd][1][sm:tm + 1]))
        else:
            unit_sum = sum((tup[0] for tup in l[sd + 1:td]))
            s_sum = sum(l[sd][1][sm:])
            t_sum = sum(l[td][1][:tm + 1])
            print(unit_sum + s_sum + t_sum)
    else:
        tup = l[sd]
        tup[1][sm] += t
        l[sd] = (tup[0] + t, tup[1])
    q -= 1

Submission status: Runtime Error

Solution code:
import math, sys

#??°????????????????????§????¨????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [0] * (2 * self.TreeRange - 1)

    def add(self, i, x):
        i += self.TreeRange - 1
        self.List[i] += x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] += x

    def getsum(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°0????????????
        if right <= s or t <= left:
            return 0
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
            return l + r

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.add(x, y)
    elif cmd == 1:
        print(ST.getsum(x,y + 1, right = ST.TreeRange))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


class RSQ(object):
    INT_MAX = 2**31 - 1

    def __init__(self, nn, init_val=0):
        self.val = [init_val] * (nn+1)
        self.n = 1
        while self.n < nn:
            self.n *= 2
        self.dat = [init_val] * ((2 * self.n)-1)

    def update(self, k, a):
        # A[k]???a?????´??°?????????????????°???????????¨?????´??°
        self.val[k] = a
        k += (self.n - 1)
        self.dat[k] = a

        while k > 0:
            k = (k - 1) // 2        #  ??????index??????
            self.dat[k] = self.dat[k * 2 + 1] + self.dat[k * 2 + 2]

    def add(self, k, a):
        self.val[k] += a
        self.update(k, self.val[k])

    def query(self, a, b, k, l, r):
        # [a, b)???????°????????±??????? (0????????§b???????????????)
        # ??????????????¨?????????query(a, b, 0, 0, n)?????¢??§??????????????????k, l, r???????????????????????´??°?????????
        if r <= a or b <= l:        #  ?????????????????§??¨??????????????????
            return RSQ.INT_MAX
        if a ==l and r == b:
            return self.dat[k]           #  ???????????°???????????????????????§????????°????????¨??????????????????????°?????????????????????????
        else:
            mid = (l+r) // 2
            if b <= mid:
                return self.query(a, b, k*2+1, l, (l+r)//2) #  ????????°????????????????°????
            elif a >= mid:
                return self.query(a, b, k*2+2, (l+r)//2, r) #  ????????°????????????????°????
            else:
                vl = self.query(a, mid, k*2+1, l, mid)
                vr = self.query(mid, b, k*2+2, mid, r)
                return vl + vr


    def find(self, s, t):
        return self.query(s, t+1, 0, 0, self.n)


def main(args):
    n, q = map(int, input().split(' '))

    rq = RSQ(n)
    for _ in range(q):
        com, x, y = map(int, input().split(' '))
        if com == 0:
            rq.add(x, y)
        elif com == 1:
            res = rq.find(x, y)
            print(res)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
class RSQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]
            
    def add(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] += num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def call_search(self, a, b):
        return self.search(a, b, index = 0, l = 0, r = self.length - 1)

    def search(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif r < a or b < l:
            return self.ini_num
        else:
            return self.search(a, b, index * 2 + 1, l, (l + r) // 2) + self.search(a, b, index * 2 + 2, (l + r) // 2 + 1, r)

v_num, query = map(int, input().split(" "))
rsq = RSQ(v_num, 0)
for _ in range(query):
    comm, index, num = map(int, input().split(" "))
    if comm == 0:
        rsq.add(index, num)
    else:
        print(rsq.call_search(index, num))

Submission status: Runtime Error

Solution code:
class RSQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        if length == 1:
            length = 2
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def add(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] += num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def call_search(self, a, b):
        return self.search(a, b, index = 0, l = 0, r = self.length - 1)

    def search(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif r < a or b < l:
            return self.ini_num
        else:
            return self.search(a, b, index * 2 + 1, l, (l + r) // 2) + self.search(a, b, index * 2 + 2, (l + r) // 2 + 1, r)

v_num, query = map(int, input().split(" "))
rsq = RSQ(v_num, 0)
for _ in range(query):
    comm, index, num = map(int, input().split(" "))
    if comm == 0:
        rsq.add(index, num)
    else:
        print(rsq.call_search(index, num))

Submission status: Runtime Error

Solution code:
class SegmentTree():
	def __init__(self,n):
		self.dat = [0 for _ in range(n*2-1)]
		#index n???????????????????????¢?????????:
		#???????????? : (n-1)//2
		#???????????? : (2n+1) , (2n+2)
		self.n = n

	def update (self,node_index,value):
		""" index?????????value????????´?????? """
		index = node_index + (self.n-1) #node_index????????????dot???index?????????
		self.dat[index] += value

		#?????°????????????????????????????????´????????????
		while index > 0 :
			index = (index - 1) // 2				 #???????????????????????£???
			self.dat[index] = self.dat[index*2+1] + self.dat[index*2+2] #??????????????????????????????

	def querry (self,left,right,nowNode,nowLeft,nowRight):
		"""[left,right):??¢?´¢??????,noeNode:?????¨????????????,[nowLeft,nowRight):?????¨?????????????????????"""

		# ??????????????¶??£????????????
		if nowRight < left or nowLeft > right:
			return 0

		# ?????¨?????¢?´¢???????????¨????????????????????????????????????
		if left <= nowLeft and nowRight <= right:
			return self.dat[nowNode]

		# ???????????????????????????????????¨???????????????
		else:
			value_left = self.querry(left,right,2*nowNode+1,nowLeft,(nowLeft+nowRight)//2)
			value_right = self.querry(left,right,2*nowNode+2,(nowLeft+nowRight)//2+1,nowRight)
			return (value_left + value_right)

	def DEBUG_dat(self):
		print(self.dat)


if __name__ == "__main__":
	n ,q  = map(int,input().split(" "))
	result = []

	for i in range(1,20):
		if 2 ** i >= n:
			min_pow2 = 2 **  i
			break

	tree = SegmentTree(min_pow2)

	for i in range(q):
		com,x,y = map(int,input().split(" "))
		if com == 0:
			tree.update(x,y)
		else:
			result.append(tree.querry(x,y,0,0,min_pow2-1))


	for ans in result:
		print(ans)

Submission status: Runtime Error

Solution code:
import sys;

def init(n_):
    length = 1;
    while(length < n_):
        length*=2
    element=[0]*(2*length-1)
    for i in range(2*length-1):
        element[i] = 0
    return element,length

def update(k,a,element):
    k+=n-1
    element[k]+=a
    while(k > 0):
        k = (int)((k-1)/2)
        element[k] = element[k*2+1]+element[k*2+2]

def findmin(a, b):
    return findquery(a,b+1,0,0,n)

def findquery(a, b, k, l, r):
    if(r <= a or b <= l):
        return 0
    if(a <= l and r <= b):
        return element[k]

    vl = findquery(a,b,k*2+1,l,(int)((l+r)/2+0.5))
    vr = findquery(a,b,k*2+2,(int)((l+r)/2),r)
    return vl+vr

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

element,n = init(n)

for i in range(q):
    query,key,value = map(int, input().split());
    if(query == 0):
        update(key,value,element)
    else :
        print(findmin(key,value))

Submission status: Runtime Error

Solution code:
import sys;

def init(n_):
    length = 1;
    while(length < n_):
        length*=2
    length2 = (2*length-2)
    if(length2 == 0):
        length2 = 1
    element=[0]*length2
    for i in range(length2):
        element[i] = 0
    return element,length

def update(k,a,element):
    k+=n-1
    if(n == 1):
        k = 0
    element[k]+=a
    while(k > 0):
        k = (int)((k-1)/2)
        element[k] = element[k*2+1]+element[k*2+2]

def findmin(a, b):
    return findquery(a,b+1,0,0,n)

def findquery(a, b, k, l, r):
    if(r <= a or b <= l):
        return 0
    if(a <= l and r <= b):
        return element[k]

    vl = findquery(a,b,k*2+1,l,(int)((l+r)/2+0.5))
    vr = findquery(a,b,k*2+2,(int)((l+r)/2),r)
    return vl+vr

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

element,n = init(n)

for i in range(q):
    query,key,value = map(int, input().split());
    if(query == 0):
        update(key,value,element)
    else :
        if(n==1):
            key = 0
        print(findmin(key,value))

Submission status: Runtime Error

Solution code:
import sys;

def init(n_):
    length = 1;
    while(length < n_):
        length*=2
    length2 = (2*length-1)
    if(length2 == 0):
        length2 = 1
    element=[0]*length2
    for i in range(length2):
        element[i] = 0
    return element,length

def update(k,a,element):
    k+=n-1
    if(n == 1):
        k = 0
    element[k]+=a
    while(k > 0):
        k = (int)((k-1)/2)
        element[k] = element[k*2+1]+element[k*2+2]

def findmin(a, b):
    return findquery(a,b+1,0,0,n)

def findquery(a, b, k, l, r):
    if(r <= a or b <= l):
        return 0
    if(a <= l and r <= b):
        return element[k]

    vl = findquery(a,b,k*2+1,l,(int)((l+r)/2+0.5))
    vr = findquery(a,b,k*2+2,(int)((l+r)/2),r)
    return vl+vr

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

element,n = init(n)

for i in range(q):
    query,key,value = map(int, input().split());
    if(query == 0):
        update(key,value,element)
    else :
        if(n==1):
            key = 0
        print(findmin(key,value))

Submission status: Runtime Error

Solution code:

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

n_ = 1 # 実際に確保した配列のサイズ
while n_ < n:
  n_ *= 2

seg_tree = [0 for i in range(2*n_-1)]

def add(i, x):
  i += n_ - 1
  seg_tree[i] += x
  while i > 0 :
    i = int((i - 1)/2)
    #seg_tree[i] = seg_tree[i*2+1] + seg_tree[i*2+2]
    seg_tree[i] += x

def getSum(s, t):
  return query(s, t+1, 0, 0, n_)

def query(a, b, k, l, r):
  if r <= a or b <= l :
    return 0
  if a <= l and r <= b:
    return seg_tree[k]

  vl = query(a, b, k*2+1, l, int((l+r)/2))
  vr = query(a, b, k*2+2, int((l+r)/2), r)
  return vl + vr


output = []

for i in range(q):
  line = list(map(int, input().split()))

  if line[0] == 0:
    add(line[1], line[2])

  else :
    output.append(getSum(line[1],line[2]))


for ans in output:
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    D = [0] * (2*n_ - 1)

    return n_, D


def update(k, a):
    k += n_ - 1
    D[k] += a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = D[k*2 + 1] + D[k*2 + 2]


def findSum(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 0

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return vl + vr


if __name__ == '__main__':
    n, q = map(int, input().split())

    n_, D = initRMQ(n)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findSum(x, y))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    D = []
    for _ in range(2*n_ - 1):
        D.append(0)

    return n_, D


def update(k, a):
    k += n_ - 1
    D[k] += a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = D[k*2 + 1] + D[k*2 + 2]


def findSum(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 0

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return vl + vr


if __name__ == '__main__':
    n, q = map(int, input().split())

    n_, D = initRMQ(n)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findSum(x, y))

Submission status: Runtime Error

Solution code:
import math

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.height = math.ceil(math.log2(n))
        self.nodes = [0 for i in range(pow(2, self.height+1)-1)]
        self.leaf_start = pow(2, self.height)-1

    def update(self, i, x):
        pntr = self.leaf_start + i
        self.nodes[pntr] += x
        while True:
            pntr = (pntr-1)//2
            if pntr == -1: break
            self.nodes[pntr] += x

    def __query(self, s, t, k, l, r):
        if t - s <= 0: return 0
        if r <= s or t <= l: return 0
        if l == s and t == r: return self.nodes[k]
        else:
            m = (l+r)//2
            if t <= m:
                return self.__query(s, t, k*2+1, l, m)
            elif m <= s:
                return self.__query(s, t, k*2+2, m, r)
            else:
                vl = self.__query(s, m, k*2+1, l, m)
                vr = self.__query(m, t, k*2+2, m, r)
                return vl + vr

    def find(self, s, t):
        return self.__query(s, t+1, 0, 0, pow(2, self.height))

n, q = list(map(int, input().split(' ')))
st = SegmentTree(n)
for i in range(q):
    com, x, y = list(map(int, input().split(' ')))
    if com == 0:
        st.update(x, y)
    elif com == 1:
        print(st.find(x, y))