Running time analysis of a segment tree
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!