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



"""
input:
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

output:
3
2
"""

import sys


class BinaryIndexedTree(object):
    __slots__ = ('length', 'dat')

    def __init__(self, n):
        """
        Init a BIT with update and find for range sum queries.
        """
        self.length = int(n)
        self.dat = [0] * (self.length + 1)

    
    def __init_sum(self, i):
        _sum = 0
        while i > 0:
            _sum += self.dat[i]
            i -= i & (-i)
        return _sum

    def get_sum(self, s, t):
        return self.__init_sum(t) - self.__init_sum(s - 1)

    
    def get_add(self, i, x):
        while i <= self.length:
            self.dat[i] += x
            i += i & (-i)
        return self.dat


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.get_add(ele_1, ele_2)
        elif cmd == 1:
            res = case.get_sum(ele_1, ele_2)
            print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    case = BinaryIndexedTree(n_num)
    ans = action(q_list)

Solution (Python):



"""
input:
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

output:
3
2
"""

import sys


class BinaryIndexedTree(object):
    __slots__ = ('length', 'dat')

    def __init__(self, n):
        """
        Init a BIT with update and find for range sum queries.
        """
        self.length = int(n)
        self.dat = [0] * (self.length + 1)

    
    def __init_sum(self, i):
        _sum = 0
        while i > 0:
            _sum += self.dat[i]
            i -= i & (-i)
        return _sum

    def get_sum(self, s, t):
        return self.__init_sum(t) - self.__init_sum(s - 1)

    
    def get_add(self, i, x):
        while i <= self.length:
            self.dat[i] += x
            i += i & (-i)
        return None


def action(cmd_list):
    case = BinaryIndexedTree(n_num)
    
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.get_add(ele_1, ele_2)
        elif cmd == 1:
            res = case.get_sum(ele_1, ele_2)
            print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    ans = action(q_list)

Solution (Python):



"""
input:
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

output:
3
2
"""

import sys


class BinaryIndexedTree(object):
    __slots__ = ('length', 'dat')

    def __init__(self, n):
        """
        Init a BIT with update and find for range sum queries.
        """
        self.length = int(n)
        self.dat = [0] * (self.length + 1)

    
    def __init_sum(self, i):
        _sum = 0
        while i > 0:
            _sum += self.dat[i]
            i &= (i - 1)
        return _sum

    def sum_st(self, s, t):
        return self.__init_sum(t) - self.__init_sum(s - 1)

    
    def assign_ix(self, i, x):
        while i <= self.length:
            self.dat[i] += x
            i += i & (-i)
        return None


def action():
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    queries = map(lambda x: x.split(), _input[1:])
    case = BinaryIndexedTree(n_num)

    for query in queries:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.assign_ix(ele_1, ele_2)
        elif cmd == 1:
            res = case.sum_st(ele_1, ele_2)
            print(res)

    return case


if __name__ == '__main__':
    action()

Solution (Python):
def add(i, x):
    i += n-1
    sg[i] += x
    while i>0:
        i = (i-1)//2
        sg[i] += x


def getSum(a, b):
    return _getSum(a, b+1, 0, 0, n)


def _getSum(a, b, k, l, r):
    if b <= l or r <= a:
        return 0

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

    ll = _getSum(a, b, k*2+1, l, (r+l)/2)
    rr = _getSum(a, b, k*2+2, (r+l)/2, r)
    return ll+rr


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

sg = [0] * (2*n-1)

for i in range(q):
    (c, x, y) = map(int, input().split())
    if c:
        print(getSum(x, y))
    else:
        add(x, y)

Solution (Python):
import sys

inf = (1 << 31) - 1

def solve():
    n, q = map(int, sys.stdin.readline().split())

    sg = SegTree([0]*n)

    for qi in range(q):
        
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            x -= 1
            sg.add(x, y)
        else:
            x, y = x-1, y-1
            ans = sg.get_sum(x, y + 1, 0, 0, 2**sg.depth)
            print(ans)

