Range Queries

Instructions

在这一章，我们考虑一种能够维护区间询问（Range Queries）的数据结构。
在一个区间询问中，我们的目标是对数列的某个区间 $[a,b]$ 得到一个固定的信息。

经典的区间查询：

• $\operatorname{sum}_q(a,b)$：区间 $[a,b]$ 的所有值的和;
• $\operatorname{min}_q(a,b)$：区间 $[a,b]$ 中的最小值；
• $\operatorname{max}_q(a,b)$：区间 $[a,b]$ 中的最大值。

几个例子，对于下面数列的区间 $[3,6]$ 进行询问：

在这个例子中，$\operatorname{sum}_q(3,6)=14$，$\operatorname{min}_q(3,6)=1$，$\operatorname{max}_q(3,6)=6$。

考虑暴力做法，以 sum 操作为例：

int sum(int a, int b) {
    int s = 0;
    for (int i = a; i <= b; ++i)
        s += array[i];
    return s;
}

非常简单，max 和 min 操作也是如此，应该不需要太多解释了吧。

若 $n$ 为数组长度，$q$ 为询问次数，则这段代码是最坏时间复杂度是 $O(nq)$ 的。

如果 $n$ 和 $q$ 都很大（均为 $10^5$ 级别），那么这段代码的效率会非常低。

Static array queries

静态区间查询，就是不进行修改的区间查询，对于序列某段的和，可以用前缀和很轻松地解决，这个就不必多说了。

首先，那么对于任意区间 $[l,r]$ 和任意下标 $id$，其中 $1\leq id\leq l\leq r\leq n$，都有 $\operatorname{sum}_q(l,r)=\operatorname{sum}_q(id,r)-\operatorname{sum}_q(id,l-1)$。
因此，大致思路就是令 $q_i=\operatorname{sum}_q(1,i)$，那么 $\operatorname{sum}_q(l,r)=q_r-q_{l-1}$。

int q[N],a[N];
void init(int n) {
    q[0]=0;
    for(int i=1;i<=n;++i) q[i]=q[i-1]+a[i];
}
int query(int l,int r) {
    return q[r]-q[l-1];
}

代码大致就是如此。

对于 max 和 min 操作，可以参照 st 表进行操作。