title: querying sub array sum using segment tree complexity
body: <p>I understand that segment trees can be used to find the sum of sub array of A. And that this can done in O(logn) time according to the tutorial <a href="http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/" rel="nofollow">here</a>.</p>
  
  <p>However I'm not able to prove that the querying time is indeed O(logn). This link (and many others) say that we can prove that at each level, the maximum number of nodes processed is 4 and so O(4logn) == O(logn). But how do we prove this, perhaps by contradiction?</p>
  
  <p>And if so, if we were to use segment trees for ranged sum of higher dimensional arrays, how would the proof be extended?</p>
  
  <p>For example, I can think of finding a sub matrix sum by dividing the original matrix into 4 quadrants (similar to halving intervals in linear arrays) building a quadrant segment tree but the proof eludes me.</p>