这个是现学的,你运行看看能不能过
class Node:
def __init__(self, l, r):
self.l = l
self.r = r
self.inc = 0
self.sum = 0
self.mid = (self.l + self.r) // 2
# 初始化结点基本信息
def BuildTree(root: int, l: int, r: int, tree: [Node]):
if root >= len(tree):
return
tree[root].l = l
tree[root].r = r
mid = (l + r) // 2
tree[root].mid = mid
if l == r:
return
BuildTree(2 * root + 1, l, mid, tree)
BuildTree(2 * root + 2, mid + 1, r, tree)
# 初始化插入数值
def Insert(root: int, i: int, v: int, tree: [Node]):
if root >= len(tree):
return
if tree[root].l == i and tree[root].r == i: # 直系父亲
tree[root].sum += i
return
tree[root].sum += v # 爷爷辈
if i <= tree[root].mid:
Insert(root * 2 + 1, i, v, tree)
else:
Insert(root * 2 + 2, i, v, tree)
# 在start到end范围内都加上inc
def Add(root: int, start: int, end: int, inc: int, tree: [Node]):
if root >= len(tree):
return
if tree[root].l == start and tree[root].r == end: # 范围刚好在这个结点l,r,只需要赋一次值,后面计算直接inc*数量
tree[root].inc += inc
return
tree[root].sum += inc * (end - start + 1) # 总的增加
# 对子树增加
if end <= tree[root].mid:
Add(root * 2 + 1, start, end, inc, tree)
elif start > tree[root].mid:
Add(root * 2 + 2, start, end, inc, tree)
else:
Add(root * 2 + 1, start, tree[root].mid, inc, tree)
Add(root * 2 + 2, tree[root].mid + 1, end, inc, tree)
def Query(root: int, start: int, end: int, tree: [Node]):
if tree[root].l == start and tree[root].r == end:
return tree[root].sum + tree[root].inc * (end - start + 1)
tree[root].sum += tree[root].inc * (tree[root].r - tree[root].l + 1)
Add(2 * root + 1, tree[root].l, tree[root].mid, tree[root].inc, tree)
Add(2 * root + 2, tree[root].mid + 1, tree[root].r, tree[root].inc, tree)
tree[root].inc = 0
if end <= tree[root].mid: # 区间在root左侧,只需要计算左侧的总和
return Query(root * 2 + 1, start, end, tree)
elif start > tree[root].mid: # 区间在root右侧,只需要计算右侧的总和
return Query(root * 2 + 2, start, end, tree)
else: # 区间在root左右侧都有部分,需要计算两侧的总和
return Query(root * 2 + 1, start, tree[root].mid, tree) + \
Query(root * 2 + 2, tree[root].mid + 1, end, tree)
def main():
n, m = map(int, input().split())
tree = []
for _ in range(n * 4):
tree.append(Node(0, 0))
BuildTree(0, 1, n, tree)
for _ in range(m):
p, k, L, R = map(int, input().split())
Add(0, p, p, k, tree)
print(Query(0, L, R, tree))
main()