class SegmentTreeDynamic: class Node: left, right = None, None val, add = 0, 0 # def __init__(self, left, right, val, add): # self.left = left # self.right = right # self.val = val # self.add = add def __init__(self): pass N = int(1e9) root = Node() def update(self, node, start, end, l, r, val): if l <= start and end <= r: node.val += ((end - start) + 1) * val node.add = val return mid = (start + end) >> 1 self.pushDown(node, mid - start + 1, end - mid) if l <= mid: self.update(node.left, start, mid, l, r, val) if r > mid: self.update(node.right, mid + 1, end, l, r, val) self.pushup(node) def pushup(self, node): node.val = node.left.val + node.right.val def pushDown(self, node, leftNum, rightNum): if node.left is None: node.left = self.Node() if node.right is None: node.right = self.Node() if node.add == 0: return node.left.val = node.add * leftNum node.right.val = node.add * rightNum node.add = 0 def query(self, node, start, end, l, r): if l <= start and end <= r: return node.val mid, ans = (start + end) >> 1, 0 self.pushDown(node, mid - start + 1, end - mid) if l <= mid: ans += self.query(node.left, start, mid, l, r) if r > mid: ans += self.query(node, mid + 1, end, l, r) return ans
Python实现线段树
2022-11-26
141
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
代码如下
目录
相关文章
|
Python
|
7月前
|
算法
索引
Python
|
Python
|
算法
大数据
Python
|
机器学习/深度学习
算法
Python
|
存储
数据安全/隐私保护
计算机视觉
|
前端开发
Python
|
iOS开发
Python
|
Python
|
机器学习/深度学习
算法
数据可视化
