3
$\begingroup$

Can someone provide an analysis of the update and query operations of a segment tree?

I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and right sub-trees. If we could prove that one of these calls terminates fairly quickly, the time complexity would be logarithmically bounded. But how do we prove this?

Improve this question
$\endgroup$
4
  • $\begingroup$ Actually in the case of querying you choose whether to go left or right based on the range covered. Look at the implementation details in the topcoder example you linked to below. $\endgroup$
    – 1110101001
    Nov 29, 2014 at 4:49
  • $\begingroup$ In some case you go both left and right. That's why I'm finding it hard to prove the claim $\endgroup$
    – adijo
    Nov 30, 2014 at 4:47
  • 1
    $\begingroup$ Yes, fair point. After some intense googling I think I found the answer you are looking for and even addresses this conundrum: web.stanford.edu/class/cs166/lectures/00/Extra00.pdf $\endgroup$
    – 1110101001
    Nov 30, 2014 at 6:37
  • $\begingroup$ Thanks, but how exactly does the "flush against the wall" structure ensure a log n complexity? They haven't elaborated on that part. $\endgroup$
    – adijo
    Dec 3, 2014 at 5:28

1 Answer 1

Reset to default
4
$\begingroup$

Those are my lecture slides, so I figured I'd chime in. :-)

The idea is to split apart the recursive calls being made into two different classes: recursive calls where the range being searched is the entire range of a node and recursive calls where the range being searched corresponds to just a part of the range. One of the observations you can make is that if you do a range search on a segment tree, after the initial split made in the recursive call, every recursive call made either spans the entire range given by a node or corresponds to a subrange that's flush up against one of the sides of the range given by a node.

As an optimization in a segment tree, any recursive call that's made for a range that completely spans a node doesn't do any further recursion; it just returns the cached value and stops. Therefore, the only recursive calls that fire off more recursive calls are ones where the range searched is flush against the side of the range spanned by a node. If you look at what happens in that case, you'll see that every recursive call made from that point either is over a full range (in which case it doesn't really count as a recursive call; we can charge that work back to the initial recursive call) or is to a flush against the side range. This means that while the recursion does indeed branch, one of those branches always immediately ends. Therefore, the work done obeys the recurrence

T(n) = T(n / 2) + O(1)

where that O(1) term counts both the work for the recursive call and the (up to) one recursive call made on a full range, which terminates immediately. That solves to O(log n), as required.

Hope this helps!

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.