Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 p x: a_p \gets a_p + x

1 l r: Print \sum_{i = l}^{r - 1}{a_i}.

Constraints

1 \leq N, Q \leq 500,000

0 \leq a_i, x \leq 10^9

0 \leq p < N

0 \leq l_i < r_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Sample Output 1

15
7
25
6



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


Sample output:
15
7
25
6

Submission status: Accepted

Solution code:
class fenwick_tree:
    def __init__(self, n=0, T=int):
        self._n = n
        self.data = [T() for _ in range(n)]
        self.T = T
    
    def add(self, p, x):
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = self.T()
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
t = fenwick_tree(n)
a = list(map(int, input().split()))
for i in range(n):
    t.add(i, a[i])
for _ in range(q):
    qtype, op1, op2 = map(int, input().split())
    if qtype == 0:
        t.add(op1, op2)
    else:
        print(t.sum(op1, op2))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline


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():
    # https://judge.yosupo.jp/problem/point_add_range_sum
    _, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    ans = []
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l, r)
        else:
            ans.append(fwt.query(l-1, r-1))
    print(*ans, sep="\n")


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
    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__":
    yosupo()
    # aoj()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline


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():
    # https://judge.yosupo.jp/problem/point_add_range_sum
    _, 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())
        if type_ == 0:
            fwt.add(l, r)
        else:
            print(fwt.query(l-1, r-1))


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
    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__":
    yosupo()
    # aoj()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # Fenwick Tree
    N = bit = None

    def init(n):
        nonlocal N, bit
        N = n
        bit = [0] * (N + 1)  # 1-origin

    def bit_add(pos, val):
        assert pos > 0
        x = pos
        while x <= N:
            bit[x] += val
            x += x & -x  # (x & -x) = rightmost 1 = block width

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

    # parse input
    N, Q = map(int, input().split())
    init(N)
    AS = list(map(int, input().split()))
    for i, a in enumerate(AS):
        bit_add(i + 1, a)

    for _q in range(Q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit_add(b + 1, c)
        else:
            print(bit_sum(c) - bit_sum(b))


# tests
T1 = """
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
7
25
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


# Fenwick Tree
def init(n):
    global N, bit
    N = n
    bit = [0] * (N + 1)  # 1-origin


def bit_add(pos, val):
    assert pos > 0
    x = pos
    while x <= N:
        bit[x] += val
        x += x & -x  # (x & -x) = rightmost 1 = block width


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


def bit_bisect(lower):
    "find a s.t. v1 + v2 + ... + va >= lower"
    x = 0
    k = 1 << (N.bit_length() - 1)  # largest 2^m <= N
    while k > 0:
        if (x + k <= N and bit[x + k] < lower):
            lower -= bit[x + k]
            x += k
        k //= 2
    return x + 1


def main():
    # parse input
    N, Q = map(int, input().split())
    init(N)
    AS = map(int, input().split())
    for i, a in enumerate(AS):
        bit_add(i + 1, a)

    for _q in range(Q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit_add(b + 1, c)
        else:
            print(bit_sum(c) - bit_sum(b))


# tests
T1 = """
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
7
25
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


# Fenwick Tree
def init(n):
    global N, bit
    N = n
    bit = [0] * (N + 1)  # 1-origin


def bit_add(pos, val):
    assert pos > 0
    x = pos
    while x <= N:
        bit[x] += val
        x += x & -x  # (x & -x) = rightmost 1 = block width


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


def bit_bisect(lower):
    "find a s.t. v1 + v2 + ... + va >= lower"
    x = 0
    k = 1 << (N.bit_length() - 1)  # largest 2^m <= N
    while k > 0:
        if (x + k <= N and bit[x + k] < lower):
            lower -= bit[x + k]
            x += k
        k //= 2
    return x + 1


def main():
    # parse input
    N, Q = map(int, input().split())
    init(N)
    AS = list(map(int, input().split()))
    for i, a in enumerate(AS):
        bit_add(i + 1, a)

    for _q in range(Q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit_add(b + 1, c)
        else:
            print(bit_sum(c) - bit_sum(b))


# tests
T1 = """
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
7
25
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    #you can use this function when the BIT has only non-negative values.
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x


N,Q = list(map(int,input().split()))
A = list(map(int,input().split()))
bit = BIT(A)

for i in range(Q):
    f,a,b = list(map(int,input().split()))
    if f==0:
        bit.add(a, b)
    else:
        if a==0:
            print(bit.sum(b-1))
        else:
            print(bit.sum(b-1)-bit.sum(a-1))

Submission status: Accepted

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
A = I[2:2 + N]
XYZ = I[2 + N:]
X, Y, Z = XYZ[::3], XYZ[1::3], XYZ[2::3]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)
for idx, val in enumerate(A):
    BIT.add(idx + 1, val)
for x, y, z in zip(X, Y, Z):
    if x:
        print(BIT.sum(z) - BIT.sum(y))
    else:
        BIT.add(y + 1, z)

Submission status: Accepted

Solution code:
from typing import Optional, Sequence


class BinaryIndexedTree:
    """Binary Indexed Tree (Fenwick Tree): O(logN)

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

    __slots__ = ["_size", "_tree", "is_zero_origin"]

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

        if initial_values:
            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_origin:
            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] in 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] in O(logN)."""
        if not self.is_zero_origin:
            left -= 1
        return self.sum(right) - self.sum(left)


def point_add_range_sum():
    # https://judge.yosupo.jp/problem/point_add_range_sum
    N, Q, *X = map(int, open(0).read().split())
    A, queries = X[:N], X[N:]
    tree = BinaryIndexedTree(N, A)
    res = []
    for com, x, y in zip(*[iter(queries)] * 3):
        if com:
            res.append(tree.range_sum(x, y))
        else:
            tree.add(x, y)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    point_add_range_sum()

Submission status: Accepted

Solution code:
# Date [ 2020-09-08 00:04:04 ]
# Problem [ b.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class BinaryIndexedTree:
    def __init__(self, n):
        '''1-index'''
        self.size = n + 1
        self.data = [0] * self.size
        self.element = [0] * self.size
        self.depth = 1 << n.bit_length() - 1
    
    def build(self, array):
        for i, x in enumerate(array):
            self.add(i, x)

    def add(self, i, v):
        self.element[i] += v; i += 1 # 1-index
        while i < self.size:
            self.data[i] += v
            i += i & -i
    
    def sum(self, i):
        ret = 0; i += 1 # 1-index
        while i > 0:
            ret += self.data[i]
            i -= i & -i
        return ret
    
    def query(self, l, r=None):
        '''get sum [l, r)'''
        if r == None: return self.element[l]
        return self.sum(r) - self.sum(l-1)

    def lower_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] < v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1
    
    def upper_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] <= v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1

def Main():
    n, q = read_ints()
    bit = BinaryIndexedTree(n)
    a = read_int_list()
    bit.build(a)
    for _ in range(q):
        t, l, r = read_ints()
        if t == 0:
            bit.add(l, r)
        else:
            print(bit.query(l, ~-r))    

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    # a - 1の場所にwを追加する
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    # a未満の数字が何個あるか
    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

N, Q = getNM()
A = getList()
query = [getList() for i in range(Q)]

# 全部1-indexになるので注意
bit = BIT(N + 1)
for i in range(N):
    # [1, 2, 3, 4, 5]の場合
    # 1番目(0 + 1)に１を
    # 2番目(1 + 1)に２を置く
    bit.add(i + 1, A[i])

for a, b, c in query:
    if a == 0:
        bit.add(b + 1, c)
    else:
        # [1, 2, 3, 4, 5]の[0, 3)について聞きたい時
        # bit.get(0 + 1, 3 + 1)
        print(bit.cum(b + 1, c + 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

a = list(map(int,input().split()))
for i in range(N):
    BIT_update(i+1,a[i])

for i in range(Q):
    a,b,c = map(int,input().split())
    if a == 0:
        BIT_update(b+1,c)
    else:
        print(BIT_query(c)-BIT_query(b))

Submission status: Accepted

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


class BinaryIndexedTree:
    """一点加算、区間総和クエリをそれぞれO(logN)で答えるデータ構造。"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexedTreeを構築する。O(N)"""
        for i, val in enumerate(array):
            self.bit[i + 1] = val
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加算する。O(logN)"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def sum(self, l, r):
        """区間[l, r)の和を求める。O(logN)"""
        return self._sum(r) - self._sum(l)

    def bisect_left(self, val):
        """区間[0, ind)の和がval以上になる最小のindを求める。O(logN)"""
        if val <= 0:
            return 0
        ind = 0
        k = 1 << self.size.bit_length()
        while k:
            if ind + k <= self.size and self.bit[ind + k] < val:
                val -= self.bit[ind + k]
                ind += k
            k >>= 1
        return ind + 1


