I wanted to study the segmentation tree for many query type questions… need some help and tutorials on that… with some solved examples
A nice explanation can be found on this blog with solved examples.
Segment tree uses recursion multiple times. This was the part that made me feel uneasy about segment tree. I could understand it ( and also I know using recursion for printing fibonaci sequence, gcd etc), I could not visualize it. As a result I could not solve a single problem related to segment tree. Recently, I was studying quick sort and merge sort (helping in class work of a friend) and after some trying, I was able to visualize recursion. I also solved some dynamic programming problems using recursion (TLE though), which made me feel good. Then I tried segment tree once again and I was able to visualize it, and hence code it as well. I did some trivial segment tree problems so far and am looking forward to a problem on codechef (may be in some external challenge).
What I am trying to say is, find out the part where it is difficult to understand and visualize. Focus on that part only. If it is the recursion like me, try quick sort and merge sort.
p.s. I usually do sorting using STL sort() which is why I never actually understood recursion as well as quick and merge sort. So, even if there are shortcuts available, it is worth giving the original algorithm a try.