Class #03 | |

Pedro Ribeiro - DCC/FCUP |

**Range Maximum Query (RMQ):**- I know the
**RMQ**and what is asks for - I know variants, such as asking for the minimum or the sum (
**RSQ**)

- I know the
**Square-root (srt) decomposition**- I know the meaning of
**decomposing**an array of size*n*into buckets of size*sqrt(n)* - I know how to answer an RMQ
using*query**sqrt decomposition* - I know how to do a
in RMQ using*single update**sqrt decomposition* - I understand how to
**adapt**it to variations such as RSQ.

- I know the meaning of
**Segments trees:**- I understand the concept of
**segment trees** - I know how how to
**implement**segment trees using simple arrays - I know how to answer an RMQ
using*query**segment trees* - I know how to do a
in RMQ using*single update**segment trees* - I understand how to
**adapt**the**merge**function of a segment tree to more complex variations (including storing several values in a node, like for instance in a**merge sort tree**) - I know and understand the concept of
**lazy propagation**to make**range updates** - I know and understand the concept of
**offline processing**and how I can (re)sort queries to make a good usage of segment trees - I know and understand the concept of
**2D Segment Trees**for generalizing to a 2D case

- I understand the concept of

**Videos:**- Segment Trees and Lazy Propagation [42m14s] (my own video from the Topics in Advanced Algorithms course)

**General References in websites:**- Range Minimum Query and Lowest Common Ancestor (TopCoder Tutorial)
- Algorithm Gym :: Everything About Segment Trees (CodeForces Blog Post)
- Sqrt Decomposition (E-Maxx Algorithms)
- Segment Trees (E-Maxx Algorithms)

**Example Implementations:**- Example implementation of segment trees: 12086.cpp
*(will eventually explain it with livecoding)*

[solves UVA 12086 - Potentiometers]**[FUNCTIONAL EXAMPLE CODE!]**

- Example implementation of segment trees: 12086.cpp
**Book References:**- Section 9.3 and Chapters 27 and 28 of the Competitive Programmer's Handbook book
- Section 2.3.3 of the Competitive Programming book

Pedro Ribeiro - DCC/FCUP |
**Último update:**