n, q = map(int, input().split())
a = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]


bit = BinaryIndexedTree(n)
bit.build(a)
for flag, l, r in queries:
    if flag:
        print(bit.sum(l, r))
    else:
        bit.add(l, r)  # l = index, r = val

Submission status: Accepted

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

class SegmentTree():
    def __init__(self,A,n,ide_ele):
        self.ide_ele=ide_ele
        self.num =2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=A[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=segfunc(self.seg[2*i+1],self.seg[2*i+2])

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

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,self.seg[p])
            if q&1 == 1:
                res = segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,self.seg[p])
        else:
            res = segfunc(segfunc(res,self.seg[p]),self.seg[q])
        return res
N,Q = list(map(int,input().split()))
A = list(map(int,input().split()))
ST = SegmentTree(A,N,0)
for i in range(Q):
    n,p,x = list(map(int,input().split()))
    if n==1:
        print(ST.query(p,x))
    else:
        A[p] += x
        ST.update(p,A[p])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

# BinaryIndexedTree
# O(logN)で累積和取得と値の更新
# add(i,x)...i番目にxを加算
# sum(i,j)...[i,j)の累積和を取得
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

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

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a

n,q=map(int,input().split())
a=list(map(int,input().split()))
Bit=BinaryIndexedTree(n)
for i in range(n):Bit.add(i,a[i])
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    Bit.add(a,b)
  else:
    print(Bit.sum(a,b))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, stdin


