You are not logged in. Please login at to post your questions!


Require help on segmentation tree.... how to create and implement them..

I wanted to study the segmentation tree for many query type questions.... need some help and tutorials on that... with some solved examples

asked 20 Mar '15, 08:40

jain_mj's gravatar image

accept rate: 25%

A nice explanation can be found on this blog with solved examples.


answered 20 Mar '15, 14:08

shivam217's gravatar image

accept rate: 20%

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.


answered 21 Mar '15, 23:56

dragonemperor's gravatar image

accept rate: 10%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 20 Mar '15, 08:40

question was seen: 528 times

last updated: 23 Mar '15, 15:17