### kartik8800's blog

By kartik8800, history, 3 years ago,

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

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.
5. Common Range Query Data Structures for efficiently solving these problems.

## Prefix Arrays

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)

Introduction to Sparse Table.
Solve Range Min Queries in O(1) time.

1. what is sparse table?
2. how to build a sparse table?
3. how to use it to solve queries?
4. Cpp code.

## Square Root Decomposition

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

1. Mo's algorithm over arrays and trees.
2. Segment trees with/without lazy propagation.
3. Fenwick tree
4. Persistent data structures.
5. 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 :)

• +110

| Write comment?
 » 3 years ago, # |   +6 Thanks bro! Gonna watch em all.
 » 3 years ago, # |   +7 please upload the remaining ones soon, your explanations are gold.
•  » » 3 years ago, # ^ |   +1 Thanks :) will try to upload soon.