Week 11 | Range Updates and Range Maximums

27 April, 2021

What was discussed?

1. Forest Queries : subgrid sum queries.
2. Salary Queries : how to use ordered sets.
3. Pizzeria Queries : dealing with absolute values in ds problems.
       Prerequisite: Dynamic Range Minimum Queries
4. Problem: Maintain a data structure which supports the following updates and querys on an array $A$ (initially all $A[i]$ are $0$)-
   • $\texttt{update}(l, r, x)$: do $A[i] := A[i] + x$ for all $i \in [l, r]$.
   • $\texttt{query}(l, r)$: find $\max_{i=l}^{r} A[i]$.
   Solution using square root decomposition and segment tree with lazy propagation.

Recording

References

• cp-algorithms
• Another recommended playlist for segment trees: LightOJ