Problem:
Range Sum Query Write a program which manipulates a sequence A = { a 1 , a 2 , . . . , a n } with the following operations:  add(i, x) : add x to a i .  getSum(s, t) : print the sum of a s , a s+1 ,...,a t .  Note that the initial values of a i ( i = 1, 2, . . . , n ) are 0. Input  n  q  com 1  x 1  y 1  com 2  x 2  y 2 ... com q  x q  y q  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(x i , y i ) and '1' denotes getSum(x i , y i ) . Output For each getSum operation, print the sum in a line. Constraints   1 ≤ n ≤ 100000    1 ≤ q ≤ 100000   If com i is 0, then 1 ≤ x i ≤ n , 0 ≤ y i ≤ 1000 .  If com i is 1, then 1 ≤ x i ≤ n , 1 ≤ y i ≤ 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

Solution (Python):

class BIT:
    
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-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))

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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 ** (len(bin(self.len + 1)) - 2)
        self.n = n
        
        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):
        
        i += self.n
        self.node[i] = val
        
        while i > 1:
            
            i //= 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)

        
        
        
        def get(k, l, r):
            
            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




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.query(x, y + 1))

Solution (Python):



"""
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)
    


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))



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_B()

Solution (Python):

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:
  
  def __init__(self,size):
    self.data = [0]*(size+1)
    self.size = size
  
  
  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))

Solution (Python):
"""Range Minimum Query (RMQ)"""




def update(idx, x):
    idx += size-1  
    seg[idx] += x  
    
    while idx > 0:
        idx = (idx-1)//2  
        seg[idx] = seg[2*idx+1] + seg[2*idx+2]  
    
    return



def query(a, b, k, l, r):  
    
    if r <= a or b <= l:  
        return INF  
    if a <= l and r <= b:
        return seg[k]  
    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  


N, Q = map(int, input().split())  
size = 1  
while N > size:
    size *= 2  



INF = 0  

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))

Solution (Python):


"""
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()

Solution (Python):
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()  
        self.data = [ele_id] * (2 * self.n - 1)  
        self.ele_id = ele_id  
        self.op_func = op_func  

    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]  
        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):
        
        i += self.n - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2  
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

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

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            
            return self.ele_id
        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            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)

Solution (Python):


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:
            
            ans.append(getSum(arg[1]) - getSum(arg[0]-1))
        
    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

Solution (Python):
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()

Solution (Python):
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)))

Solution (Python):

import sys
input = sys.stdin.readline

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

class RMQ:
    def __init__(self, n, e):
        
        self.e = e
        
        self.num_min =2**(n-1).bit_length()
        self.seg=[self.e]*2*self.num_min

    def initialize(self, init):
        
        
        for i in range(n):
            self.seg[i+self.num_min-1]=init[i]
        
        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)

Solution (Python):
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()

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

    def __init__(self):
        pass

    def load(self, l):
        
        self.lenData = 2 ** (len(l) - 1).bit_length()  
        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]
        """
        
        nodeId = (self.lenData - 1) + i
        
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            
            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の結果を返す
        """
        
        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()

for _ in range(q):
    
    cmd, a, b = map(int, input().split())
    if cmd == 0: 
        st.addValue(a - 1, b)
    else:
        print(st.query(a - 1 , b + 1 -1))

Solution (Python):
import sys
input = sys.stdin.readline

class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])
    def update(self,index,x):
        index += self.n-1
        self.tree[index] = x
        while index>0:
            index = (index-1)//2
            self.tree[index] = self.func(self.tree[2*index+1],self.tree[2*index+2])
    def query(self,left,right): 
        if right <= left:
            return self.ie
        left += self.n-1
        right += self.n-2
        res = self.ie
        while right-left > 1:
            if left & 1 == 0:
                res = self.func(res,self.tree[left])
            if right & 1 == 1:
                res = self.func(res,self.tree[right])
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            res = self.func(res,self.tree[left])
        else:
            res = self.func(self.func(res,self.tree[left]),self.tree[right])
        return res

N,Q = map(int,input().split())
A = [0 for _ in range(N)]

st = SegmentTree(A,lambda x,y:x+y,0)
ans = []

for _ in range(Q):
    com,x,y = map(int,input().split())
    if com == 0:
        st.update(x-1,st.query(x-1,x)+y)
    else:
        ans.append(st.query(x-1,y))

