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:
from array import array

class BIT(object):

    def __init__(self, size, init_data=None):
        self.size = size
        if init_data is None:
            init_data = [0] * (size + 1)
        self.data = array("q", init_data)

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

    def add(self, idx, value):
        while idx <= self.size:
            self.data[idx] += value
            idx += idx & -idx

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

Submission status: Accepted

Solution code:
n, q = map(int, raw_input().split())
n0 = 2**n.bit_length()
data = [0]*(n0*2)
def add(k, a):
    k += n0 - 1
    data[k] += a
    while k:
        k = (k - 1) / 2
        data[k] += a
def query(a, b, k, l, r):
    if b <= l or r <= a:
        return 0
    if a <= l and r <= b:
        return data[k]
    vl = query(a, b, 2*k+1, l, (l + r) / 2)
    vr = query(a, b, 2*k+2, (l + r) / 2, r)
    return vl + vr
def getSum(s, t):
    print query(s, t+1, 0, 0, n0)
for i in xrange(q):
    com, x, y = map(int, raw_input().split())
    [add, getSum][com](x, y)

Submission status: Accepted

Solution code:
import sys
import math

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

# make a balanced binary tree.
n = 2 ** math.ceil(math.log(n, 2))

A = [0 for i in range(2 * n - 1)]

# operating function
def add(i, x):
    # note; argument i is 1-based.
    i += n - 2
    A[i] += x

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

def getSum(s, t, k, l, r):
    if r < s or t < l:
        return 0
    elif s <= l and r <= t:
        return A[k]
    else:
        mid = (l + r) // 2
        lsum = getSum(s, t, k * 2 + 1, l, mid)
        rsum = getSum(s, t, k * 2 + 2, mid + 1, r)
        return lsum + rsum

for s_i in f_i:
    com, x, y = map(int, s_i.split())
    if com == 0:
        add(x, y)
    else:
        ans = getSum(x, y, 0, 1, n)
        print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


class FenwickTree(object):

    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]

    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s

    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)

    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def main():
    n, q = map(int, input().split())
    ft = FenwickTree(n)
    for _ in range(q):
        c, x, y = map(int, input().split())
        if c == 0:
            ft.add(x - 1, y)
        elif c == 1:
            print(ft.sum_range(x - 1, y))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def update(index,y):
    targ[index] += y
    index = (index - 1) // 2
    while True:
        targ[index] = targ[index*2 + 1] + targ[index*2 + 2]
        if index <= 0:
            break
        index = (index - 1) // 2

def find(ini,end,node,inode,enode):
    #print(ini,end,node,inode,enode)
    if ini > enode or inode > end:
        return 0
    elif (inode >= ini and end >= enode) or inode == enode:
        return targ[node]
    else:
        ininum = find(ini,end,node*2 + 1,inode,(inode+enode)//2)
        endnum = find(ini,end,node*2 + 2,(inode+enode)//2 + 1,enode)
        return ininum + endnum

num,query = (int(n) for n in input().split(' '))
ln = 2 ** math.ceil(math.log2(num)) - 1
if num == 1:
    tail = 2
else:
    tail = 2 ** math.ceil(math.log2(num)) - num
targ = [0] * (ln + num + tail)
for q in range(query):
    #print(targ)
    qtype,temp1,temp2 = (int(n) for n in input().split(' '))
    if qtype == 0:
        update(temp1+ln-1,temp2)
    else:
        print(find(temp1-1,temp2-1,0,0,ln))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

    # sum(A[1] ... A[i])
    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)

    # A[i] += x
    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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

    # sum(A[1] ... A[i])
    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)

    # A[i] += x
    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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

    # sum(A[1] ... A[i])
    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)

    # A[i] += x
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
        # print(sg.data)
        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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)))  # honto ha int() iranai
        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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8


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)
            # print(bit.tree)
        elif c == 1:
            print(bit.sum(y) - bit.sum(x-1))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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