Problem:


Range Add Query (RAQ)

Write a program which manipulates a sequence A = {a1, a2, . . .  , an} with the following operations:

  
add(s, t, x): add x to as, as+1, ..., at.

  
get(i): output the value of ai.

Note that the initial values of ai (i = 1, 2, . . .  , n) are 0.

Input

n q
query1
query2
:
queryq

  In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:

0 s t x 

  or

1 t

  The first digit represents the type of the query. '0' denotes add(s, t, x) and '1' denotes get(i).

Output

For each get operation, print the value.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

  1 ≤ s ≤ t ≤ n

  1 ≤ i ≤ n

  0 ≤ x ≤ 1000
  

Sample Input 1

3 5
0 1 2 1
0 2 3 2
0 3 3 3
1 2
1 3

Sample Output 1

3
5

Sample Input 2

4 3
1 2
0 1 4 1
1 2

Sample Output 2

0
1



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


Sample output:
3
5

Submission status: Wrong Answer

Solution code:
import math


def hoge(s, e, value):
    s += l
    e += l

    for d in range(rank, -1, -1):
        l_end_node, r_end_node = s >> d, e >> d
        l_end_leaf = l_end_node << d, (l_end_node + 1 << d) - 1
        r_end_leaf = r_end_node << d, (r_end_node + 1 << d) - 1

        if l_end_node == r_end_node:
            if l_end_leaf[0] == s and r_end_leaf[1] == e:
                # match
                lazy[l_end_node] += value
                break
        else:
            if l_end_leaf[0] == s:
                # match
                lazy[l_end_node] += value
                s = l_end_leaf[1] + 1
            elif l_end_node+1 < r_end_node:
                # match
                lazy[l_end_node] += value

            if r_end_leaf[1] == e:
                # match
                lazy[r_end_node] += value
                e = r_end_leaf[0]-1
            elif l_end_node+1 < r_end_node:
                # match
                lazy[r_end_node] += value

        if d > 0:
            # propagation
            lazy_left = lazy[l_end_node]
            lazy[l_end_node] = 0
            lazy[l_end_node << 1] += lazy_left
            lazy[(l_end_node << 1)+1] += lazy_left
            if l_end_node != r_end_node:
                lazy_right = lazy[r_end_node]
                lazy[r_end_node] = 0
                lazy[r_end_node << 1] += lazy_right
                lazy[(r_end_node << 1)+1] += lazy_right

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [0]*(2*l)
lazy = [0]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1]-1, query[2]-1, query[3])
    else:
        ap(get_value(query[1]-1))

print("\n".join((str(n) for n in ans)))

Submission status: Wrong Answer

Solution code:
import math


def hoge(s, e, value):
    s += l
    e += l
    d = rank

    while d >= 0 and s <= e:
        l_end_node, r_end_node = s >> d, e >> d
        l_end_leaf = l_end_node << d, (l_end_node + 1 << d) - 1
        r_end_leaf = r_end_node << d, (r_end_node + 1 << d) - 1

        if l_end_node == r_end_node:
            if l_end_leaf[0] == s and r_end_leaf[1] == e:
                # match
                lazy[l_end_node] += value
                break
        else:
            if l_end_leaf[0] == s:
                # match
                lazy[l_end_node] += value
                s = l_end_leaf[1] + 1
            elif l_end_node+1 < r_end_node:
                # match
                lazy[l_end_node+1] += value

            if r_end_leaf[1] == e:
                # match
                lazy[r_end_node] += value
                e = r_end_leaf[0]-1
            elif l_end_node+1 < r_end_node:
                # match
                lazy[r_end_node-1] += value

        if d > 0:
            # propagation
            lazy_left = lazy[l_end_node]
            lazy[l_end_node] = 0
            lazy[l_end_node << 1] += lazy_left
            lazy[(l_end_node << 1)+1] += lazy_left
            if l_end_node != r_end_node:
                lazy_right = lazy[r_end_node]
                lazy[r_end_node] = 0
                lazy[r_end_node << 1] += lazy_right
                lazy[(r_end_node << 1)+1] += lazy_right

        d -= 1

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [0]*(2*l)
lazy = [0]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1]-1, query[2]-1, query[3])
    else:
        ap(get_value(query[1]-1))

print("\n".join((str(n) for n in ans)))

Submission status: Wrong Answer

Solution code:
import math


