Editorial for Another Contest 3 Problem 4 - Range Updates and Range Queries


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

This problem can be solved in a few ways, generally revolving around data structures that support range update with lazy propagation and range query. We'll outline one such solution that uses two segment trees.

We'll take one segment tree that maintains an array A of elements and supports range increment and the range sum query f(l, r) = \displaystyle\sum_{i=l}^r A[i]. Another one will support range increment and the range sum query f(l, r) = \displaystyle\sum_{i=l}^r i \cdot A[i]. The original range sum query will be answered by summing the range sum query over both segment trees. To perform a range increment, perform a range increment on the first segment tree over [l, r] with value (1-l) \cdot a, and perform a range increment on the second segment tree over [l, r] with value a.


Comments

There are no comments at the moment.