线段树I
题目链接
P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
模板代码
import sys
input = lambda: sys.stdin.readline()
class Node:
def __init__(self):
self.val = 0
self.tag = 0
class Tree:
def __init__(self, N, datas):
self.a = [Node() for _ in range(N)]
self.datas = datas
def build(self, root, l, r):
if l == r:
self.a[root].val = self.datas[l]
return
mid = l + r >> 1
self.build(root << 1, l, mid)
self.build(root << 1 | 1, mid + 1, r)
self.push_up(root)
def push_up(self, root):
self.a[root].val = self.a[root << 1].val + self.a[root << 1 | 1].val
def push_down(self, root, l, r):
if self.a[root].tag == 0:
return
mid = l + r >> 1
left = root << 1
right = root << 1 | 1
self.a[left].val += self.a[root].tag * (mid - l + 1)
self.a[right].val += self.a[root].tag * (r - mid)
self.a[left].tag += self.a[root].tag
self.a[right].tag += self.a[root].tag
self.a[root].tag = 0
def update(self, root, l, r, ql, qr, k):
if ql > r or qr < l:
return
if ql <= l and qr >= r:
self.a[root].tag += k
self.a[root].val += k * (r - l + 1)
return
self.push_down(root, l, r)
mid = l + r >> 1
self.update(root << 1, l, mid, ql, qr, k)
self.update(root << 1 | 1, mid + 1, r, ql, qr, k)
self.push_up(root)
def query(self, root, l, r, ql, qr):
if ql > r or qr < l:
return 0
if ql <= l and qr >= r:
return self.a[root].val
self.push_down(root, l, r)
mid = l + r >> 1
return self.query(root << 1, l, mid, ql, qr) + self.query(root << 1 | 1, mid + 1, r, ql, qr)
n, m = map(int, input().split())
datas = [0] + [*map(int, input().split())]
mytree = Tree(n * 4, datas)
mytree.build(1, 1, n)
for _ in range(m):
op = [*map(int, input().split())]
if op[0] == 1:
mytree.update(1, 1, n, op[1], op[2], op[3])
else:
print(mytree.query(1, 1, n, op[1], op[2]))