Problem:


RSQ and 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.

  
getSum(s, t): report the sum of as, as+1, ..., at.

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 s t

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

Output

For each getSum operation, print the sum;

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

  1 ≤ s ≤ t ≤ n

  0 ≤ x < 1000

Sample Input 1

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

Sample Output 1

4
8

Sample Input 2

4 3
1 1 4
0 1 4 1
1 1 4

Sample Output 2

0
4



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


Sample output:
4
8

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


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

    def get_sum(self, s, t):
        return self.__get_sum(1, 1, self.tn, s, t)

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

    def add(self, s, t, x):
        self.__add(1, 1, self.tn, s, t, x)

    def __add(self, c, l, r, s, t, x):

        if 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)
buf = []
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        st.add(*map(int, query[1:]))
    else:
        buf.append(st.get_sum(*map(int, query[1:])))
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
def f(l):
    for i in range(1, len(l)):
        l[i] += l[i-1]
    return l


n, q = map(int, input().split())
A = [0] * (n+2)

for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        s, t, x = query[1:]
        A[s] += x
        A[t+1] -= x
    else:
        s, t = query[1:]
        sum = f(f(A[:]))
        print(sum[t] - sum[s-1])

Submission status: Accepted

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

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

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


class Solve:
    def __init__(self, n):
        self.n = n
        self.p = BinaryIndexedTree(n + 1)
        self.q = BinaryIndexedTree(n + 1)

    def add(self, s, t, x):
        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 get_sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

    def dump(self):
        print(*(self.get_sum(i, i) for i in range(self.n + 1)))


n, q = map(int, input().split())
st = Solve(n)
buf = []
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        st.add(*map(int, query[1:]))
    else:
        buf.append(st.get_sum(*map(int, query[1:])))
print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
import sys

def solve():
    N, Q = map(int, sys.stdin.readline().split())

    p = FenwickTree(N + 1)
    q = FenwickTree(N + 1)

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

        if query[0] == '0':
            c, s, t, x = map(int, query.split())
            s -= 1
            p.add(s, -s*x)
            p.add(t, t*x)
            q.add(s, x)
            q.add(t, -x)
        else:
            c, s, t = map(int, query.split())
            s -= 1

            res = p.get_sum(t) + q.get_sum(t)*t
            res -= p.get_sum(s) + q.get_sum(s)*s

            print(res)

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

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

        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,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


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

    def add(self, a, b, x, k, l, r):
        def ina(k, l, r):
            if a <= l and r <= b:
                self.A[k] += x
            elif l < b and a < r:
                self.B[k] += (min(b, r) - max(a, l)) * x
                m = (l+r) // 2
                ina(k*2+1, l, m)
                ina(k*2+2, m, r)

        ina(k, l, r)

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

            if a <= l and r <= b:
                return self.A[k] * (r - l) + self.B[k]

            res = (min(b, r) - max(a, l)) * self.A[k]
            m = (l+r) // 2
            res += inq(k*2+1, l, m)
            res += inq(k*2+2, m, r)
            return res

        return inq(k, l, r)

def main():
    n,q = LI()
    qa = [LI() for _ in range(q)]

    ras = RangeAddSum(n)
    rr = []
    for qi in qa:
        s = qi[1] - 1
        t = qi[2]
        if qi[0] == 0:
            x = qi[3]
            ras.add(s, t, x, 0, 0, n)
        else:
            rr.append(ras.query(s, t, 0, 0, n))

    return JA(rr, "\n")

