# Doveqise

### P3372 【模板】线段树 1 题解

posted on 2019-09-15 08:05:06 | under 题解 |

python用户表示python也是可以写数据结构的 (逃)

class Segment_Tree:
def __init__(self, alist):初始化线段树
self.num = alist[:]
self.tag = [0]*4*len(self.num)
self.siz = [0]*4*len(self.num)
self.data = [0]*4*len(self.num)
self.n = len(self.num)
self.build(1, 1, n)

def ls(self, x):左儿子
return x << 1

def rs(self, x):右儿子
return x << 1 | 1

def push_up(self, x):
self.data[x] = self.data[self.ls(x)]+self.data[self.rs(x)]

self.data[x] += k*self.siz[x]
self.tag[x] += k

def push_down(self, x):下放标记

if(self.tag[x] != 0):
if(self.siz[self.siz[self.ls(x)]] != 0):
if(self.siz[self.siz[self.rs(x)]] != 0):
self.tag[x] = 0

def build(self, x, l, r):建树
if(l == r):
self.siz[x] = 1
self.data[x] = self.num[l-1]
return
mid = (l+r) >> 1
self.build(self.ls(x), l, mid)
self.build(self.rs(x), mid+1, r)
self.push_up(x)
self.siz[x] = self.siz[self.ls(x)]+self.siz[self.rs(x)]

def update(self, x, ql, qr, l, r, k):
if(ql <= l) & (r <= qr):
return
self.push_down(x)
mid = (l+r) >> 1
if(ql <= mid):
self.update(self.ls(x), ql, qr, l, mid, k)
if(qr > mid):
self.update(self.rs(x), ql, qr, mid+1, r, k)
self.push_up(x)

def query(self, x, ql, qr, l, r):
res = 0
if(ql <= l) & (r <= qr):
return self.data[x]
self.push_down(x)
mid = (l+r) >> 1
if(ql <= mid):
res += self.query(self.ls(x), ql, qr, l, mid)
if(qr > mid):
res += self.query(self.rs(x), ql, qr, mid+1, r)
return res

n, m = input().split()
n = int(n)
m = int(m)
alist = input().split()
alist = [int(i) for i in alist]
bax = Segment_Tree(alist)
while(m > 0):
a = input().split()
if(int(a[0]) == 1):
bax.update(1, int(a[1]), int(a[2]), 1, n, int(a[3]))
if(int(a[0]) == 2):
print(bax.query(1, int(a[1]), int(a[2]), 1, n))
m = m-1