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