# start = time.time()
print(main())
# pe(time.time() - start)

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:
      s,t,x = y
      data0.add(s,-x*(s-1))
      data0.add(t+1,x*t)
      data1.add(s,x)
      data1.add(t+1,-x)
    else:
      s,t = y
      ans.append(data1.sum(t)*t+data0.sum(t)-data1.sum(s-1)*(s-1)-data0.sum(s-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_RAQ_and_RSQ():
    """
    Range Add Queryと，Range Sum QueryがどちらもO(logn)
    BIT 2本使う
    1-indexed 半閉区間
    """

    def __init__(self, n):
        self.p = fenwick_tree(n+1)
        self.q = fenwick_tree(n+1)

    def init_array(self, A):
        for i, a in enumerate(A):
            pass

    def add_interval(self, i, j, w):
        """ [i,j]にwを加算 """
        j += 1
        self.p.add(i, -w*i)
        self.p.add(j, w*j)
        self.q.add(i, w)
        self.q.add(j, -w)

    def sum_until(self, i):
        """ [1,c)の和を求める """
        if i <= 0 or self.p.size < i:
            raise IndexError
        return self.p.sum_until(i) + self.q.sum_until(i)*(i)

    def sum_acc(self, i, j):
        """ [i,j] の区間和を取得 """
        return self.sum_until(j+1) - self.sum_until(i)


def main():
    N, Q = (int(i) for i in input().split())
    bit = fenwick_tree_RAQ_and_RSQ(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)
        elif com == 2:
            x = A[0]
            print(bit.sum_until(x))
        else:
            x, y = A
            print(bit.sum_acc(x, y))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


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


def set_width(width):
    set_depth((width - 1).bit_length() + 1)


def get_size(pos):
    ret = pos.bit_length()
    return (1 << (DEPTH - ret))


def up(pos):
    pos += SEGTREE_SIZE // 2
    return pos // (pos & -pos)


def up_propagate(table, pos, binop):
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1]
        )


def force_down_propagate(
    action_table, value_table, pos,
    action_composite, action_force, action_unity
):
    max_level = pos.bit_length() - 1
    size = NONLEAF_SIZE
    for level in range(max_level):
        size //= 2
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            # action_table[i * 2] = action_composite(
            #     action, action_table[i * 2])
            # action_table[i * 2 + 1] = action_composite(
            #     action, action_table[i * 2 + 1])
            action_table[i * 2] += action
            action_table[i * 2 + 1] += action
            action_table[i] = action_unity
            # value_table[i * 2] = action_force(
            #     action, value_table[i * 2], size)
            # value_table[i * 2 + 1] = action_force(
            #     action, value_table[i * 2 + 1], size)
            value_table[i * 2] += action * size
            value_table[i * 2 + 1] += action * size


def force_range_update(
    value_table, action_table, left, right,
    action, action_force, action_composite, action_unity
):
    """
    action_force: action, value, cell_size => new_value
    action_composite: new_action, old_action => composite_action
    """
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            value_table[left] = action_force(
                action, value_table[left], get_size(left))
            action_table[left] = action_composite(action, action_table[left])
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action_force(
                action, value_table[right], get_size(right))
            action_table[right] = action_composite(action, action_table[right])

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def lazy_range_update(
        action_table, value_table, start, end,
        action, action_composite, action_force, action_unity, value_binop):
    "update [start, end)"
    L = up(start)
    R = up(end)
    force_down_propagate(
        action_table, value_table, L,
        action_composite, action_force, action_unity)
    force_down_propagate(
        action_table, value_table, R,
        action_composite, action_force, action_unity)

    # print("action", file=sys.stderr)
    # debugprint(action_table)
    # print("value", file=sys.stderr)
    # debugprint(value_table)
    # print(file=sys.stderr)

    force_range_update(
        value_table, action_table, start, end,
        action, action_force, action_composite, action_unity)
    up_propagate(value_table, L, value_binop)
    up_propagate(value_table, R, value_binop)


def lazy_range_reduce(
    action_table, value_table, start, end,
    action_composite, action_force, action_unity,
    value_binop, value_unity
):
    "reduce [start, end)"
    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

    return range_reduce(value_table, start, end, value_binop, value_unity)