def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def query(bit, start, stop):
    if start == 0:
        return bit_sum(bit, stop - 1)
    else:
        return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)


readline = stdin.readline
setrecursionlimit(10 ** 6)

N, Q = map(int, readline().split())
a = list(map(int, readline().split()))

bit = [0] * N
for i in range(N):
    bit_add(bit, i, a[i])

result = []
for _ in range(Q):
    Query = readline()
    if Query[0] == '0':
        _, p, x = map(int, Query.split())
        bit_add(bit, p, x)
    elif Query[0] == '1':
        _, l, r = map(int, Query.split())
        result.append(query(bit, l, r))

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

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree_Exception(Exception):
    pass

class Binary_Indexed_Tree():
    def __init__(self,N,L=[]):
        """calcを演算とするN項のBinary Indexed Treeを作成

        N:要素数
        """
        self.calc=lambda x,y:x+y
        self.unit=0

        N=max(N,len(L))

        k=1
        d=1

        while k<N:
            k*=2
            d+=1

        X=[None]+[0]*k

        self.num=k
        self.depth=d

        if L:
            for i in range(len(L)):
                p=i+1
                while p<=k:
                    X[p]+=L[i]
                    p+=p&(-p)
        self.data=X

    def index(self,k,index=1):
        """第k要素の値を出力する.

        k:数列の要素
        index:先頭の要素の番号
        """

        p=k+(1-index)
        return self.sub_array(p,p)

    def add(self,k,x,index=1):
        """第k要素にx加え,更新を行う.

        k:数列の要素
        x:更新後の値
        index:先頭の要素の番号
        """
        p=k+(1-index)
        while p<=self.num:
            self.data[p]+=x
            p+=p&(-p)

    def update(self,k,x,index=1):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """

        a=self.index(k,index)
        y=x-a

        self.add(k,y,index)

    def sub_array(self,From,To,index=1):
        """第From要素から第To要素までの総和を求める.

        From:始まり
        To:終わり
        index:先頭の要素の番号
        """
        alpha=max(1,From+(1-index))
        beta=min(self.num,To+(1-index))
        return self.__section(beta)-self.__section(alpha-1)

    def __section(self,To):
        S=0
        x=To
        while x>0:
            S+=self.data[x]
            x-=x&(-x)
        return S
#================================================
N,Q=map(int,input().split())
A=list(map(int,input().split()))
B=Binary_Indexed_Tree(N,A)

X=[]
for _ in range(Q):
    t,u,v=map(int,input().split())
    if t==0:
        B.add(u,v,0)
    else:
        X.append(B.sub_array(u,v-1,0))
print("\n".join(map(str,X)))

Submission status: Accepted

Solution code:
# Date [ 2020-09-08 00:04:04 ]
# Problem [ b.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class BinaryIndexedTree:
    def __init__(self, n):
        '''1-index'''
        self.size = n + 1
        self.data = [0] * self.size
        self.element = [0] * self.size
        self.depth = 1 << n.bit_length() - 1
    
    def build(self, array):
        for i, x in enumerate(array):
            self.add(i, x)

    def add(self, i, v):
        self.element[i] += v; i += 1 # 1-index
        while i < self.size:
            self.data[i] += v
            i += i & -i
    
    def sum(self, i):
        ret = 0; i += 1 # 1-index
        while i > 0:
            ret += self.data[i]
            i -= i & -i
        return ret
    
    def query(self, l, r=None):
        '''get sum [l, r)'''
        if r == None: return self.element[l]
        return self.sum(r) - self.sum(l-1)

    def lower_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] < v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1
    
    def upper_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] <= v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1

def Main():
    n, q = read_ints()
    bit = BinaryIndexedTree(n)
    a = read_int_list()
    bit.build(a)
    for _ in range(q):
        t, l, r = read_ints()
        if t == 0:
            bit.add(l, r)
        else:
            print(bit.query(l, ~-r))    

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
def RSQ_add(i, x):
    while True:
        if i > n:
            break
        b[i] += x
        i += i & -i

def RSQ_getsum(i):
    s = 0
    while True:
        if i <= 0:
            break
        s += b[i]
        i -= i & -i
    return s

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    RSQ_add(i + 1, a[i])
for _ in range(q):
    x, y, z = map(int, input().split())
    if x == 0:
        RSQ_add(y + 1, z)
    else:
        ans = RSQ_getsum(z) - RSQ_getsum(y)
        print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
NN = 19
BIT = [0] * (2 ** NN + 1)

def addbit(i, x=1):
    i += 1
    while i <= 2**NN:
        BIT[i] += x
        i += i & (-i)

def getsum(i):
    ret = 0
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret

N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
for i, a in enumerate(A):
    addbit(i, a)

for _ in range(Q):
    a, b, c = map(int, input().split())
    if a == 0:
        addbit(b, c)
    else:
        print(getsum(c) - getsum(b))