class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.depth = 0

        while 2**self.depth < self.n:
            self.depth += 1

        self.data = [0]*(2**(self.depth + 1) - 1)

        self.data[2**(self.depth) - 1:2**(self.depth) - 1 + self.n] = a[:]

        for i in range(2**self.depth - 2, -1, -1):
            self.data[i] = self.data[2*i + 1] + self.data[2*i + 2]

    def add(self, i, x):
        i += 2**self.depth - 1
        self.data[i] += x

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

    def get_sum(self, s, t, k, left, right):
        if t <= left or right <= s:
            return 0
        if s <= left and right <= t:
            return self.data[k]

        vl = self.get_sum(s, t, 2*k + 1, left, (left + right) // 2)
        vr = self.get_sum(s, t, 2*k + 2, (left + right) // 2, right)

        return vl + vr

if __name__ == '__main__':
    solve()

Solution (Python):
import sys

inf = (1 << 31) - 1

def solve():
    n, q = map(int, sys.stdin.readline().split())

    bit = BinaryIndexedTree([0]*n)

    for qi in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            x -= 1
            bit.add(x, y)
        else:
            ans = bit.get_sum(y) - bit.get_sum(x - 1)
            print(ans)

class BinaryIndexedTree:
    def __init__(self, a):
        self.n = len(a)
        self.bit = [0]*(self.n + 1)

        for i in range(1, self.n + 1):
            self.bit[i] += a[i - 1]

            if i + (i & (-i)) <= self.n:
                self.bit[i + (i & (-i))] += self.bit[i]

    def add(self, i, x):
        i += 1

        while i <= self.n:
            self.bit[i] += x
            i += i & (-i)

    def get_sum(self, r):
        res = 0

        while r > 0:
            res += self.bit[r]
            r -= r & (-r)

        return res

class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.depth = 0

        while 2**self.depth < self.n:
            self.depth += 1

        self.data = [0]*(2**(self.depth + 1) - 1)

        self.data[2**(self.depth) - 1:2**(self.depth) - 1 + self.n] = a[:]

        for i in range(2**self.depth - 2, -1, -1):
            self.data[i] = self.data[2*i + 1] + self.data[2*i + 2]

    def add(self, i, x):
        i += 2**self.depth - 1
        self.data[i] += x

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

    def get_sum(self, s, t, k, left, right):
        if t <= left or right <= s:
            return 0
        if s <= left and right <= t:
            return self.data[k]

        vl = self.get_sum(s, t, 2*k + 1, left, (left + right) // 2)
        vr = self.get_sum(s, t, 2*k + 2, (left + right) // 2, right)

        return vl + vr

if __name__ == '__main__':
    solve()

Solution (Python):
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")):
        
        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 - 1, y)
    elif cmd == 1:
        print(ST.getsum(x - 1,y , right = ST.TreeRange))

Solution (Python):
import math
import functools


class SegmentTree:
    def __init__(self, a: list, default: int, op):
        real_size = len(a)
        self.elem_size = 1 << int(math.ceil(math.log2(real_size)))  
        self.tree_size = 2 * self.elem_size + 1
        self.tree = [default] * (self.elem_size - 1) + a + [default] * (self.elem_size - real_size)
        self.operation = op

    def get_range_index(self, x, y, k=0, l_end=0, r_end=None):
        if r_end is None:
            r_end = self.elem_size

        if l_end == x and y == r_end-1:
            return [k]
        elif not l_end <= x <= y < r_end:
            return []

        mid = (l_end + r_end) // 2
        left_y = y if y < mid-1 else mid-1
        right_x = x if x > mid else mid

        left = self.get_range_index(x, left_y, 2*k+1, l_end, mid)
        right = self.get_range_index(right_x, y, 2*k+2, mid, r_end)
        return left + right

    def get_value(self, x, y):
        tree = self.tree
        index_list = self.get_range_index(x, y)
        op = self.operation
        return functools.reduce(op, (tree[n] for n in index_list))

    def update_tree(self, k: int):
        op = self.operation
        tree = self.tree

        while k > 0:
            k = (k-1) // 2
            left, right = tree[2*k+1], tree[2*k+2]
            tree[k] = op(left, right)

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size - 1 + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rsq = SegmentTree([0]*n, 0, lambda x, y: x+y)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rsq.set_value(x-1, y, "+")
    else:
        ans.append(rsq.get_value(x-1, y-1))
print("\n".join([str(n) for n in ans]))

Solution (Python):
import math


class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree"]

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree_size = 2 * self.elem_size + 1
        self.tree = [default] * (self.elem_size - 1) + a + [default] * (self.elem_size - real_size)

    def get_range_index(self, x, y, k=0, l_end=0, r_end=None):
        '''[x, y], tree[k], [l_end, r_end)'''
        if r_end is None:
            r_end = self.elem_size

        if l_end == x and y == r_end-1:
            return [k]
        elif not l_end <= x <= y < r_end:
            return []

        mid = (l_end + r_end) // 2
        left_y = y if y < mid-1 else mid-1
        right_x = x if x > mid else mid

        left = self.get_range_index(x, left_y, 2*k+1, l_end, mid)
        right = self.get_range_index(right_x, y, 2*k+2, mid, r_end)
        return left + right

    def get_value(self, x, y):
        tree = self.tree
        index_list = self.get_range_index(x, y)

        return sum(tree[n] for n in index_list)

    def update_tree(self, k: int):
        tree = self.tree

        while k > 0:
            k = (k-1) // 2
            left, right = tree[2*k+1], tree[2*k+2]
            tree[k] = left + right

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size - 1 + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rsq = SegmentTree([0]*n, 0)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rsq.set_value(x-1, y, "+")
    else:
        ans.append(rsq.get_value(x-1, y-1))
print("\n".join([str(n) for n in ans]))

Solution (Python):
import math


class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree"]

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree_size = 2 * self.elem_size + 1
        self.tree = [default] * (self.elem_size - 1) + a + [default] * (self.elem_size - real_size)

    def get_range_index(self, x, y, k=0, l_end=0, r_end=None):
        '''[x, y], tree[k], [l_end, r_end)'''
        if r_end is None:
            r_end = self.elem_size

        if l_end == x and y == r_end-1:
            return [k]

        mid = (l_end + r_end) // 2
        left_y = y if y < mid-1 else mid-1
        right_x = x if x > mid else mid

        left = self.get_range_index(x, left_y, 2*k+1, l_end, mid) if x <= left_y else []
        right = self.get_range_index(right_x, y, 2*k+2, mid, r_end) if right_x <= y else []
        return left + right

    def get_value(self, x, y):
        tree = self.tree
        index_list = self.get_range_index(x, y)

        return sum(tree[n] for n in index_list)

    def update_tree(self, k: int):
        tree = self.tree

        while k > 0:
            k = (k-1) // 2
            left, right = tree[2*k+1], tree[2*k+2]
            tree[k] = left + right

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size - 1 + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rsq = SegmentTree([0]*n, 0)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rsq.set_value(x-1, y, "+")
    else:
        ans.append(rsq.get_value(x-1, y-1))
print("\n".join([str(n) for n in ans]))

Solution (Python):
import math


class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree"]

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree_size = 2 * self.elem_size + 1
        self.tree = [default] * (self.elem_size - 1) + a + [default] * (self.elem_size - real_size)

    def get_range_index(self, x, y, k=0, l_end=0, r_end=None):
        '''[x, y], tree[k], [l_end, r_end)'''
        default, tree = 0, self.tree
        if r_end is None:
            r_end = self.elem_size

        if l_end == x and y == r_end-1:
            return tree[k]

        mid = (l_end + r_end) // 2
        left_y = y if y < mid-1 else mid-1
        right_x = x if x > mid else mid

        left = self.get_range_index(x, left_y, 2*k+1, l_end, mid) if x <= left_y else default
        right = self.get_range_index(right_x, y, 2*k+2, mid, r_end) if right_x <= y else default
        return left + right

    def get_value(self, x, y):
        tree = self.tree
        return self.get_range_index(x, y)

        

    def update_tree(self, k: int):
        tree = self.tree

        while k > 0:
            k = (k-1) // 2
            left, right = tree[2*k+1], tree[2*k+2]
            tree[k] = left + right

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size - 1 + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rsq = SegmentTree([0]*n, 0)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rsq.set_value(x-1, y, "+")
    else:
        ans.append(rsq.get_value(x-1, y-1))
print("\n".join([str(n) for n in ans]))

Solution (Python):

"""
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):
        
        self.val[k] = a
        k += (self.n - 1)
        self.dat[k] = a

        while k > 0:
            k = (k - 1) // 2        
            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):
        
        
        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+1)
    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:])

Solution (Python):



class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (N + 1)

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

    def sum(self, a):
        if a == 0:
            return 0
        s = 0
        x = a
        while x > 0:
            s += self.tree[x]
            x -= (x & -x)
        return s


def main():
    N, Q = map(int, input().split(" "))
    bit = BinaryIndexedTree(N)
    for i in range(Q):
        c, x, y = map(int, input().split(" "))
        if c == 0:
            bit.add(x, y)
            
        elif c == 1:
            print(bit.sum(y) - bit.sum(x-1))



if __name__ == "__main__":
    main()

Solution (Python):

"""
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 BIT(object):
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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

            i -= (i & -i)

        return s

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

    def find(self, s, t):
        t_sum = self.sum(t)
        s_sum = self.sum(s - 1)
        return t_sum - s_sum


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

    rq = BIT(n+1)
    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:])

Solution (Python):

"""
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 BIT(object):
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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


        return s

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

    def find(self, s, t):
        t_sum = self.sum(t)
        s_sum = self.sum(s - 1)
        return t_sum - s_sum


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

    rq = BIT(n+1)
    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:])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n,q = LI()
    a = [LI() for _ in range(q)]
    def f(a,b):
        return a + b
    seg = Seg(n+1, 0, f)
    r = []
    for c,x,y in a:
        if c == 0:
            seg.update(x,seg.find(x)+y)
        else:
            r.append(seg.query(x,y+1))

    return '\n'.join(map(str,r))


print(main())

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class BIT():
    def __init__(self, n):
        i = 1
        while 2**i <= n:
            i += 1
        self.H = i
        self.N = 2**i
        self.A = [0] * self.N

    def find(self, i):
        r = 0
        while i:
            r += self.A[i]
            i -= i & (i-1) ^ i
        return r

    def update(self, i, x):
        while i < self.N:
            self.A[i] += x
            i += i & (i-1) ^ i

    def query(self, a, b):
        return self.find(b-1) - self.find(a-1)

def main():
    n,q = LI()
    a = [LI() for _ in range(q)]
    b = BIT(n+3)
    r = []
    for c,x,y in a:
        if c == 0:
            b.update(x,y)
        else:
            r.append(b.query(x,y+1))

    return '\n'.join(map(str,r))


print(main())

Solution (Python):
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 - 1, num)
    else:
        print(rsq.call_search(index - 1, num - 1))

Solution (Python):
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 r < a or b < l:
            return self.ini_num            
        elif a <= l <= r <= b:
            return self.segtree[index]
        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 - 1, num)
    else:
        print(rsq.call_search(index - 1, num - 1))

Solution (Python):
class SegmentTree():
	def __init__(self,n):
		self.dat = [0 for _ in range(n*2-1)]
		
		
		
		self.n = n

	def update (self,node_index,value):
		""" index?????????value????????´?????? """
		index = node_index + (self.n-1) 
		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-1,y)
		else:
			result.append(tree.querry(x-1,y-1,0,0,min_pow2-1))

	for ans in result:
		print(ans)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.array = [0 for i in range(n + 1)]

    def sum(self, i):
        result = 0
        while(i > 0):
            result = result + self.array[i]
            i -= i & (-i)
        return result

    def range_sum(self, i, j):
        tmp_i = self.sum(i - 1)
        tmp_j = self.sum(j)
        return tmp_j - tmp_i

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


init = [int(n) for n in input().split()]
a = []

bit = BIT(init[0])

for i in range(init[1]):
    line = [int(n) for n in input().split()]
    if line[0] == 0:
        bit.add(line[1], line[2])
    else:
        print(bit.range_sum(line[1], line[2]))

Solution (Python):
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-1,value,element)
    else :
        print(findmin(key-1,value-1))

Solution (Python):
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-1,value,element)
    else :
        print(findmin(key-1,value-1))