def hoge(s, e, value):
    s += l
    e += l
    d, l_running, r_running = rank, 1, 1

    while l_running or r_running:
        _s, _e = s, e
        l_end_node, r_end_node = s >> d, e >> d
        l_end_leaf = l_end_node << d, (l_end_node + 1 << d) - 1
        r_end_leaf = r_end_node << d, (r_end_node + 1 << d) - 1

        if l_end_node == r_end_node:
            if l_end_leaf[0] == s and r_end_leaf[1] == e:
                # match
                lazy[l_end_node] += value
                break
        else:
            if l_running:
                if l_end_leaf[0] == s:
                    # match
                    lazy[l_end_node] += value
                    l_running = 0
                elif l_end_node+1 < r_end_node:
                    # match
                    lazy[l_end_node+1] += value

            if r_running:
                if r_end_leaf[1] == e:
                    # match
                    lazy[r_end_node] += value
                    r_running = 0
                elif l_end_node+1 < r_end_node:
                    # match
                    lazy[r_end_node-1] += value

        if d > 0:
            # propagation
            if l_running:
                lazy_left = lazy[l_end_node]
                lazy[l_end_node] = 0
                lazy[l_end_node << 1] += lazy_left
                lazy[(l_end_node << 1)+1] += lazy_left
            if r_running:
                lazy_right = lazy[r_end_node]
                lazy[r_end_node] = 0
                lazy[r_end_node << 1] += lazy_right
                lazy[(r_end_node << 1)+1] += lazy_right

        d -= 1

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [0]*(2*l)
lazy = [0]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1]-1, query[2]-1, query[3])
    else:
        ap(get_value(query[1]-1))

print("\n".join((str(n) for n in ans)))

Submission status: Accepted

Solution code:
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a
    return self.value[x]

  def update(self, x, add, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      pass
    elif left <= x_left and x_right <= right:
      self.value[x] += add
    else:
      self.update(x * 2 + 1, add, left, right)
      self.update(x * 2 + 2, add, left, right)
  
  def query(self, x, total):
    if x < 0:return total
    total += self.value[x]
    return self.query((x - 1) // 2, total)

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
tree = TemplateTree([0] * n)

for _ in range(q):
  lst = list(map(int, input().split()))
  if lst[0] == 0:
    s, t, x = lst[1:]
    tree.update(0, x, s - 1, t - 1)
  else:
    i = lst[1]
    print(tree.query(tree.iter_size - 1 + i - 1, 0))

Submission status: Accepted

Solution code:
N, Q =map(int, input().split())

data = [0]*(N+1)
def add(k, x):
  while k <= N:
    data[k] += x
    k += k & -k
def get(k):
  s = 0
  while k:
    s += data[k]
    k -= k & -k
  return s

ans = []
for q in range(Q):
  a = input()
  if a[0] == "1":
    ans.append(str(get(int(a[2:]))))
  else:
    s, t, x = map(int, a[2:].split())
    add(s, x)
    if t < N:
      add(t+1, -x)
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())

data = [0]*(N+1)
def add(k, x,y):
    while k <= N:
        data[k] += y
        k += k & -k
    x+=1
    while x <= N:
        data[x] -= y
        x += x & -x
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
for i in range(Q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        print(get(t[1]))
    else:
        add(t[1],t[2],t[3])

Submission status: Accepted

Solution code:
from math import log2, ceil


class SegmentTree:
    def __init__(self, n):
        tn = 2 ** ceil(log2(n))
        self.a = [0] * (tn * 2)

    def find(self, c, l, r, i):
        if l == r:
            return self.a[c]
        mid = (l + r) // 2
        if i <= mid:
            return self.a[c] + self.find(c * 2, l, mid, i)
        else:
            return self.a[c] + self.find(c * 2 + 1, mid + 1, r, i)

    def add(self, c, l, r, s, t, x):
        if l == r or l == s and r == t:
            self.a[c] += x
            return
        mid = (l + r) // 2
        if t <= mid:
            self.add(c * 2, l, mid, s, t, x)
        elif s > mid:
            self.add(c * 2 + 1, mid + 1, r, s, t, x)
        else:
            self.add(c * 2, l, mid, s, mid, x)
            self.add(c * 2 + 1, mid + 1, r, mid + 1, t, x)


n, q = map(int, input().split())
st = SegmentTree(n)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        # CAUTION: DSL_2_D: i = 0,1,...,n-1.  DSL_2_E: i = 1,2,...,n.
        s, t, x = map(int, query[1:])
        st.add(1, 1, n, s, t, x)
    else:
        print(st.find(1, 1, n, int(query[1])))

Submission status: Accepted

Solution code:
import sys

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

    ft = FenwickTree(n)

    for qi in range(q):
        query = sys.stdin.readline().rstrip()

        if query[0] == '0':
            c, s, t, x = map(int, query.split())
            ft.add(s, x)
            ft.add(t + 1, -x)
        else:
            c, i = map(int, query.split())

            print(ft.get_sum(i))


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

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

    def get_sum(self, r):
        res = 0

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

        return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math


def hoge(s, e, value):
    s += l
    e += l
    d, l_running, r_running = rank, 1, 1

    while l_running or r_running:
        l_end_node, r_end_node = s >> d, e >> d
        l_end_leaf = l_end_node << d, (l_end_node + 1 << d) - 1
        r_end_leaf = r_end_node << d, (r_end_node + 1 << d) - 1

        if l_end_node == r_end_node:
            if l_end_leaf[0] == s and r_end_leaf[1] == e:
                # match
                lazy[l_end_node] += value
                break
        else:
            if l_running:
                if l_end_leaf[0] == s:
                    # match
                    lazy[l_end_node] += value
                    l_running = 0
                # ??????????????????????????????????????????????¶?????????????????????´???
                elif l_end_node >> 1 << 1 == l_end_node and l_end_node+1 < r_end_node:
                    # match
                    lazy[l_end_node+1] += value

            if r_running:
                if r_end_leaf[1] == e:
                    # match
                    lazy[r_end_node] += value
                    r_running = 0
                elif r_end_node >> 1 << 1 == r_end_node-1 and l_end_node+1 < r_end_node:
                    # match
                    lazy[r_end_node-1] += value

        if d > 0:
            # propagation
            if l_running:
                lazy_left, lazy[l_end_node] = lazy[l_end_node], 0
                lazy[l_end_node << 1] += lazy_left
                lazy[(l_end_node << 1)+1] += lazy_left
            if r_running:
                lazy_right, lazy[r_end_node] = lazy[r_end_node], 0
                lazy[r_end_node << 1] += lazy_right
                lazy[(r_end_node << 1)+1] += lazy_right

        d -= 1

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [0]*(2*l)
lazy = [0]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1]-1, query[2]-1, query[3])
    else:
        ap(get_value(query[1]-1))

