Hello Codeforces!
It's been a while since I contributed something useful to the CF community. So here I am trying my best to make some high quality lectures on range query data structures!
For trying out some range query problems: head to cses range query section
For solutions: my previously written cf blog
Video Series for range query DS
Range Query Problems and Data Structures
Video link: https://youtu.be/8wJzUFZOqK4
Welcome to the series on Range Query data structures and problems!! In this video we will discuss:
1. What are range query problems?
2. Types of Range query problems.
3. Online queries vs offline queries.
4. point updates and range updates.
5. Common Range Query Data Structures for efficiently solving these problems.
Prefix Arrays
Video link: https://youtu.be/-_Jj4U5V4N0
We will talk about:
1. What are prefix arrays?
2. How to build them.
3. How to use them to answer queries.
4. Why can't we use them for range min or max queries?
5. Building a library for solving range query problems using prefix arrays.
Sparse Table | Range Minimum Query in O(1)
Video link: https://youtu.be/iaRvydtqLV4
Introduction to Sparse Table.
Solve Range Min Queries in O(1) time.
- what is sparse table?
- how to build a sparse table?
- how to use it to solve queries?
- Cpp code.
Square Root Decomposition
Video link: https://youtu.be/ZakhE_eaonY
Gentle introduction to Square Root Decomposition.
implementation of the idea discussed in the video: cpp code
To solve the problem of answering range queries on an Array A[1..N].
Queries are of two types:
1. find function F applied on the range [L,R]. F can be sum, min, max or wide range of other functions.
2. point update. set A[i] = new_value V.
Algorithm:
1. Break Array A into X smaller chunks each with Y elements.
2. Find F applied over each chunk individually.
Why exactly root N chunks each with root N elements?
Upcoming topics
- Mo's algorithm over arrays and trees.
- Segment trees with/without lazy propagation.
- Fenwick tree
- Persistent data structures.
- CF/CC/SPOJ Problem solving using above data structures
Hope people will find this useful.
Will keep updating this blog with more content.
Happy Coding :)
