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

Solution (Python):
"""
n,q = map(int,input().split())
a = list(map(int,input().split()))

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

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

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

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele = 0


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(a)

for _ in range(q):
    q1,p,x = map(int,input().split())
    if q1 == 0:
        update(p, seg[p+num-1] + x)
    else:
        print(query(p, x))
"""



from typing import Callable, List, TypeVar

T = TypeVar("T")

class SegmentTree:
    """Segment Tree"""

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[T], e: T, op: Callable[[T, T], T]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: T) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> T:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> T:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> T:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[T], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0

def add(x, y):
    return x + y

n,q = map(int,input().split())
a = list(map(int,input().split()))
tree = SegmentTree(a, 0, add)

for _ in range(q):
    t,p,x = map(int,input().split())
    if t == 0:
        tree.set(p, tree.get(p) + x)
    else:
        print(tree.prod(p, x))

Solution (Python):
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] += x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: 
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]

N, Q = map(int, input().split())
A = list(map(int, input().split()))
st = SegmentTree(A)
ans = []
for _ in range(Q):
    t, i, j = map(int, input().split())
    if t:
        ans.append(st.query(i, j))
    else:
        st.update(i, j)

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

Solution (Python):
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys


@njit((i8[:], i8), cache=True)
def sum(tree, i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8, i8), cache=True)
def add(tree, size,  i, x):
    while i <= size:
        tree[i] += x
        i += i & -i


@njit((i8[:], i8, i8), cache=True)
def range_sum(tree, l, r):
    return sum(tree, r) - sum(tree, l)


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

    bit = np.array([0] + sys.stdin.buffer.readline().split(), np.int64)
    for i in range(1, n+1):
        if i + (i & -i) < n + 1:
            bit[i + (i & -i)] += bit[i]

    for y in sys.stdin.buffer.readlines():
        q, p, x = map(int, y.split())
        if q:
            print(range_sum(bit, p, x))
        else:
            add(bit, n, p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def sum(tree, i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s


def add(tree, size,  i, x):
    while i <= size:
        tree[i] += x
        i += i & -i


def range_sum(tree, l, r):
    return sum(tree, r) - sum(tree, l)


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

    bit = [0] + list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(1, n+1):
        if i + (i & -i) < n + 1:
            bit[i + (i & -i)] += bit[i]

    for y in sys.stdin.buffer.readlines():
        q, p, x = map(int, y.split())
        if q:
            print(range_sum(bit, p, x))
        else:
            add(bit,n, p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n+1):
            if i + (i & -i) < n + 1:
                self.tree[i + (i & -i)] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n+1):
            x = i + (i & -i)
            if x < n + 1:
                self.tree[x] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit, i8, jitclass
import sys

spec = [
    ("size", i8),
    ("tree", i8[:])
]


@jitclass(spec)
class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = np.array([0] + arr, np.int64)
        for i in range(1, n+1):
            x = i + (i & -i)
            if x < n + 1:
                self.tree[x] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import sys
from numba import njit, i8, jitclass

spec = [
    ("size", i8),
    ("tree", i8[:])
]


@jitclass(spec)
class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = np.array([0] + arr, np.int64)
        for i in range(1, n+1):
            if i + (i & -i) < n + 1:
                self.tree[i + (i & -i)] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np


class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = np.array([0] + arr)
        for i in range(1, n+1):
            if i + (i & -i) < n + 1:
                self.tree[i + (i & -i)] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """
        (a0+a1+...+ai < x となる最大の i (存在しない時は -1 ) , その時の a0+a1+...+ai )
        a0+a1+...+ai <= x としたい場合は equal = True
        二分探索であるため、ai>=0 を満たす必要がある
        """
        sum_ = 0
        pos = -1    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: 
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))




import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
A = map(int, input().split())
B = Bit(N)
B.built(A)
for _ in range(Q):
    a, b, c = map(int, input().split())
    if a: print(B.get(b,c))
    else: B.add(b,c)

Solution (Python):
import sys


class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n+1):
            if i + (i & -i) < n + 1:
                self.tree[i + (i & -i)] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

    def build(self, arr):
        
        for i, a in enumerate(arr):
            self.add(i+1, a)

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

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

    def range_sum(self, l, r):
        
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    bit.build(map(int, sys.stdin.buffer.readline().split()))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

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

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


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(n):
        bit.add(i+1, a[i])
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

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

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


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(n):
        bit.add(i+1, a[i])
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

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

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


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(n):
        bit.add(i+1, a[i])
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

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

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


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(n):
        bit.add(i+1, a[i])
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

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

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): 
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N,Q = map(int,input().split())
A = list(map(int,input().split()))
Tree = SegmentTree(A, segfunc, 0)
for _ in range(Q):
  query, a,b = map(int,input().split())
  if query == 0:
    Tree.add(a,b)
  else:
    print(Tree.sum(a,b))

Solution (Python):
n,q = map(int,input().split())
a = list(map(int,input().split()))

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

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

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

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele = 0


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(a)

for _ in range(q):
    q1,p,x = map(int,input().split())
    if q1 == 0:
        update(p, seg[p+num-1] + x)
    else:
        print(query(p, x))