线段树

参考网址: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+....+R2^x-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