线段树

B站视频

B站一个视频，讲的基础的单点修改，区间查询，但讲的很清楚，是学习线段树很好的开端，能够快速入门。
有了基础之后，再看博客学习更深刻的线段树的内容会好很多。
学习博客：https://blog.csdn.net/weixin_45697774/article/details/104274713
更深刻 https://blog.csdn.net/zearot/article/details/48299459

线段树时间复杂度分析：

线段树高度：

可以看出每次都将区间的长度一分为二,数列长度为n,所以线段树的高度是log(n),这是很多高效操作的基础。

建树复杂度：

因为每次将区间的长度一分为二,所有创造的节点个数，即底层有n个节点，那么倒数第二次约n/2个节点，倒数第三次约n/4个节点，依次类推：

n + 1/2 * n + 1/4 * n + 1/8 * n + ...
=   (1 + 1/2 + 1/4 + 1/8 + ...) * n
=   2n

所以构造线段树的时间复杂度和空间复杂度都为O(n)，线段树需要的数组元素个数是2*n,构造线段树要开辟至少2倍的储存空间。

单点修改复杂度

更新需要从叶子节点一路走到根节点, 去更新线段树上的值。因为线段树的高度为log(n),所以更新序列中一个节点的复杂度为log(n)。

线段树的区间查询复杂度

假设要查询的区间长度为n
任意长度的线段，最多被拆分成logn条线段树上存在的线段，所以查询的时间复杂度为O(log(n))。

线段树的区间修改复杂度

类似于区间查询，所以也为O(log(n))。

线段树的使用场景

对于数据量较大数组维护
1.单点修改，区间查询
2.区间修改，单点查询
3.区间修改，区间查询

什么情况下，无法使用线段树？

如果我们删除或者增加区间中的元素，那么区间的大小将发生变化，此时是无法使用线段树解决这种问题的。

本文地址：https://blog.csdn.net/zhaochuanfei666/article/details/107641838