Range Minimum query using Naive algorithm [O(1) update + O(N) query]
In the naive approach for range minimum query, we can execute the update query in constant time which is efficient and the best case but the query operation takes linear time O(N) which is slow depending upon number of elements and queries.
Find the maximum sum bitonic subsequence
Given a sequence of numbers in an array A[0.......N]. Find the sum of the maximum bitonic subsequence in the array. naive algorithm will take exponential time O(N * (2^N)) but we can reduced it to O(N^2) using Dynamic programming. We will explore naive approach and go into the dynamic programming
Optimizing a Segment Tree with Lazy Propagation
Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.
Using Farach Colton and Bender Algorithm to solve LCA【O(V) query】
The basic idea of Farach Colton and Bender Algorithm is to traverse all the nodes using the Depth First Search graph traversal and keep a record of all the visited nodes and there corresponding heights. This allows to answer LCA queries in O(V) time complexity