Segment tree

1.定义

储存区间数据的二叉树，每个节点表示一个区间(经过操作过后的结果)

区间有n个元素，数组表示需要有多少节点？

• 最好情况: 刚好为满二叉树(n = 2^k)，为2n空间
• 最差情况: 刚好满二叉树多出来一个(n = 2^k + 1)，为4n空间

2.目标

高效(O(logn))进行区间更新，查询：2011~2014年的平均，最高，最低温度

普通数组的时间复杂度为O(n)

3.基本操作(还是递归)

初始化，更新，查询

注意：节点容量；递归边界；constructor里面return吗？抛出异常吗？

4.扩展

1. 区间更新(lazy update, 记录lazy数组，访问到时再更新)
2. 二维线段树
3. 动态线段树
4. binary index tree
5. range minimum query

code

https://github.com/nyannko/leetcode-java/blob/master/src/ds/segmenttree/SegmentTree.java