http://www.lintcode.com/en/problem/segment-tree-query-ii/

注意点：先考虑 给定区间和root区间的位置关系，然后将一些显而易见的结果返回；

　　　　如果给定区间>root区间，将给定区间缩小至root区间大小。

　　　　如果给定区间<=root区间， 那分别查询给定区间在root左右子树区间的结果。

　　　　最后所有的结果统计总是通过叶节点的区间结果累计起来的。[0,0]],[1,1]...

 

1  public int query(SegmentTreeNode root, int start, int end) { 2      if(root == null) return 0; 3      int left = root.start, right = root.end; 4      if(start > end || start > right || end < left) return 0; 5       6      if((start == left && end == right)) return root.count; 7      if(left > start) start = left; 8      if(right < end) end = right; 9      if(left < right) {10          int count1 = query(root.left, start, end);11          int count2 = query(root.right, start, end);12          return count1 + count2;13      }14      return root.count;  //left == right15      16  }17  //九章18  public int query(SegmentTreeNode root, int start, int end) {19         // write your code here20         if(start > end || root==null)21             return 0;22         if(start <= root.start && root.end <= end) { // 相等 23             return root.count;24         }25         26         int mid = (root.start + root.end)/2;27         int leftsum = 0, rightsum = 0;28         if(start > root.end || end < root.start) return 0;29         // 左子区30         if(start <= mid) {31             if( mid < end) { // 分裂 32                 leftsum =  query(root.left, start, mid);33             } else { // 包含 34                 leftsum = query(root.left, start, end);35             }36         }37         // 右子区38         if(mid < end) { // 分裂 339             if(start <= mid) {40                 rightsum = query(root.right, mid+1, end);41             } else { //  包含 42                 rightsum = query(root.right, start, end);43             } 44         }  45         // else 就是不相交，mid不在start-end的区间范围内，说明，start-end仅在左子区或者右子区46         return leftsum + rightsum;47  }