print(*ans,sep='\n')

Solution (Python):
class Segment_Tree:
    def __init__(self,n,func,init):
        self.n = n
        self.tree = [init]*(2*self.n - 1)
        self.func = func
        self.init = init

    def update(self,i,x):
        i += self.n - 1
        self.tree[i] = x
        while i>0:
            i = int((i-1)/2)
            self.tree[i] = self.func((self.tree[2*i+1], self.tree[2*i+2]))

    def find(self,a,b,k,l,r):
        if r <= a or b <= l:
            return self.init
        if a <= l and r <= b:
            return self.tree[k]
        vl = self.find(a,b,k*2+1,l,int((l+r)/2))
        vr = self.find(a,b,k*2+2,int((l+r)/2),r)
        return self.func((vl, vr))

n, q = map(int, input().split())
N = 1
while N < n:
    N *= 2

func = lambda a: a[0]+a[1]

segtre = Segment_Tree(N,func,0)

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0: 
        segtre.update(x-1,segtre.tree[x + segtre.n - 2]+y)
    else: 
        print(segtre.find(x-1,y,0,0,N))

Solution (Python):
class SegmentTree:
    def __init__(self, array, seg_func, ide_ele):
        n = len(array)
        self.size = 2**(n - 1).bit_length()
        self.seg_func = seg_func
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele] * (2 * self.size - 1)

        for i in range(n):
            self.seg[i + self.size - 1] = array[i]
        for i in range(self.size - 2, -1, -1):
            self.seg[i] = self.seg_func(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, index, sbn):
        index += self.size - 1
        self.seg[index] += sbn
        while index:
            index = (index - 1) // 2
            self.seg[index] = self.seg_func(self.seg[index * 2 + 1], self.seg[index * 2 + 2])

    def query(self, lower_ep, upper_ep):
        if upper_ep <= lower_ep:
            return self.ide_ele
        lower_ep += self.size - 1
        upper_ep += self.size - 2
        res = self.ide_ele
        while (upper_ep - lower_ep) > 1:
            if lower_ep & 1 == 0:
                res = self.seg_func(res, self.seg[lower_ep])
            if upper_ep & 1 == 1:
                res = self.seg_func(res, self.seg[upper_ep])
                upper_ep -= 1

            lower_ep //= 2
            upper_ep = (upper_ep - 1) // 2
        if lower_ep == upper_ep:
            res = self.seg_func(res, self.seg[lower_ep])
        else:
            res = self.seg_func(self.seg_func(res, self.seg[lower_ep]), self.seg[upper_ep])
        return res


def add(a, b):
    return a + b


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

Solution (Python):
n,q = map(int,input().split(" "))
tree = [0] * (n + 1)
querys = [tuple(map(int,input().split(" "))) for _ in range(q) ]

def b_sum(i):

    ans = 0
    while i > 0:
        ans += tree[i]
        i -=(i) & (-i)


    return ans



for query in querys:
    com,x,y = query
    if com == 0:
        i = x
        x = y

        while i <= n:

            tree[i] += x
            i += (i) & (-i)

    if com == 1:

        s = x - 1
        t = y




        print(b_sum(t) - b_sum(s))

