线段树属于二叉树, 其核心特征就是支持区间加法，这样就可以把任意待查询的区间$[L, R]$分解到线段树的节点上去，再把这些节点的信息合并起来从而得到区间$[L,R]$的信息。
下面证明在线段树上查询任意区间的复杂度是$O(\log{N})$的，$N$是区间总长度。
由于访问一个节点（即获得一个节点内与待查询区间$[L, R]$相关的信息）是$O(1)$的，只要证明查询一个区间要访问的节点数是$O(\log{N})$的。
如果某个节点完全包含在$[L,R]$内，则不会再向下查询，我们称这样的节点为完整节点，如果所查询的节点只有一部分在$[L,R]$内，则还要从这个节点向下查询，我们称这样的节点为部分节点。
由于区间的连续性，我们有：
在线段树的每一层内
- 部分节点最多只有$2$个，而且与$[L,R]$交在两端。
- 完整节点最多有$2$个， 因为完整节点的兄弟一定不是完整节点，否则它们的父亲也是完整节点，矛盾！ 换言之，完整节点的兄弟如果被访问到，则其必为部分节点， 否则此完整节点必在待查询区间$[L,R]$的一端。
所以每一层内最多访问4个节点，而线段树有$O(\log{N})$层，所以复杂度是$O(\log{N})$。
UPD:
上面的证明虽然已经十分简洁, 但我觉得还是有点故弄玄虚...
很容易看出只有部分节点才会分裂为下层的两个节点, 而部分节点最多有两个, 更直白一点, 只有两端的节点才会分裂 , (诚如某君所言, 借助形象思维)很容易就得到每层内最多访问4个节点.
这篇小文简直败笔... 逃....