Problem:
RSQ and RAQ Write a program which manipulates a sequence A = { a 1 , a 2 , . . .  , a n } with the following operations:  add(s, t, x) : add x to a s , a s+1 , ..., a t .  getSum(s, t) : report the sum of a s , a s+1 , ..., a t .  Note that the initial values of a i ( i = 1, 2, . . .  , n ) are 0. Input  n  q  query 1  query 2 : query q  In the first line, n (the number of elements in A ) and q (the number of queries) are given. Then, i th query query i 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

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

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

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


print(main())

Solution (Python):

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

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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
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
            action_table[i * 2 + 1] += action
            action_table[i] = action_unity
            
            
            
            
            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)

    
    
    
    
    

    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
    
    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:
            
            s, t, value = args
            lazy_range_update(
                action_table, value_table, s - 1, t,
                value, action_composite, action_force, action_unity, value_binop)

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

        
        
        
        
        



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

Solution (Python):
class BinaryIndexedTree():  
    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)))

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

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


class BinaryIndexTree:  
    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")

Solution (Python):
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":  
        _, s, t, x = query
        s, t, x = map(int, [s, t, x])
        lazyBit.add(s, t+1, x)

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

Solution (Python):

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:  
        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  
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  
        self.tree = [self.ide] * (2 * self.num)  
        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  
            v = self.lazy[i]
            if v == self.lide:
                continue
            
            
            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)
        '''
        
        ids = tuple(_gidx(l, r, self.num))
        
        
        
        
        
        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
        
        for i in ids:
            i -= 1  
            
            
            
            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がありえないよ)')
        
        self._lazyprop(*_gidx(l, r, self.num))
        
        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))

Solution (Python):
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 
        self.apply = apply 
        self.comp = comp 
        self.e = e 
        self.identity = identity 
        self.v, self.length = self._build(lst) 
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        
        
        e, N, op = self.e, self.N, self.op
        tree = [e] * N + lst + [e] * (N - self.n)
        length = [1] * (2 * N)
        for i in range(N - 1, 0, -1):
            lc, rc = i << 1, (i << 1)|1
            tree[i] = op(tree[lc], tree[rc])
            length[i] = length[lc] + length[rc]
        return tree, length
    
    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
    
    
    def _propagate_topdown(self, *indices):
        identity, v, lazy, length, apply, comp = self.identity, self.v, self.lazy, self.length, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lc, rc = k << 1, (k << 1) | 1
            lazy[lc] = comp(lazy[lc], x)
            lazy[rc] = comp(lazy[rc], x)
            v[lc] = apply(v[lc], x, length[lc])
            v[rc] = apply(v[rc], x, length[rc])
            lazy[k] = identity 

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

    
    def update(self, l, r, x):
        *indices, = self._indices(l, r)
        self._propagate_topdown(*indices)
        
        N, v, lazy, length, apply, comp = self.N, self.v, self.lazy, self.length, self.apply, self.comp
        
        
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x, length[left]); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x, length[right])
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                lazy[left] = comp(lazy[left], x)
                v[left] = apply(v[left], x, length[left])
                left += 1
            if right & 1:
                right -= 1
                lazy[right] = comp(lazy[right], x)
                v[right] = apply(v[right], x, length[right])
            left >>= 1; right >>= 1
        self._propagate_bottomup(indices)
    
    
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: 
                L = op(L, v[left])
                left += 1
            if right & 1: 
                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, l: x + f*l
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:
        s, t = arg
        ans.append(lpsg.fold(s-1, t))
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline


class BIT():
    """区間加算、区間取得クエリをそれぞれ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(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]
bit = BIT(n)

for i in range(q):
    if query[i][0] == 0:
        _, l, r, x = query[i]
        bit.add(l-1, r, x)
    else:
        _, l, r = query[i]
        print(bit.get_sum(l-1, r))