favorite We need a little bit of your help to keep things running, click on this banner to learn more

ADA University - March 7 - Segment Tree

Sum of Squares with Segment Tree

Segment trees are extremely useful. In particular "Lazy Propagation" (for example allows one to compute sums over a range in O(lg(n)) and update ranges in O(lg(n)) as well. In this problem you will compute the sum of squares over a range with range updates of two types:

  • increment in a range
  • set all numbers the same in a range.


First line contains number of test cases. First line of each test contains two positive integers n (n105) and q (q105). The next line contains n integers, each no more than 1000 by absolute value. Each of the next q lines starts with a number, which indicates the type of operation:

2 st nd – return the sum of the squares of the numbers with indices in [st, nd] {i.e., from st to nd inclusive} (1stndn).

1 st nd x – add "x" to all numbers with indices in [st, nd] (1stndn, and -1000x1000).

0 st nd x – set all numbers with indices in [st, nd] to "x" (1stndn, and -1000x1000).


For each test case output the “Case <caseno>:” in the first line and from the second line output the sum of squares for each operation of type 2. Intermediate overflow will not occur with proper use of 64-bit signed integer.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
2 1 1
Output example #1
Case 1:
Case 2: