Part 1. RMQ的种类

这个不用多说，RMQ是一类非常常见的问题。以下是一些常用的数据结构，以及他们所能胜任的问题（这里只讨论基本情况，不关心可持久化之类的其他问题）：

前缀和：静态区间求和
ST表：静态区间最值（也可以是与最值有关的，比如 $\gcd$ ）
树状数组：区间单点修改，区间查询
线段树：通吃

那么，我们有没有想过，为什么这些数据结构就有所区别，能胜任的问题形式也不同呢？

Part 2. 静态 RMQ 的区别

其实，RMQ的区别就是这个数据结构存储信息的区别。区别在那里呢？我们先要明白一个问题，那就是 RMQ 相关的数据结构肯定是通过某种预处理，使得在最终处理实际问题的时候，能够压缩复杂度。

两种典型的RMQ问题就是最值问题和加和问题，两种问题在暴力的复杂度下，都是 $O(n)$ 的单次查询。

接下来，我们从静态入手，来看看这两种问题的简便求解策略：

对于加和问题，我们可以利用前缀和，利用“一大块减去一小块就是剩下的”的思路，把从前往后的和求出来，这样在最终进行计算的时候，我们就只关心最前面和最后面的值。
对于最值问题，我们会发现，虽然这个问题不能够利用“一大块减去一小块”的思想（因为最值只是一个值，你也不知道他究竟在哪一个区间里），但是我们会发现，在这个问题中，就算是两块重复的区间，最值也并不会因此就发生变化，那么我们就有了ST表，轻松维护整个区间。

这就是静态RMQ的基本思路。那么，重头戏就来了。

Part 3. 从静态到动态

究竟是什么，让线段树和树状数组可以维护动态的区间？很多人有一个错误的认识，那就是因为这两种数据结构存储了更多的信息。

恰恰相反，这两种数据结构，是存储了更少的信息。

我们来对比以下前缀和和树状数组：

当动态修改某一个数据或者区间的时候，我们需要修改的是上图这一列上的所有的蓝色部分。很明显，树状数组维护的数据更少。这样的好处就是，当我们在修改原数据的时候，可以看到，前缀和需要把所有的数据都重写一个遍，明显浪费时间，而树状数组，就算是最坏的情况，10个数据中也只维护了4个，大大节约成本。

那么，你肯定会想，ST表也只维护了 $\log$ 级别的数据啊，为什么他就不能动态查询呢？其实道理也很简单，那就是虽然我们只维护了 $\log$ 级别的行数，但是每一行内，如果我们要修改数据，可就不只是修改一个那么简单了。

这个图片就比较直观了（当然我没画完，不然放不开）。因为ST表的每一层都是有多个重合部分的，这保证了查询时优秀的复杂度，也保证了动态维护时巨大的开销。我们对比一下线段树：

可以看到，线段树没有重合部分，相比之下，他不能实现像ST表一样的 $O(1)$ 优秀复杂度，但是他保证了无论是查找还是修改，都是 $\log$ 级别的复杂度。

Part 4. 树状数组到底局限在何处

显然，线段树和树状数组都可以维护区间的和。那么究竟是什么使得树状数组没有线段树那么通用呢？

要想搞明白这是为什么，我们需要找到树状数组的根本。很多同学在初学树状数组的时候，根本就不知道这玩意和树有什么关系。事实是，这个问题的答案就是树状数组与树的关系。

其实，树状数组和线段树有很大的相似之处。他们都是由二叉树实现的。线段树很明显，但是树状数组就稍微抽象一些了。

我们用这幅图来理解一下树状数组和树的关系：

这样我们看看（其中，形如 xab 节点是我为了占位而加上的），其实树状数组中的 f[i] 就是图中以数字为节点的子树的和。这样我们就很轻松的发现树状数组和线段树的区别：线段树把树状数组中用来占位的 xab 节点也赋予了节点编号，他们也能被查询。

这样这个问题就解决了。树状数组只能查询区间和，那是因为树状数组只有从1到终点，才能实现 $\log$ 级别的查询和修改。比如，如果从3节点出发，你就不能调用那个 x42 节点，因为你并没有一个专门的空间存储他。这样当你从一个不是起点的地方出发的时候，时间复杂度就退化了，只有后半部分可以用树状数组的方式运算，前半部分还是得用暴力实现。这样，由于最值问题不满足区间加法，树状数组就没法实现类似于“后面的减去前面的”的解决方案了。但是，如果给树状数组一个懒标记，事实是他也可以实现区间修改，不过这样就和线段树没什么区别了，还不如线段树方便。当然，树状数组这样也是有道理的，比如，这样他就只需要 $n$ 的空间复杂度，同时时间复杂度常数也比较低。所以，遇到问题，灵活处理。