Skip to main content

Advance Topics

RMQ#

The Range Minimum Query is advance level because of the stricter constraints such queries require the use of advanced data structures and algorithms. Range queries are of two types, with and without update of values. The range queries with update of values are further of two types, first is point update, the second is range update. Compared to point update range queries, range update range queries can be more challenging because this type of queries require adding another level of optimisation on top of the range queries with point update. You will learn about range queries with range update while studying segment trees with lazy propagation. Read the article to know about the data structures that can help you in solving different types of range query problems.

Dynamic Programming with Bit Masking#

Before studying this topic it is recommended that you study the basic dynamic programming approaches, and related terms namely, dp state, state transition, choices. Dynamic programming with bit masking approach requires one special condition to prevail, which is, the decision that you can make for transition from the current state to the next state depends on the decisions made at all the previous states, then you can use a mask to easily represent all the previously made choices and the currently available choices. This approach helps to optimise the time complexity of a brute force solution from O(n!) to exponential time, so to say for applying dynamic programming with bit masking requires a very small n ( 10<= n<= 20), which can be another vital signal that you will need to use dynamic programming with bit masking. To learn more this topic, read from this well written articles.

Dynamic Programming with Digits#

Suppose you are given a large range from 1 to N, N of the order of 1e18, and you are asked to find all numbers in a range from L to R that satisfy some definite criterias, in such a case if you iterate and check each number you are headed straight for a solution that will give a TLE, instead a better and more optimised approach is using digit DP. Digit DP is a specific approach of DP which is applied in the special scenario described earlier. To learn more about digit DP and how to apply it, read on from this well written article, also read and understand the sample code to get a feel of this powerful optimised approach.

In-Out Dynamic Programming on Trees#

If you thought DP ended with bit-masking or digits, you are wrong, now you will learn to apply DP on trees, which is a more advanced level technique and presents many more challenges, that being said it is a very interesting approach and one that you should learn if you are aiming for top spots in competitive programming competitions. If you are aiming to become a top level coder, what are you waiting for, start learning right now from these wonderful explanations of the topic.

Sparse Table#

Sparse Table is a popular data structure that helps to answer range queries in O(logn) time, as you must know by now range queries are of two types, with and without updates, sparse table helps to answer range queries without update efficiently. For range queries with update the table has to be recomputed each time which is an additional workload that degrades the time complexity. But how does it help to answer range queries? Is there any pre-computation required? Why is re-computation required? All these questions you should be able to answer, post reading these wonderful articles.

Fenwick Tree#

Fenwick tree is a data structure that offers services similar to segment tree, but compared to segment tree it is a lot easier to code and can save your coding time. You can use fenwick tree to solve many range query problems with ease. So what is the structure of Fenwick Tree? How to implement the basic operations of insert, update and fetch? If you don’t wanna lose your time coding up a segment tree it is recommended you read on, start right now.

Segment Tree with Lazy Propagation#

Earlier while studying segment tree, you must have seen how segment tree can be useful to answer range queries in O(logn) time, and can also handle point updates easily. However if you do range updates with the help of segment tree, the worst case time complexity of update operation would become O(nlogn) from O(logn). Segment Tree with Lazily Propagation is a concept of doing things lazily, this helps you reduce the time complexity of update operation to O(logn). Hmm, so you wanna learn more about it, then don’t worry, all you need to do is read these great articles and you won’t ever have to worry about range updates again. So what are you waiting for, start reading.

Square Root Decomposition#

Suffix Array#

Suffix Tree#

Edge Connectivity and Vertex Connectivity#