Segment tree with lazy propagation
Your task
Implement a segment tree with lazy propagation over an array of length n initialized to all zeros. Process a list of operations: ["add", l, r, v] adds v to every element in the inclusive range [l, r], and ["sum", l, r] returns the sum of that inclusive range. Indices are 0-based and 0 <= l <= r < n. Return the list of answers to the "sum" operations, in order.
Examples
seg_lazy_range_add_sum(n: int, ops: list[list]) -> list[int]Example 1
Input
seg_lazy_range_add_sum(5, [["add", 0, 4, 2], ["sum", 0, 4], ["add", 1, 3, 3], ["sum", 1, 3], ["sum", 0, 4]])Output
[10, 15, 19]