线段树

引入

假设有这样的问题：有 \(n\) 个数，\(m\) 次操作，操作分为：修改某一个数或者查询一段区间的值。

分析下，如果针对数组元素的修改可以是 \(O(1)\) 完成，求某个区间值需要 \(O(n)\) 才可以完成，如果 \(n\) 和 \(m\) 都很大的情况，这个复杂度就很难接受了。

我们之前学过的前缀和算法可以解决区间求和的问题，并且时间复杂度是 \(O(1)\)，但如果涉及到修改操作，前缀和数组都需要重新计算，时间复杂度也是 \(O(n)\)。

有没有什么办法可以兼顾以上两种操作，并且可以将时间复杂度降低？

这就是我们要学习的线段树！把修改和查询的时间复杂度都降到 \(O(logn)\)！

定义

线段树是一种二叉搜索树 ， 对于线段树中的每一个非叶子结点 \([a,b]\)，它的左儿子表示的区间为 \([a,\frac{a+b}{2}]\)，右儿子表示的区间为 \([\frac{a+b}{2}+1,b]\)。因此线段树是平衡二叉树，设最后的子节点数目为 \(N\)，即整个线段区间的长度，其空间复杂度为 \(O(n)\)。

若对于一个数组使用前缀和数组保存它的区间和，那么查找区间和时间复杂度为 \(O(1)\)，而区间修改时间复杂度为 \(O(n)\)。使用线段树可以快速查找或修改某个区间的值，时间复杂度为 \(O(logN)\)。

区间和与单点修改问题

算法思想

假如有一个数组 \(a\)，长度为 \(7\)，将 \(a\) 赋值为：

\(a = \{1,10,100,1000,10000,100000,1000000\}\)。

为什么每个数要这么大呢？因为这样就能看出线段树的具体实现方法，后文会讲。

把 \(a\) 数组转化为线段树，就是下图。

可以发现，原来数组的值在二叉树都是最底下，节点的父亲都为左儿子与右儿子的和，我们从上到下把权值存入数组 \(z\) 中，\(z = \{1111111,1111,1110000,11,1100,110000,1000000,1,10,100,1000,10000,100000\}\)

那么每个节点表示从下标 \(l\) 到 \(r\) 的和我们也可以表示出来了。

查询操作

如何查询从 \(l\) 到 \(r\) 的和？