def debugprint(xs, minsize=0, maxsize=None):
    global DEPTH
    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 = ["|"] * DEPTH
    level = 0
    next_level = 2
    for i in range(1, SEGTREE_SIZE):
        if i == next_level:
            level += 1
            next_level *= 2
        width = ((minsize + 1) << (DEPTH - 1 - level)) - 1
        result[level] += strs[i].center(width) + "|"
    print(*result, sep="\n", file=sys.stderr)


def main():
    from operator import add
    # parse input
    N, Q = map(int, input().split())
    set_width(N)

    value_unity = 0
    value_table = [value_unity] * SEGTREE_SIZE
    value_binop = add
    action_unity = 0
    action_table = [action_unity] * SEGTREE_SIZE

    def action_force(action, value, size):
        return action * size + value

    def action_composite(new_action, old_action):
        return new_action + old_action

    for _time in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            # add
            s, t, value = args
            lazy_range_update(
                action_table, value_table, s - 1, t,
                value, action_composite, action_force, action_unity, value_binop)

        else:
            # getSum
            s, t = args
            print(lazy_range_reduce(
                action_table, value_table, s - 1, t,
                action_composite, action_force, action_unity, value_binop, value_unity))

        # print("action", file=sys.stderr)
        # debugprint(action_table)
        # print("value", file=sys.stderr)
        # debugprint(value_table)
        # print(file=sys.stderr)


# tests
T1 = """
3 5
0 1 2 1
0 2 3 2
0 3 3 3
1 1 2
1 2 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
8
"""
T2 = """
4 3
1 1 4
0 1 4 1
1 1 4
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
4
"""


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


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


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 BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

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

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ():
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

import sys
input = sys.stdin.readline

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

R = RAQandRSQ(N)

res = []

for _ in range(Q):
    q, *p = map(int, input().split())
    if q == 0:
        s, t, x = p
        R.add(s, t + 1, x)
    else:
        s, t = p
        res.append(R.sum(s, t + 1))

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,Q = LI()
N0 = 2 ** (N).bit_length()
data = [0 for _ in range(N0*2)]
lazy = [0 for _ in range(N0*2)]

