Range Assign Update and Sum Query

Given an array of length n initially filled with zeros, process two types of operations: assign every value in a range to a constant, and query the sum of a range. Return all query answers in order. This is a classic lazy propagation problem because range assignment must be pushed down efficiently.

Input Format

n = array length, operations = range assignments and sum queries

Output Format

sum for every type-2 query, in order

Constraints

  • 1 <= n <= 10^5
  • 1 <= operations.length <= 10^5
  • Each operation is [1, left, right, value] for assignment or [2, left, right] for sum query.

Examples

Example 1:

Input:

n = 5
operations = [[1,1,3,2],[2,0,4],[1,2,4,1],[2,0,4]]

Output:

[6,5]

Explanation:

After assigning 2 to indices 1 through 3, the sum is 6. After reassigning 1 to indices 2 through 4, the total becomes 5.

Example 2:

Input:

n = 4
operations = [[1,0,2,3],[2,1,3],[1,1,1,0],[2,0,3]]

Output:

[6,6]

Explanation:

The first query sees [3,3,3,0] on indices 1..3. After the second assignment, the array becomes [3,0,3,0], whose total sum is 6.

Loading...
Range Assign Update and Sum Query