SBS

What is segment tree? Segment Tree is used in cases where there are multiple range queries on array and modifications of elements of the same array. For example, finding the sum of all the elements in an array from indices L to R, or finding the minimum (famously known as Range Minimum Query problem) of all the elements in an array from indices L to R. A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmic time. We define the segment tree for the interval [i, j] in the following recursive manner: the first node will hold the information for the interval [i, j] if i<j the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2+1, j] Notice that the height of a segment tree for an interval with N elements is [logN] + 1. Here is how a segment tree for the interval [0, 9] would look like: Some easy problems to exercise your segment trees knowledge: Range sum query - mutable M...

What is Dynamic Programming? Dynamic programming (usually referred to as  DP  ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.  shortly  'Remember your Past'  :)  Now you should ask, How it's different than Divide & conquer method, right? - The answer is very simple, There is only one key difference, In Divide and conquer method once you solve one particular sub-problem then you do not encounter it again, simply non-overlapping sub-problems.  In D&Q, we divide the problem in to non-overlapping sub-problems and solve them independently, like in MergeSort and QuickSort . - Whereas, if you find there are many overlapping sub-problems, then it's a ...