前缀最值

1 问题模型

本篇保留 树状数组基础 的管辖区间,把块内运算由求和改为取最大值,严格支持:

  • chmax(p,v):执行 ap←max⁡(ap,v)a_p\leftarrow\max(a_p,v)。
  • prefix_max(r):查询 max⁡(a1,…,ar)\max(a_1,\ldots,a_r)。

chmax 只会让一个位置变大或保持不变,不能把它改小。这一限制决定了修改能否直接沿树状数组的更新路径进行。

2 块内最大值

令:

c[i]=max⁡i−lowbit⁡(i)+1≤j≤iaj. c[i]=\max_{i-\operatorname{lowbit}(i)+1\le j\le i}a_j.

查询前缀时仍沿 i -= lowbit(i) 取块。例如 [1,7][1,7] 拆成 [1,4][1,4]、[5,6][5,6]、[7,7][7,7],对三个块的最大值再取最大值即可。

负数数组的前缀 1 到 7 拆为三个块,块最大值分别为负 2、负 3、负 8,整个前缀最大值为负 2

修改位置 pp 时,仍只影响沿 i += lowbit(i) 枚举的覆盖块。设某块原最大值为 MM,执行 chmax(p,v) 后,其最大值恰好为:

max⁡(M,v). \max(M,v).

原有元素不会变小,所以旧最大值仍有效;新引入的候选只有 vv。

3 修改与查询

3.1 单点 chmax

void chmax(int p, long long v) {
    for (int i = p; i <= n; i += lowbit(i)) {
        c[i] = max(c[i], v);
    }
}

即使 v<apv<a_p,这段代码也不会让任何块变小,与 chmax 的含义一致。

3.2 前缀最大值

long long prefix_max(int r) {
    long long res = NEG_INF;
    for (int i = r; i > 0; i -= lowbit(i)) {
        res = max(res, c[i]);
    }
    return res;
}

初始化时,先将所有块设为负无穷,再逐个插入原数组。查询所选块互不重叠且覆盖整个前缀,取这些块最大值的最大值,就得到正确答案。

不能默认初始化为零。 若原数组全为负数,零会成为不属于数组的错误候选。代码使用 long long 的最小值作为 NEG_INF,这里只比较大小,不对它做加法。

4 两个限制

4.1 不支持任意赋值

数组为 [5,4][5,4] 时,c[2]=5c[2]=5。若将第一个数赋值为 11,新的块最大值应为 44。

执行 max(c[2],1) 仍会得到 55。块只存旧最大值,没有记录删除它后应由谁接替,所以无法这样处理变小的赋值。

4.2 不能用前缀相减求区间最值

数组 [5,1,4][5,1,4] 与 [5,2,3][5,2,3] 的前缀最大值 prefix_max(1)、prefix_max(3) 都为 55,但区间 [2,3][2,3] 的最大值分别为 44 和 33。

这说明两个前缀最大值不足以恢复一般区间最大值。求和可通过减法消去左侧部分,最大值没有对应的消去操作。

5 代码实现

下面使用一个直接检验本篇接口的任务:

  • 输入 n,mn,m,接着输入初始数组。
  • 1 p v:执行 chmax(p,v)。
  • 2 r:查询前缀最大值,保证 1≤r≤n1\le r\le n。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000 + 5;
const long long NEG_INF = numeric_limits<long long>::lowest();
int n, m;
long long c[maxn];

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

void chmax(int p, long long v) {
    for (int i = p; i <= n; i += lowbit(i)) c[i] = max(c[i], v);
}

long long prefix_max(int r) {
    long long res = NEG_INF;
    for (int i = r; i > 0; i -= lowbit(i)) res = max(res, c[i]);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    fill(c, c + n + 1, NEG_INF);
    for (int i = 1; i <= n; ++i) {
        long long v;
        cin >> v;
        chmax(i, v);
    }
    while (m--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            long long v;
            cin >> v;
            chmax(x, v);
        } else {
            cout << prefix_max(x) << '\n';
        }
    }
    return 0;
}

初始化为 O(nlog⁡n)O(n\log n),单次修改和查询均为 O(log⁡n)O(\log n)。有效存储为 O(n)O(n),数组容量由 maxn 指定。

5.1 示例

输入:
5 5
-5 -2 -7 -4 -9
2 4
1 3 6
2 3
1 5 -20
2 5

输出:
-2
6
6

最后一次修改不会使第 55 项变小,因此数组为 [−5,−2,6,−4,−9][-5,-2,6,-4,-9]。

6 与 DP 结合

在 最长上长子序列 中,以第 ii 项结尾的最长严格递增子序列满足:

fi=1+max⁡j<i, aj<aifj. f_i=1+\max_{j<i,\ a_j<a_i}f_j.

从左向右扫描,按值离散化。若树状数组在排名 rr 处记录已扫描元素的最佳 DP 值,则转移可写为:

long long best = max(0LL, prefix_max(rank - 1)) + 1;
chmax(rank, best);

这里下标是值的排名,树中保存的是 DP 长度。rank-1 保证严格递增,max(0LL, ...) 表示允许没有前驱。每个排名的最优值只会增大,正好符合本篇的修改条件。

7 练习

  1. 按本篇格式实现前缀最值,检查全负数、无效的较小更新和只有一个元素的情形。
  2. 完成 atcoder dp_q: AtCoder DP Q Flowers:按原顺序选择高度严格递增的花,最大化美丽值总和。按高度维护前缀最大 DP 值,将上面的长度增量 11 换成当前花的美丽值。该题的原题面保证美丽值为正,因此允许空前驱的值为 00。

维护前缀最小值时可对称地使用 chmin:初值为正无穷,修改只能让一个位置变小。不要只替换 max,却仍保留任意方向的赋值。

尾部追加并查询一般区间的情况,继续阅读 区间最值。

8 相关题解

暂无相关题解