def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) // 2
    rm = (R // (R & -R)) // 2
    while L < R:
        if R <= rm:
            yield R-1
        if L <= lm:
            yield L-1
        L //= 2; R //= 2
    while L:
        yield L-1
        L //= 2

def eval(*ids):
    for i in reversed(ids):
        v = lazy[i]
        if v == 0: continue
        lazy[i*2+1] += v // 2
        lazy[i*2+2] += v // 2
        data[i*2+1] += v // 2
        data[i*2+2] += v // 2

        lazy[i] = 0

def data_add(l,r,x):
    *ids, = gindex(l,r)
    eval(*ids)
    L = l + N0; R = r + N0
    n = 1
    while L < R:
        if R % 2:
            R -= 1
            lazy[R-1] += x * n
            data[R-1] += x * n
        if L % 2:
            lazy[L-1] += x * n
            data[L-1] += x * n
            L += 1
        L //= 2; R //= 2; n *= 2
    for i in ids:
        data[i] = data[i*2+1] + data[i*2+2]

def data_get(l,r):
    eval(*gindex(l,r))
    L = l + N0; R = r + N0

    ret = 0
    while L < R:
        if R % 2:
            R -= 1
            ret += data[R-1]
        if L % 2:
            ret += data[L-1]
            L += 1
        L //= 2; R //= 2
    return ret

for _ in range(Q):
    q = LI()
    if q[0] == 0:
        data_add(q[1],q[2]+1,q[3])
    else:
        print (data_get(q[1],q[2]+1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N + 1
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

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

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

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1

    def upper_bound(self, val):
        if val < 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] <= val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


class RangeSumAdd:
    def __init__(self, N):
        self.bit0 = BinaryIndexTree(N)
        self.bit1 = BinaryIndexTree(N)

    def RangeAdd(self, l, r, x):
        """
        閉区間[l, r]にxを加える
        """
        self.bit0.add(l, -x * (l - 1))
        self.bit0.add(r + 1, x * r)
        self.bit1.add(l, x)
        self.bit1.add(r + 1, -x)

    def getSum(self, i):
        return self.bit0.sum(i) + i * self.bit1.sum(i)

    def RangeSum(self, l, r):
        """
        閉区間[l, r]にxを加える
        """
        return self.getSum(r)-self.getSum(l-1)


if __name__ == "__main__":
    N, Q = map(int, input().split())
    bit = RangeSumAdd(N + 10)
    ans = []

    for _ in range(Q):
        T, *arg = map(int, input().split())
        if T == 0:
            bit.RangeAdd(*arg)
        else:
            ans.append(bit.RangeSum(*arg))

    if ans:
        print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

class LazyBit():
    """区間加算、区間取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_sum: 区間[l, r)の和を求める
    l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit0 = [0] * (n + 1)
        self.bit1 = [0] * (n + 1)

    def _add(self, bit, i, val):
        i = i + 1
        while i <= self.n:
            bit[i] += val
            i += i & -i

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

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(self.bit0, l, -val * l)
        self._add(self.bit0, r,  val * r)
        self._add(self.bit1, l,  val)
        self._add(self.bit1, r, -val)

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._get(self.bit0, r) + r * self._get(self.bit1, r) \
               - self._get(self.bit0, l) - l * self._get(self.bit1, l)

n, q = MAP()
lazyBit = LazyBit(n+1)
for _ in range(q):
    query = input().split()
    if query[0] == "0":  # update
        _, s, t, x = query
        s, t, x = map(int, [s, t, x])
        lazyBit.add(s, t+1, x)

    else:  # find
        _, s, t = query
        s, t = map(int, [s, t])
        print(lazyBit.get_sum(s, t+1))

Submission status: Accepted

Solution code:

def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    lm = (L // (L & -L)) >> 1  # これで成り立つの天才か？
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1
        R >>= 1
    while L:  # Rでもいいけどね
        yield L
        L >>= 1


import operator


class SegmentTreeForRSQandRAQ:  # 区間合計(ホントは何でも良い)クエリ と 区間加算クエリを扱うことにする
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木 もしかしたらバグがあるかも
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        self.lazy = [self.lide] * (2 * self.num)  # 遅延配列
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            v = self.lazy[i]
            if v == self.lide:
                continue
            #########################################################
            # この4つの配列をどう更新するかは問題によって異なる
            self.tree[2 * i + 1] += v >> 1  # 区間加算クエリなので
            self.tree[2 * i + 2] += v >> 1
            self.lazy[2 * i + 1] += v >> 1
            self.lazy[2 * i + 2] += v >> 1
            #########################################################

            self.lazy[i] = self.lide  # 遅延配列を空に戻す

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(_gidx(l, r, self.num))
        #########################################################
        # 区間加算queryのような操作の順序が入れ替え可能な場合これをする必要なないが多くの場合でしたほうがバグが少なく(若干遅くなる)
        # self._lazyprop(*ids)
        #########################################################
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            #########################################################
            # ** 問題によって値のセットの仕方も変えるべし**
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            #########################################################
            x <<= 1  # 区間加算クエリでは上段では倍倍になるはずだよね
            l >>= 1
            r >>= 1
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            #########################################################
            # 関数の先頭でlazy propを省略した場合は、現在のノードにlazyが反映されていないことがある
            # lazyを省略するならここを慎重に書き換えなければならない
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            #########################################################

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*_gidx(l, r, self.num))
        # 2, 区間[l,r)の最小値を求める
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


n, q = map(int, input().split())
ls = [0] * n
seg = SegmentTreeForRSQandRAQ(ls)

for _ in range(q):
    cmd, *tmp = map(int, input().split())
    if cmd == 0:
        s, t, x = tmp
        seg.update(s - 1, t, x)
    else:
        s, t = tmp
        print(seg.query(s - 1, t))