树状数组 Python实现

具体原理参考 浅谈树状数组 区间修改&区间查询

这里直接给出 区间修改 + 区间查询 的代码

常数超级无敌巨大。

import sys

# sys.stdin = open('check.in', 'r')
# sys.stdout = open('check.out', 'w')

N = int(1e6 + 15)

tr1 = [0] * N
tr2 = [0] * N

def read():
    return [int(x) for x in input().split()]

def lowbit(x):
    return x & (-x)

def _add(tr, x, v):
    i = x
    while(i <= n):
        tr[i] += v; i += lowbit(i)

def add(x, v):
    _add(tr1, x, v); _add(tr2, x, v * x)

def _qry(tr, x):
    r = 0; i = x
    while(i > 0):
        r += tr[i]; i -= lowbit(i)
    return r

def qry(l, r):
    _1 = _qry(tr1, r) * (r + 1) - _qry(tr1, l - 1) * l
    _2 = _qry(tr2, r) - _qry(tr2, l - 1)
    return _1 - _2 

n, m = read()

a = [0] + read()

for i in range(1, n + 1):
    add(i, a[i] - a[i - 1])

for qwq in range(m):
    t = read()
    if(t[0] == 1):
        l = t[1]; r = t[2]; x = t[3]
        add(l, x); add(r + 1, -x)
    else:
        l = t[1]; r = t[2]
        print(qry(l, r))