【树状数组，区间最值】P2880 [USACO07JAN] Balanced Lineup G

题意概括

给定 $n$ 头牛的身高 $h_1,h_2,\dots,h_n$，有 $q$ 次询问。

每次询问给出区间 $[l,r]$，要求输出这个区间内最高牛和最低牛的身高差，也就是：

$$\max(h_l,h_{l+1},\dots,h_r)-\min(h_l,h_{l+1},\dots,h_r) $$

样例分析

样例中身高序列为：

1 7 3 4 2 5

第一次询问 $[1,5]$，区间内的身高为：

1 7 3 4 2

最高为 $7$，最低为 $1$，答案为 $7-1=6$。

第二次询问 $[4,6]$，区间内的身高为：

4 2 5

最高为 $5$，最低为 $2$，答案为 $5-2=3$。

第三次询问 $[2,2]$，区间内只有一头牛，最高和最低都是 $7$，答案为 $0$。

题目分析

这道题需要多次查询静态区间的最大值和最小值。

如果每次询问都从 $l$ 扫到 $r$，一次询问最坏是 $O(n)$，而 $q$ 最大为 $1.8\times 10^5$，会超时。

这题可以用树状数组处理。

普通树状数组常用来维护前缀和，而这里我们不维护和，而是维护区间最大值和区间最小值。

设 $lowbit(i)$ 表示 $i$ 在树状数组中管辖区间的长度，那么节点 $i$ 管辖的区间是：

$$[i-lowbit(i)+1,i]$$

例如：

i = 4, lowbit(4) = 4
节点 4 管辖 [1,4]

i = 6, lowbit(6) = 2
节点 6 管辖 [5,6]

i = 7, lowbit(7) = 1
节点 7 管辖 [7,7]

i = 8, lowbit(8) = 8
节点 8 管辖 [1,8]

因此我们可以让：

• $mx_i$ 表示节点 $i$ 管辖区间内的最大值；
• $mn_i$ 表示节点 $i$ 管辖区间内的最小值。

建树时，把每个位置 $i$ 的身高加入所有包含它的树状数组节点中。

查询 $[l,r]$ 时，从右端点 $r$ 开始向左拆区间。

如果当前节点 $r$ 管辖的整段区间：

$$[r-lowbit(r)+1,r]$$

完全在 $[l,r]$ 内，就可以直接使用 $mx_r$ 和 $mn_r$，然后跳过这一整段。

如果这段区间越过了左边界 $l$，就不能整段使用，只能单独处理当前位置 $r$，然后令 $r$ 减 $1$。

这样就能把一个询问区间拆成若干个树状数组已经维护好的区间，再合并最大值和最小值。

以询问 $[1,5]$ 为例：

[1,5] 可以拆成 [5,5] 和 [1,4]

其中：

节点 5 管辖 [5,5]
节点 4 管辖 [1,4]

所以只需要用这两个节点的信息，就能得到整个区间的最大值和最小值。

这道题没有修改操作，所有身高一开始就确定，所以用树状数组维护静态区间最值是可以的。

参考实现

#include<bits/stdc++.h>
using namespace std;

const int N = 50005;
const int INF = 1e9;

int n, q;
int a[N], mx[N], mn[N];

int lb(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i <= n; i += lb(i)) {
        mx[i] = max(mx[i], v);
        mn[i] = min(mn[i], v);
    }
}

int gmx(int l, int r) {
    int res = 0;
    while (r >= l) {
        if (r - lb(r) + 1 >= l) {
            res = max(res, mx[r]);
            r -= lb(r);
        } else {
            res = max(res, a[r]);
            r--;
        }
    }
    return res;
}

int gmn(int l, int r) {
    int res = INF;
    while (r >= l) {
        if (r - lb(r) + 1 >= l) {
            res = min(res, mn[r]);
            r -= lb(r);
        } else {
            res = min(res, a[r]);
            r--;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    for (int i = 1; i <= n; i++) mn[i] = INF;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << gmx(l, r) - gmn(l, r) << '\n';
    }

    return 0;
}

复杂度分析

建树时，每个位置会更新 $O(\log n)$ 个树状数组节点，所以预处理复杂度为 $O(n\log n)$。

每次询问时，从右端点向左拆成若干个树状数组区间，复杂度为 $O(\log n)$。

因此总时间复杂度为：

$$O((n+q)\log n)$$

空间复杂度为：

$$O(n)$$