print("\n".join((str(n) for n in ans)))

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

def solve():
  ans = []
  N, Q = map(int, input().split())
  data0 = BIT(N+1)
  data1 = BIT(N+1)
  for i in range(Q):
    p,*y = map(int, input().split())
    if p==0:
      l,r,x = y
      data0.add(l,-x*(l-1))
      data0.add(r+1,x*r)
      data1.add(l,x)
      data1.add(r+1,-x)
    else:
      r = y[0]
      ans.append(data1.sum(r)*r+data0.sum(r)-data1.sum(r-1)*(r-1)-data0.sum(r-1))
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

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

    def init_array(self, A):
        for i, a in enumerate(A, start=1):
            self.add(i, a)

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

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

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


class fenwick_tree_interval_add(fenwick_tree):
    """
    区間加算と，一点取得がO(log n)
    区間和を求めるのは，区間の長さをkとして，O(k)
    """

    def __init__(self, n):
        super().__init__(n)

    def init_array(self, A):
        for i in range(self.size):
            if i != 0:
                self.__add(i+1, A[i] - A[i-1])
            else:
                self.__add(i+1, A[i])

    def add_interval(self, i, j, w):
        if i <= 0 or self.size < j or j < i:
            raise IndexError
        self.__add(i, w)
        if j < self.size:
            self.__add(j+1, -w)

    def get_val(self, i):
        if i <= 0 or self.size < i:
            raise IndexError
        return self.__sum_until(i)

    def __sum_until(self, i):
        return super().sum_until(i)

    def __add(self, i, x):
        super().add(i, x)


def main():
    N, Q = (int(i) for i in input().split())
    bit = fenwick_tree_interval_add(N)
    for _ in range(Q):
        com, *A = (int(i) for i in input().split())
        if com == 0:
            (x, y, w) = A
            bit.add_interval(x, y, w)
        else:
            x = A[0]
            print(bit.get_val(x))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 2 ** 31 - 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def set_depth(depth):
    global N, SEGTREE_SIZE, NONLEAF_SIZE
    N = depth
    SEGTREE_SIZE = 1 << N
    NONLEAF_SIZE = 1 << (N - 1)


