Main learning outcomes for this class
- 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)
- 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 query using sqrt decomposition
- I know how to do a single update in RMQ using sqrt decomposition
- I understand how to adapt it to variations such as RSQ.
- 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 query using segment trees
- I know how to do a single update in RMQ using 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
Study Material
- General References in websites:
- Example Implementations:
- Book References:
Pedro Ribeiro - DCC/FCUP |
Último update: