Segment trees
Here I like to discuss cool data structures and algorithms that can computer programmers become much better in what they do :) and its fun to learn and discuss , so lets learn something called 'Segment trees' Before we talk about what it does , lets discuss whats the need for such a data structure. Suppose we have an array of N numbers a[1],a[2],....a[N] Now I have two operations that I can perform on this array Retrieve the sum of any sub-array between index i..j Modify the value of any element a[i] So whats the complexity of each of these operations Retrieve the sum of any sub-array between index i..j - Big-Oh(N) since the size of sub-array can vary from 1 to N Modify the value of any element a[i] - Big-Oh(1) , ie. constant time Now lets suppose N is very large then computing the size of each subarray is very costly so we need to think and find a mechanism that helps to reduce the complexity of finding the sum of any sub-array of the given array. How?? ...