def range_update(table, left, right, action):
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            table[left] = action(table[left])
            left += 1
        if right & 1:
            right -= 1
            table[right] = action(table[right])
        left //= 2
        right //= 2


def down_propagate_to_leaf(table, pos, binop, unity):
    pos += NONLEAF_SIZE
    down_propagate(table, pos, binop, unity)
    return table[pos]


def down_propagate(table, pos, binop, unity):
    for max_level in range(N):
        if 2 ** max_level > pos:
            max_level -= 1
            break
    for level in range(max_level):
        i = pos >> (max_level - level)

        table[i * 2] = binop(table[i], table[i * 2])
        table[i * 2 + 1] = binop(table[i], table[i * 2 + 1])
        table[i] = unity


def set_items(table, xs):
    for i, x in enumerate(xs, NONLEAF_SIZE):
        table[i] = x


def debugprint(xs, minsize=0, maxsize=None):
    strs = [str(x) for x in xs]
    if maxsize != None:
        for i in range(NONLEAF_SIZE, SEGTREE_SIZE):
            strs[i] = strs[i][:maxsize]
    s = max(len(s) for s in strs[NONLEAF_SIZE:])
    if s > minsize:
        minsize = s

    result = ["|"] * N
    level = 0
    next_level = 2
    for i in range(1, SEGTREE_SIZE):
        if i == next_level:
            level += 1
            next_level *= 2
        width = ((minsize + 1) << (N - 1 - level)) - 1
        result[level] += strs[i].center(width) + "|"
    print(*result, sep="\n")


def main():
    from operator import add
    N, Q = map(int, input().split())
    depth = N.bit_length() + 1
    set_depth(depth)
    table = [0] * SEGTREE_SIZE

    for time in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            # update
            s, t, value = args
            range_update(table, s, t + 1, lambda x: x + value)

        else:
            # find
            print(down_propagate_to_leaf(
                table, args[0], add, 0))