Solution (Python):
class FenwickTree:
    """FenwickTree (Binary Indexed Tree, 0-index)

    Queries:
        1. add(i, val): add val to i-th value
        2. sum(n): sum(bit[0] + ... + bit[n-1])

    complexity: O(log n)

    See: http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, a_list):
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(self.N, 1 << (self.N - 1).bit_length()):
            self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

    def sum(self, n):
        ret = 0
        while n >= 0:
            ret += self.bit[n]
            n = (n & (n + 1)) - 1
        return ret

    def query(self, low, high):
        return self.sum(high) - self.sum(low)


def yosupo():
    
    N, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        print([fwt.sum(i) for i in range(N+1)])
        if type_ == 0:
            fwt.add(l, r)
        else:
            print(fwt.query(l, r))


def aoj():
    
    N, Q = map(int, input().split())
    fwt = FenwickTree([0] * N)
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l-1, r)
        else:
            print(fwt.query(l-2, r-1))


if __name__ == "__main__":
    
    aoj()

Solution (Python):
class Bit(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def add(self, a: int, w: int):
        x: int = a
        while x <= self.N:
            self.bit[x] += w
            x += x & -x

    def sum(self, a: int):
        ret: int = 0
        x: int = a
        while x > 0:
            ret += self.bit[x]
            x -= x & -x

        return ret

    def range_sum(self, x, y):
        ret1 = self.sum(y)
        ret2 = self.sum(x - 1)

        return ret1 - ret2


N, q = input().split()
N = int(N)
q = int(q)
bit = Bit(N)

for _ in range(q):
    mode, x, y = input().rstrip().split()
    if mode == "0":
        bit.add(int(x), int(y))
    else:
        ret = bit.range_sum(int(x), int(y))
        print(ret)

Solution (Python):
def add(bit, a, w, n):
    x = a
    while x <= n:
        bit[x] += w
        x += x & -x


def sum_from_zero(bit, a):
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret


def main():
    [n, q] = [int(num) for num in input().split()]

    bit = [0 for _ in range(n + 1)]

    for i in range(q):
        [com, x, y] = [int(num) for num in input().split()]

        if com == 0:
            add(bit, x, y, n)
        else:
            print(sum_from_zero(bit, y) - sum_from_zero(bit, x-1))


if __name__ == '__main__':
    main()

Solution (Python):
n, q = [int(s) for s in input().split()]
bit = [0] * (n+1)

def add(a, w):
    x = a
    while x <= n:
        bit[x] += w
        x += (x & -x)


def sum(a):
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret


for _ in range(q):
    com, x_i, y_i = [int(s) for s in input().split()]
    if com == 0:
        add(x_i,y_i)
        
    else:
        ans = sum(y_i) - sum(x_i-1)
        print(ans)

Solution (Python):
def func(x,y):
    return  x+y

class SegmentTree:
    def __init__(self, n): 
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [0] * (2*self.n-1)

    def update(self, k, a): 
        k += self.n - 1
        self.arr[k] += a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = func(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        res = 0
         
         
         
         

        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1])

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res

n,q=map(int,input().split())
sg=SegmentTree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sg.update(x-1,y)
    else:
        print(sg.query(x-1,y))

Solution (Python):


n,q = map(int,input().split( ))
s = 1
while s < n:
    s*=2

A = [0]*(2*s-1)

def query(a,b,k,l,r):
    if r<=a or b<=l:
        return 0
    if a<=l and r<=b:
        return A[k]
    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

for _ in range(q):
    c,x,y = map(int, input().split( ))
    if not c:
        x += (s-1)
        x -=1
        A[x] += y
        while x>0:
            x =(x-1)//2
            A[x] = A[x*2+1]+A[x*2+2]
        
            
    else:
        print(query(x-1,y,0,0,s))

Solution (Python):
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

n,q=map(int,input().split())
tree=Binary_Indexed_Tree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        tree.add_element(x,y)
    else:
        print(tree.partially_sum(y)-tree.partially_sum(x-1))

Solution (Python):
import sys
input = sys.stdin.readline

class SegmentTree:
    def __init__(self, num, ide_ele=0):
        tmp = 1
        while tmp < num:
            tmp *= 2
        self.n = tmp
        self.ide_ele = ide_ele
        self.l = [ide_ele] * (2 * self.n - 1)
    
    def func(self, x, y):
        return x + y
        

    def update(self, i, val):
        i = self.n - 1 + i
        self.l[i] += val
        while i > 0:
            i = (i-1)//2
            self.l[i] = self.func(self.l[i*2+1], self.l[i*2+2])
    
    def query(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.l[k]
        vl = self.query(a, b, k*2+1, l, (l+r)//2)
        vr = self.query(a, b, k*2+2, (l+r)//2, r)
        return self.func(vl, vr)

def main():
    N, Q = map(int, input().split())

    segt = SegmentTree(N)

    for _ in range(Q):
        c, x, y = map(int, input().split())
        if c == 0:
            segt.update(x-1, y)
        else:
            print(segt.query(x-1, y, 0, 0, segt.n))
        



if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, q = map(int, input().split())
    nums = [0] * (n+1)
    
    for i in range(q):
        com, x, y = map(int, input().split())
        
        if not com:
            while x <= n:
                nums[x] += y
                x += x & -x
        else:
            x -= 1
            s_sum = 0
            while x:
                s_sum += nums[x]
                x -= x & -x
            t_sum = 0
            while y:
                t_sum += nums[y]
                y -= y & -y
                
            print(t_sum - s_sum)

if __name__ == '__main__':
    main()