We can solve this task by building a red-black tree or splay tree using the input data. Each node will keep track of the sum of all the nodes beneath it. We can easily answer query types 3 and 4 by using standard binary tree manipulation techniques, and adjusting some sums along the way. Supporting query types 1 and 2 is a bit trickier. We will use the algorithm called lazy propagation.

Assume that we have to set all elements within a given range to the same value. We begin by finding the set of ~\mathcal O(\log N)~ nodes that exactly cover that range. For each node in that set, we mark that all of the node's children are set to the wanted value. Later on, when we encounter the node that has this mark set and would like to descend into that node's children, we simply transfer this mark to all the children. We can now support queries of type 1.

Solving the queries of type 2 can be achieved in a similar way. We store two integers ~A~ and ~B~ for each node. Those integers suggest that ~k^\text{th}~ child of that node should be increased by ~A \times k + B~. We "propagate" ~A~ and ~B~ in the same way as described above. We must be careful in order to keep the correct sum stored in nodes at all times.

We suggest the following sources for further reading:

• https://en.wikipedia.org/wiki/Red%E2%80%93black_tree,
• https://en.wikipedia.org/wiki/Splay_tree,
• Robert Sedgewick: Algorithms.