You are not logged in. Please login at www.codechef.com 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

3★jain_mj
372119
accept rate: 25%


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

link

answered 20 Mar '15, 14:08

shivam217's gravatar image

4★shivam217
8383515
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.

link

answered 21 Mar '15, 23:56

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,768

question asked: 20 Mar '15, 08:40

question was seen: 528 times

last updated: 23 Mar '15, 15:17