参考网址:https://www.jianshu.com/p/91f2c503e62f
实际上上面的那个教程已经说得很清楚了，这里我就只给我自己的见解和总结
使用线段树的原因
原来的需求是在某个区间范围内求和，或者给出这个区间范围内的最大值
如果按照朴素的查询，查询的时间复杂度是O(n),而如果给出m次查询，那么时间复杂度便是O(mn)
如果使用线段树，那么建树的复杂度是O(n),但查询的时间复杂度是O(lgn)（以2为底）
分析时间复杂度
构建线段树的时间复杂度
O(n)
分析:
可以推导出构建一棵树的递归方程是T(n)=2T(n/2)+R
其中R是一个时间常数
可以试着在图上画出这个线段树，可以计算出树的高度是 log2(n)
那么按照常规来,第一个节点的时间是T(n)+R
然后我们再将T(n)分摊给他的两个子节点,可以推出
T(n)=2T(n/2)+R
如此迭代下去，可以推出T(n)
T(n)=R+2R+4R+....+R2x-1
然后这个数列的长度是log2(n)
根据等比数列求和
可以算出T(n)=(n/2-1)R
那么时间复杂度就是O(n)
查询的时间复杂度
- 比如我们要查询某个区间的最大值
- 我们在建树的时候是已知特定区间的最大值了的(查看链接教程)
- 那么我们考虑最坏的情况
- 最坏的情况能够遍历到的的节点数就是
2*log2(n)（省略一些常数）
只要自己稍加试试就会发现，在一棵树里面，每个分支的最后一个节点代表的就是一个区间里面的整数，比如说1,那么最后一个节点代表的就是[1,1]这个区间 - 对于线段树我们查询时，每一层最多会遍历两个节点，我的意思是，只有这两个节点能够继续往下走，可以简单地画一下图就可以证明
- 首先假设数组区间是
[1,17],我们要求的区间是[2,15]- 那么第二层我们就要考虑
[1,9]和[10,17]- 假设先考虑
[1,9],那么往下走就分为了[1,5]和[6,9]
这两个区间都和[2,15]有交集,但是[6,9]是已知了的(整个都在[2,15]里面)，所以我们只要继续考虑左边的[1,9]就好了- 就这样我们就能看出一层我们最多只会考虑到两个节点
- 那么我们最多能遍历的节点数目就是
2*log2(n) - 那么时间复杂度就是
O(log2(n))
也许会问，我们也遍历了那个已知的节点不是吗？难道不需要时间吗？
是需要，但是你推导一下就会发现，其实遍历的节点数也只是再加一个2*log2(n)而已，时间复杂度不变
参考: https://stackoverflow.com/questions/27185066/segment-tree-time-complexity-analysis
