前缀最大/最小思想

一句话理解

前缀最大/最小：pre[i]=max(a[1..i])。

为什么要学

“左边最大是多少”可以 O(1) 查。

讲解

一边扫一边维护。也可以后缀最大。常用来枚举分割点。

它不是区间任意 [l,r] 的最值，那要用 ST 表或线段树。

例子

pre[1] = a[1];
for (int i = 2; i <= n; i++) pre[i] = max(pre[i-1], a[i]);

pre[i] 只表示从 1 到 i。

常见错误

• 用前缀最大去回答任意区间最值。
• 初始化成 0 遇负数。