# tests
T1 = """
3 5
0 1 2 1
0 2 3 2
0 3 3 3
1 2
1 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    5
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

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

    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 add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.el[i]
        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, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True         """
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        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, s):
        """ [a0, a1, a2, ...] """
        return self.el[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.el[:self.n]:
            yield s

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


class BitImos:
    def __init__(self, n):
        self.n = n
        self.p = Bit(self.n + 1)
        self.q = Bit(self.n + 1)

    def add(self, s, t, x):
        """ 区間は閉区間 [s,t] で与えられる。原理は Imos法 と同じ。"""
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        """ 半閉区間[s,t)の累積和を与える """
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

    def __getitem__(self, s):
        """ 区間加算後の s 番目の要素をO(log N)で取り出す。Imos法だとこの操作にO(N)かかる。"""
        return self.q.sum(s+1)

    def __iter__(self):
        """ max(self) で普段 Imos法 でやってることが出来る。"""
        for t in range(self.n):
            yield self.q.sum(t+1)

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        return text1

N, Q = map(int, input().split())
BI = BitImos(N)

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 0:
        BI.add(q[1]-1,q[2]-1,q[3])
    else:
        print(BI[q[1]-1])

Submission status: Accepted

Solution code:
class LazySegTree:
    INF = 0
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.lazy = [self.INF]*(2*self.n-1)

    def update(self,a,b,k,x,l,r):
        if r<=a or b<=l :return
        if a<=l and r<=b:
            self.lazy[k] += x
            return
        self.update(a,b,k*2+1,x,l,(l+r)//2)
        self.update(a,b,k*2+2,x,(l+r)//2,r)

    def Update(self,a,b,x):
        return self.update(a,b,0,x,0,self.n)

    def search(self,k,l,r):
        k += self.n-1
        res = self.INF
        while 0<=k:
            res += self.lazy[k]
            k = (k-1)//2
        return res

    def Search(self,k):
        return self.search(k,0,self.n)

def main():
    n,m = map(int,input().split())
    lst = LazySegTree(n)
    for _ in range(m):
        q = list(map(int,input().split()))
        if q[0] == 0:
            lst.Update(q[1]-1,q[2],q[3])
        else        :
            print(lst.Search(q[1]-1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Range Add Query (RAQ)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E&lang=ja

"""
import sys


def main(args):
    def add(b, k, x):
        while k <= n:
            b[k] += x
            k += k & -k

    def get(b, k):
        s = 0
        while k > 0:
            s += b[k]
            k -= k & -k
        return s

    n, queries = map(int, input().split())
    bit0 = [0] * (n + 1)
    bit1 = [0] * (n + 1)

    for _ in range(queries):
        q, *args = input().split()
        args = [int(a) for a in args]
        if q == '1':
            res = get(bit0, args[0]) + get(bit1, args[0]) * args[0]
            res -= get(bit0, args[0] - 1) + get(bit1, args[0] - 1) * (args[0] - 1)
            print(res)
        else:
            add(bit0, args[0], -args[2] * (args[0] - 1))
            add(bit1, args[0], args[2])
            add(bit0, args[1] + 1, args[2]* args[1])
            add(bit1, args[1] + 1, -args[2])


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
class SegmentTree:
    seg_len = 1
    node = []
    def __init__(self, n):
        while self.seg_len < n:
            self.seg_len <<= 1
        self.node = [ 0 for _ in range(self.seg_len*2) ]

    def add(self, l, r, x):
        l += self.seg_len
        r += self.seg_len
        while l < r:
            if l & 1 == 1:
                self.node[l] += x
                l += 1
            if r & 1 == 1:
                self.node[r-1] += x
                r -= 1
            l >>= 1; r >>= 1;

    def get(self, idx):
        idx += self.seg_len
        ret = self.node[idx]
        while True:
            idx >>= 1
            if idx == 0:
                break
            ret += self.node[idx]
        return ret

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

for _ in range(q):
    query = [ int(x) for x in input().split() ]
    if len(query) == 4:
        _, l, r, x = query
        l -= 1; r -= 1
        seg_tree.add(l, r+1, x)
    if len(query) == 2:
        _, i = query
        i -= 1;
        print(seg_tree.get(i))

Submission status: Accepted

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

class LazyPropSegmentTree:
    def __init__(self, lst, op, apply, comp, e, identity):
        self.n = len(lst)
        self.depth = (self.n - 1).bit_length()
        self.N = 1 << self.depth
        self.op = op # binary operation of elements
        self.apply = apply # function to apply to an element
        self.comp = comp # composition of functions
        self.e = e # identity element w.r.t. op
        self.identity = identity # identity element w.r.t. comp
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def _indices(self, l, r):
        left = l + self.N; right = r + self.N
        left //= (left & (-left)); right //= (right & (-right))
        left >>= 1; right >>= 1
        while left != right:
            if left > right: yield left; left >>= 1
            else: yield right; right >>= 1
        while left > 0: yield left; left >>= 1
    
    # propagate self.lazy and self.v in a top-down manner
    def _propagate_topdown(self, *indices):
        identity, v, lazy, apply, comp = self.identity, self.v, self.lazy, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lazy[k << 1] = comp(lazy[k << 1], x)
            lazy[(k << 1)|1] = comp(lazy[(k << 1)|1], x)
            v[k << 1] = apply(v[k << 1], x)
            v[(k << 1)|1] = apply(v[(k << 1)|1], x)
            lazy[k] = identity # propagated

    # propagate self.v in a bottom-up manner
    def _propagate_bottomup(self, indices):
        v, op = self.v, self.op
        for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1])

    # update for the query interval [l, r) with function x
    def update(self, l, r, x):
        *indices, = self._indices(l, r)
        self._propagate_topdown(*indices)
        
        N, v, lazy, apply, comp = self.N, self.v, self.lazy, self.apply, self.comp
        
        # update self.v and self.lazy for the query interval [l, r)
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x)
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                lazy[left] = comp(lazy[left], x)
                v[left] = apply(v[left], x)
                left += 1
            if right & 1:
                right -= 1
                lazy[right] = comp(lazy[right], x)
                v[right] = apply(v[right], x)
            left >>= 1; right >>= 1
        self._propagate_bottomup(indices)
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        # calculate the answer for the query interval [l, r)
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)

N, Q = map(int, input().split())
op = lambda x, y: x+y
apply = lambda x, f: x+f
comp = lambda f, g: f+g
e = 0
identity = 0
A = [e] * N
lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity)
ans = []
for _ in range(Q):
    t, *arg, = map(int, input().split())
    if t == 0:
        s, t, x = arg
        lpsg.update(s-1, t, x)
    else:
        ans.append(lpsg[arg[0]-1])
print('\n'.join(map(str, ans)))