区间最大利润

GitHub跳转原题关系图返回列表

区间存最低价、最高价与区间内最优交易，合并时取左段最优、右段最优、右段最高减左段最低三者最大；线段树与倍增两种实现，单次询问 O(log n)。

OJ: roj

题目 ID: 1820

难度:普及+/提高-

标签:线段树分治区间查询

创建: 2026-10-29 20:18

更新: 2026-10-29 20:39

RBook 文章:
倍增跳跃

前置题目

leetcodecn best-time-to-buy-and-sell-stock买卖股票的最佳时机A 教的「扫到一个位置时只用此前最低价算利润」就是本题合并式的单侧来源；B 把它从「整个数组扫一遍」升级成「任意询问区间」，因此必须把这条观察压成可合并的区间摘要 (min, max, best)，并在合并时补上跨段项 max_R - min_L。luogu P3372【模板】线段树 1B 的线段树解法要手写递归建树、区间划分与查询骨架，A 提供这套模板；B 只把聚合量从「区间和」换成三元摘要 (min, max, best)。

后置题目

luogu P3976[TJOI2015] 旅游B 直接复用 A 的区间三元摘要 (min, max, best) 与合并式 max(best_L, best_R, max_R - min_L)：把 A 的「一个询问区间」换成树上路径拆出的 O(log n) 段 dfn 区间，并为「同一段可能被反着走」补上 bwd、为路径整体加价补上懒标记。

形式化题目

给定长度为 $n$ 的整数序列 $A_1, \dots, A_n$ ，以及 $q$ 次相互独立的询问。每次询问给定 $1 \leqslant l < r \leqslant n$ ，求

\max_{l \leqslant i < j \leqslant r} \left(A_j - A_i\right)

其中 $n, q \leqslant 10^5$ ， $1 \leqslant A_i \leqslant 10^9$ 。

下标约束 $i < j$ 表示买入必须早于卖出，且买卖都只能发生在询问区间内部。所求的值可以是负数：区间内价格严格递减时，答案是最接近 $0$ 的那个负差。

以样例的第三次询问 $[3, 6]$ 为例，区间是 $1, 3, 4, 3$ ，取 $i = 3$ （价格 1）、 $j = 5$ （价格 4）得 $4 - 1 = 3$ 。

暴力解法

思路

照题面写：每次询问拿到 $[l, r]$ ，把区间内所有 $i < j$ 的数对枚举一遍，取 $A_j - A_i$ 的最大值。

用样例的第二次询问 $[1, 4]$ （价格 $5, 3, 1, 3$ ）把区间内的数对全部列出来：

买入 $i$	卖出 $j$	$A_j - A_i$
1（价 5）	2	$-2$
1（价 5）	3	$-4$
1（价 5）	4	$-2$
2（价 3）	3	$-2$
2（价 3）	4	$0$
3（价 1）	4	$2$

最大值 $2$ 出现在第 3 天买入、第 4 天卖出，与样例输出一致。

这个写法的正确性不需要额外论证：它枚举了区间内的全部合法数对，一个不漏。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-29 20:18
 * update_at: 2026-10-29 20:18
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接照题面写：每次询问把区间内所有 i < j 数对枚举一遍，取 A[j] - A[i] 的最大值。
// 单次询问 O(len^2)，q 次询问共 O(n^2 q)，只适合 n <= 300 的小数据。
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 305; // 暴力只处理 n <= 300 的小规模数据

const ll NEG_INF = -2000000000000000000LL;

ll n, q;
ll a[MAXN]; // a[i]：第 i 天的价格，下标从 1 开始

int main() {
    if (scanf("%lld %lld", &n, &q) != 2) return 0;
    if (n > MAXN - 1) { // 超出暴力适用范围，直接退出，避免越界
        fprintf(stderr, "brute.cpp 仅支持 n <= %d\n", MAXN - 1);
        return 0;
    }
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    for (ll t = 0; t < q; t++) {
        ll l, r;
        scanf("%lld %lld", &l, &r);

        ll best = NEG_INF; // 区间内最好的利润，可能为负
        // 枚举区间内所有先买后卖的组合
        for (ll i = l; i <= r; i++) {
            for (ll j = i + 1; j <= r; j++) {
                ll profit = a[j] - a[i];
                if (profit > best) best = profit;
            }
        }
        printf("%lld\n", best);
    }
    return 0;
}

复杂度

时间：单次询问 $O(\text{len}^2)$ ， $q$ 次询问共 $O(n^2 q)$ 。
空间： $O(n)$ ，只需要存原数组。

$n = q = 10^5$ 时比较次数可达 $10^{15}$ 量级，远超 1000 ms 能完成的量级。

瓶颈

瓶颈是同一批数对被反复枚举，而且重复发生在两个层次上。

第一层在询问之间：不同询问的区间大量重叠，比如 $[1, 10^5]$ 和 $[1, 10^5 - 1]$ 几乎完全重合，可暴力把 $10^{10}$ 个数对算了两遍。

第二层在区间内部：固定卖出时刻 $j$ 后， $A_j$ 是定值，要让 $A_j - A_i$ 最大只需 $A_i$ 尽量小，所以每个 $j$ 其实只关心左边的最小值，其余数对白算。1417 那题正是靠这一点把单次扫描压到 $O(n)$ 。

但只靠前缀最小值解决不了本题：它只能回答「从头到某处」这类询问，而本题的 $l$ 是任意的，左边的元素随时可能被排除在区间外。

所以需要一个能把任意区间拼出来的结构：让一段区间的答案能从若干小段的答案合成。

解法总览

暴力层的瓶颈是「同一批数对被反复枚举」。要消掉它，必须让一段区间的答案能从若干小段的答案拼出来。两种解法用的是同一个合并运算，区别只在「怎么把询问区间拆成若干段、段信息怎么预存」。

解法	核心观察	预处理	单次询问	空间	对应代码
解法一：线段树	三元组合并，询问时把区间拆成 $O(\log n)$ 个树结点依次合并	$O(n)$	$O(\log n)$	$O(n)$ ，实测 8.5–10 MB	`main.cpp`
解法二：倍增	同一三元组，预存所有长度为 $2^k$ 的段的答案，询问时从大到小拼区间	$O(n\log n)$	$O(\log n)$	$O(n\log n)$ ，实测 38.5–40 MB	`main2.cpp`

两者是替代关系，不是逐步优化：线段树预处理更快、空间更省，适合本题 128 MB 的限制；倍增的预处理多一个 $\log$ 因子，但把区间拆解写成了「从大到小能放就放」的统一形式，思路更接近倍增思想的通用模板。

正式主解是解法一（线段树），即 main.cpp。

合并运算：两种解法共用的基础

把一段区间切成前后相邻的两段 $L$ 、 $R$ ，最优交易的买卖位置只有三种落法，且互斥、穷尽：

买入、卖出都在 $L$ 内；
买入、卖出都在 $R$ 内；
在 $L$ 内买入、在 $R$ 内卖出。

前两种是原问题的子问题，第三种跨过了两段的交界。第三种情形里，买入时刻一定落在 $L$ 、卖出时刻一定落在 $R$ ，两边互不干扰，所以可以分别取极值：

\text{cross} = \max_{j \in R} A_j - \min_{i \in L} A_i

式子的左项是 $R$ 能提供的最高卖价，右项是 $L$ 能提供的最低买价，两者相减就是「跨段交易」的最好结果。由于买入侧和卖出侧被交界分开， $i < j$ 自动成立。

至于这两段怎么切——按中点对半分，还是按 $2$ 的幂切——不影响上面的推导，只要 $L$ 在时间上完全早于 $R$ 就行。两种解法正是在「怎么切」上不同。

于是只要每段区间存下三个数，就能把两段合成一段：

存的量	含义	合并方式
`minv`	区间内最低价	$\min(L.\text{minv},\ R.\text{minv})$
`maxv`	区间内最高价	$\max(L.\text{maxv},\ R.\text{maxv})$
`best`	区间内最优交易	$\max(L.\text{best},\ R.\text{best},\ R.\text{maxv} - L.\text{minv})$

best 的第三项就是上面的 $\text{cross}$ 。这个合并只看两段各自的三元组、不看它们怎么切出来的，所以满足结合律： $(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$ 。换句话说，这三个量的合并构成一个半群，这正是「任意区间可以拆成若干段依次合并」的全部依据，线段树和倍增能成立都靠它。

光有半群还不够，本题的合并还有两个必须记住的性质：

不满足交换律： $R.\text{maxv} - L.\text{minv} \neq L.\text{maxv} - R.\text{minv}$ ，所以合并参数不能颠倒，左段必须在前。
不满足幂等律： $X \cdot X \neq X$ 。这一条决定了重叠查询不能做，详见解法二里那一节。

用样例 $5, 3, 1, 3, 4, 3$ 看一次真实合并：把 $[1,6]$ 按中点切成 $[1,3]$ 与 $[4,6]$ 两段。

段	`minv`	`maxv`	`best`
$L = [1,3]$ ，价格 $5,3,1$	1	5	$-2$ （ $3-5$ ）
$R = [4,6]$ ，价格 $3,4,3$	3	4	$1$ （ $4-3$ ）
合并 $[1,6]$	1	5	$3$

合并结果 $3$ 来自第三项 $R.\text{maxv} - L.\text{minv} = 4 - 1 = 3$ ，即「 $L$ 里最低的 1 买入、 $R$ 里最高的 4 卖出」，正是样例给出的最优交易。两段各自的 best 分别是 $-2$ 和 $1$ ，都不如跨段这一项。

解法一：线段树

思路

把上面的三元组放进线段树。每个结点存自己管辖区间的 $(\text{minv}, \text{maxv}, \text{best})$ ，建树时自底向上合并；询问时把 $[l, r]$ 拆成 $O(\log n)$ 个结点，按从左到右的顺序依次合并。

有三处细节决定正确性：

第一，叶子结点的 best 要设成负无穷。 叶子只有一天，构不成先买后卖。若设成 0，单天会被当作「利润为 0 的交易」，那么一路递减的区间就会错答成 0 而不是负数。

第二，合并时左段必须在前。 跨段项是 $R.\text{maxv} - L.\text{minv}$ ，它默认 $R$ 在时间上晚于 $L$ 。把两段顺序写反，这一项会算成「在后面买、在前面卖」，可能得到非法的大利润。

第三，询问的三个分支要保持顺序。 完全被覆盖时直接返回该结点；只与左儿子相交就只查左边；只与右儿子相交就只查右边；跨过中点时先查左边、再查右边，然后合并。这个顺序保证了拼出来的片段与真实时间顺序一致。

正确性

引理：设 $L$ 覆盖 $[l, m]$ 、 $R$ 覆盖 $[m+1, r]$ ，则

\text{best}([l,r]) = \max\left(L.\text{best},\ R.\text{best},\ R.\text{maxv} - L.\text{minv}\right)

记等式右边为 $C$ ，左边的真实最优值为 $B$ ，分两个方向。

$C \leqslant B$ （合并式不会算出超过真实最优的值）

三项各自都对应一个 $[l, r]$ 内的合法交易： $L.\text{best}$ 对应左半段内的某个 $i < j$ ； $R.\text{best}$ 对应右半段内的某个 $i < j$ ；这两对下标都落在 $[l, r]$ 内。
第三项里， $R.\text{maxv}$ 在某时刻 $j^* \geqslant m+1$ 取到， $L.\text{minv}$ 在某时刻 $i^* \leqslant m$ 取到，于是 $i^* < j^*$ 是一对合法下标，且 $R.\text{maxv} - L.\text{minv} = A_{j^*} - A_{i^*}$ 是真实利润。
三项都是真实利润，都不超过 $B$ ，取最大后 $C \leqslant B$ 。

$C \geqslant B$ （真实最优不会被漏掉）

设最优交易为 $(i, j)$ ， $l \leqslant i < j \leqslant r$ 。
若 $j \leqslant m$ ，交易全在 $L$ 内， $B = A_j - A_i \leqslant L.\text{best} \leqslant C$ 。
若 $i \geqslant m+1$ ，交易全在 $R$ 内， $B \leqslant R.\text{best} \leqslant C$ 。
若 $i \leqslant m < j$ ，则 $A_i \geqslant L.\text{minv}$ 且 $A_j \leqslant R.\text{maxv}$ ，所以 $B = A_j - A_i \leqslant R.\text{maxv} - L.\text{minv} \leqslant C$ 。
三种情形穷尽了所有可能，每种都有 $B \leqslant C$ 。

两个方向合起来得 $B = C$ ，合并公式正确。 $\square$

两个方向都需要：只证 $C \leqslant B$ 无法排除合并式算出偏小的值，只证 $C \geqslant B$ 无法排除它算出偏大的值。第一方向里「 $i^* < j^*$ 」那一步是关键，它保证了跨段项 $R.\text{maxv} - L.\text{minv}$ 真的对应一个合法交易，而不是把卖出时刻挑到买入时刻之前。

查询过程：线段树查询把 $[l, r]$ 拆成互不相交、按从左到右排列的结点 $v_1, \dots, v_k$ ，其并集恰好是 $[l, r]$ 。由上面的引理反复合并即得 $\text{best}([l,r])$ ；由结合律，合并的括号位置不影响结果，而代码保证的左右顺序保证每次合并的参数都符合时间先后。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-29 20:18
 * update_at: 2026-10-29 20:18
 */
// main.cpp：ROJ 1820 区间最大利润（线段树）
// 询问 max(A[j] - A[i])，l <= i < j <= r。对每个区间只需要记住三件事：
//   minv：区间内最低价（最适合买入）
//   maxv：区间内最高价（最适合卖出）
//   best：区间内 max(A[j] - A[i])，i < j
// 合并左右两段 L、R 时，最优交易要么全在 L 里、要么全在 R 里、
// 要么在 L 里买在 R 里卖，第三种的利润是 R.maxv - L.minv。
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100005;

const ll NEG_INF = -2000000000000000000LL; // 答案可能为负，初值取得足够小

// 一段区间的交易信息
struct Node {
    ll minv; // 区间内最低价
    ll maxv; // 区间内最高价
    ll best; // 区间内 max(A[j] - A[i])，要求买入时刻早于卖出时刻
};

ll n, q;
ll a[MAXN];        // a[i]：第 i 天的价格，下标从 1 开始
Node tree[MAXN * 4]; // tree[p]：结点 p 覆盖的那段区间的交易信息

// p 的左儿子与右儿子编号（模板约定的 1 下标完全二叉树编号）
ll ls(ll p) { return p << 1; }
ll rs(ll p) { return p << 1 | 1; }

// 把左右相邻的两段合并成一段
Node merge_node(Node left_seg, Node right_seg) {
    Node res;
    res.minv = min(left_seg.minv, right_seg.minv);
    res.maxv = max(left_seg.maxv, right_seg.maxv);
    // 三种来源：全在左段、全在右段、左段买入右段卖出
    res.best = max(max(left_seg.best, right_seg.best), right_seg.maxv - left_seg.minv);
    return res;
}

// 建树：叶子就是一天的价格
void build(ll p, ll l, ll r) {
    if (l == r) {
        tree[p].minv = a[l];
        tree[p].maxv = a[l];
        tree[p].best = NEG_INF; // 只有一天，构不成先买后卖
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    tree[p] = merge_node(tree[ls(p)], tree[rs(p)]);
}

// 查询区间 [ql, qr] 的交易信息
Node query(ll p, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) return tree[p]; // 当前结点被完全覆盖

    ll mid = (l + r) >> 1;
    if (qr <= mid) return query(ls(p), l, mid, ql, qr);       // 只查左儿子
    if (ql > mid) return query(rs(p), mid + 1, r, ql, qr);    // 只查右儿子

    // 跨过中点：左右都要查，再按顺序合并（左段在前，右段在后）
    Node left_seg = query(ls(p), l, mid, ql, qr);
    Node right_seg = query(rs(p), mid + 1, r, ql, qr);
    return merge_node(left_seg, right_seg);
}

void solve() {
    scanf("%lld %lld", &n, &q);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    build(1, 1, n);

    for (ll i = 0; i < q; i++) {
        ll l, r;
        scanf("%lld %lld", &l, &r);
        Node res = query(1, 1, n, l, r);
        printf("%lld\n", res.best);
    }
}

int main() {
    solve();
    return 0;
}

复杂度

时间：建树 $O(n)$ ，单次询问 $O(\log n)$ ，总 $O(n + q\log n)$ 。
空间： $O(n)$ ，tree 开 $4n$ 个结点、每个结点三个 ll， $n = 10^5$ 时约 10 MB，实测峰值 8.5–10 MB。

对比暴力层的 $O(n^2 q)$ ，改善来自把「每次询问重新枚举」换成了「预先存好区间信息、询问时只合并 $O(\log n)$ 段」。合并运算是常数代价的，所以瓶颈从「数对数量」降到了「区间分解出的段数」。

解法二：倍增

思路

倍增的思路是：把所有长度为 $2^k$ 的区间的答案先算好存起来，查询时用这些块拼出 $[l, r]$ 。

预处理的递推很直接。jump_table[k][i] 表示区间 $[i,\ i + 2^k - 1]$ 的交易信息，它正好是左右相邻两个长度为 $2^{k-1}$ 的段：

\texttt{jump\_table}[k][i] = \text{merge}\left(\texttt{jump\_table}[k-1][i],\ \texttt{jump\_table}[k-1][i + 2^{k-1}]\right)

式子的意思是：一个长度 $2^k$ 的段，拆成前后两个长度 $2^{k-1}$ 的段，各自查表后合并即可。第 $0$ 层就是每个单点，逐层向上递推 $O(n\log n)$ 就能填满整张表。

查询时从大到小枚举 $2^k$ ，能放进剩余区间就取走这一段：

text

1
2
3
4从 k = max_log 递减到 0：
    若 [l, l + 2^k - 1] 还没超出 r：
        把 jump_table[k][l] 并入答案
        l += 2^k

这就是倍增文章的模板里那个「从大到小枚举 $2^i$ ，能跳就跳」的写法：每一次都试图跳尽可能大的一步，跳不动就退一档。区间长度写成二进制后，这串操作正好把 $[l, r]$ 拆成 $O(\log n)$ 个长度互不相同、互不重叠的块。

为什么这里不能直接用常见的 ST 表

常见的 ST 表查询取两个长度为 $2^k$ 的块，让它们从两端向中间重叠覆盖整个区间：

k = \lfloor \log_2(r - l + 1) \rfloor,\quad \text{ans} = \text{merge}\big(\texttt{table}[k][l],\ \texttt{table}[k][r - 2^k + 1]\big)

这种写法能成立，前提是合并运算满足可重复贡献性：两个重叠的块合起来，结果必须等于它们并集那段区间的真实信息。取最大值、最小值、最大公约数都满足这一条（重叠部分的元素被算两次也不改变结果），所以那几类问题用重叠 ST 表没有问题。

本题的合并运算不满足这一条。它的第三项是 $R.\text{maxv} - L.\text{minv}$ ，带着方向：左边那块只能当买入侧、右边那块只能当卖出侧。两块一重叠，重叠区域的元素就会同时出现在「买入侧」和「卖出侧」的候选里，于是这一项可能配出一对「卖出时刻在买入时刻之前」的非法交易。

拿样例的询问 $[1, 4]$ （价格 $5, 3, 1, 3$ ）算一遍就清楚了。区间长度是 4， $k = 2$ ，左块起点 $l = 1$ ，右块起点 $r - 2^2 + 1 = 1$ ，两块是同一段 $[1, 4]$ ：

块	`minv`	`maxv`	`best`
左块 $[1,4]$	1	5	$2$
右块 $[1,4]$ （与左块同一段）	1	5	$2$
重叠合并	—	—	$\max(2,\ 2,\ 5 - 1) = 4$

合并结果 $4$ 来自 $R.\text{maxv} - L.\text{minv} = 5 - 1$ ，可这个 $5$ 是第 $1$ 天的价格、 $1$ 是第 $3$ 天的价格，等于「第 3 天买入、第 1 天卖出」，违反 $i < j$ 。正确答案是 $2$ （第 3 天买、第 4 天卖）。

这不是个别数据的问题：把这种写法拿去跑本题的 12 组公开数据，有 9 组答案偏大。

重叠不只发生在两块完全相同时。取询问 $[1, 3]$ （价格 $5, 3, 1$ ），长度 3， $k = 1$ ，左块是 $[1, 2]$ 、右块是 $[2, 3]$ ，两块在第 2 天上重叠：

块	覆盖	`minv`	`maxv`	`best`
左块	$[1,2]$ = $5,3$	3	5	$-2$
右块	$[2,3]$ = $3,1$	1	3	$-2$
重叠合并	—	—	—	$\max(-2,\ -2,\ 3 - 3) = 0$

算出 $0$ ，正确答案是 $-2$ （ $1 - 3$ ，第 2 天买第 3 天卖）。这一次出错的是 $R.\text{maxv} - L.\text{minv} = 3 - 3 = 0$ ：那个 $3$ 是第 2 天的价格，既当了右块的最高价、又当了左块的最低价，等于拿同一天的价格和自己做交易，利润被抬到了 $0$ 。

所以本题的倍增必须用互不重叠的切分，也就是上面「从大到小能放就放」的写法：每一段只被取一次、只合并一次，跨段项永远对应「先取走的段买入、后取走的段卖出」，方向天然正确，不需要可重复贡献性。

与 rbook《ST 表》一文的对照。 那篇文章讲的是标准重叠查询，适用前提是合并运算可重复贡献，处理区间最大值、最小值、最大公约数这类问题时照它的写法没有问题。本题的合并运算带方向，恰好落在它的适用范围之外，所以不能直接套。本文的写法对应的是 rbook《倍增跳跃》那篇的「能跳就跳」模板；两篇文章本来就是前后关系（ST 表以倍增为前置），读完倍增再看 ST 表，正好能看清「什么时候两个块可以重叠、什么时候不能」这条分界线。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-29 20:22
 * update_at: 2026-10-29 20:22
 */
// main2.cpp：ROJ 1820 区间最大利润（倍增）
// 预处理 jump[k][i] = 区间 [i, i + 2^k - 1] 的交易信息，由 k-1 层的相邻两段合并得到。
// 查询 [l, r] 时从大到小枚举 2^k，能放下就取走这一段并让 l 前移，直到区间被取完。
//
// 注意：这里不能写成常见的「重叠 ST 表」查询。那种写法取两块长度为 2^k 的区间让它们
// 重叠，正确性依赖合并运算幂等（op(x, x) = x）。本题的 best 含跨段项 R.maxv - L.minv，
// 两块重叠时会把同一段既当左半又当右半，配出「先卖后买」的非法对，答案会偏大。
// 下面的写法每段只合并一次、互不重叠，所以不依赖幂等性。
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int MAXLOG = 18; // 2^17 = 131072 > 10^5，够用

const ll NEG_INF = -2000000000000000000LL; // 答案可能为负，初值取得足够小

// 一段区间的交易信息，含义与 main.cpp 完全一致
struct Node {
    ll minv; // 区间内最低价
    ll maxv; // 区间内最高价
    ll best; // 区间内 max(A[j] - A[i])，要求买入时刻早于卖出时刻
};

ll n, q;
ll a[MAXN];              // a[i]：第 i 天的价格，下标从 1 开始
Node jump_table[MAXLOG][MAXN]; // jump_table[k][i]：区间 [i, i + 2^k - 1] 的交易信息
int max_log;             // 满足 2^max_log <= n 的最大 max_log

// 把左右相邻的两段合并成一段
Node merge_node(Node left_seg, Node right_seg) {
    Node res;
    res.minv = min(left_seg.minv, right_seg.minv);
    res.maxv = max(left_seg.maxv, right_seg.maxv);
    res.best = max(max(left_seg.best, right_seg.best), right_seg.maxv - left_seg.minv);
    return res;
}

// 预处理：第 0 层是每个单点，之后每层由上一层相邻两段合并
void build_table() {
    for (ll i = 1; i <= n; i++) {
        jump_table[0][i].minv = a[i];
        jump_table[0][i].maxv = a[i];
        jump_table[0][i].best = NEG_INF; // 只有一天，构不成先买后卖
    }

    max_log = 0;
    while ((1 << (max_log + 1)) <= n) max_log++;

    for (int k = 1; k <= max_log; k++) {
        int half = 1 << (k - 1); // 半段长度 2^(k-1)
        for (ll i = 1; i + (1 << k) - 1 <= n; i++) {
            jump_table[k][i] = merge_node(jump_table[k - 1][i],
                                          jump_table[k - 1][i + half]);
        }
    }
}

// 查询 [l, r]：从大到小尝试 2^k，放得下就取走这一段，等价于倍增文章里「能跳就跳」
Node query(ll l, ll r) {
    Node res;
    bool has_piece = false; // 是否已经取到第一段

    for (int k = max_log; k >= 0; k--) {
        if (l + (1 << k) - 1 > r) continue; // 这一段放不进剩余区间，跳过
        if (!has_piece) {
            res = jump_table[k][l];
            has_piece = true;
        } else {
            res = merge_node(res, jump_table[k][l]);
        }
        l += 1 << k; // 这一段已经取走，左端点前移
    }
    return res;
}

void solve() {
    scanf("%lld %lld", &n, &q);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    build_table();

    for (ll i = 0; i < q; i++) {
        ll l, r;
        scanf("%lld %lld", &l, &r);
        Node res = query(l, r);
        printf("%lld\n", res.best);
    }
}

int main() {
    solve();
    return 0;
}

复杂度

时间：预处理 $O(n\log n)$ ，单次询问 $O(\log n)$ （从大到小枚举各层），总 $O(n\log n + q\log n)$ 。
空间： $O(n\log n)$ 。表里共 $n\log n$ 个三元组， $n = 10^5$ 时约 38 MB，实测峰值 38.5–40 MB。

与解法一相比，倍增多花了 $O(n\log n)$ 的预处理和空间，换来的是把「区间拆解」写成了一个统一形式：不需要树的递归结构，只有一张表和一次从高到低的枚举。

复杂度对比

	解法一：线段树	解法二：倍增
预处理	$O(n)$	$O(n\log n)$
单次询问	$O(\log n)$	$O(\log n)$
空间	$O(n)$	$O(n\log n)$
实测峰值内存	8.5–10 MB	38.5–40 MB
实测最大单点	109–170 ms	114–143 ms
适用场景	本题首选，空间充裕、可能带修改时更合适	纯静态查询，且希望代码贴近倍增模板时

两者询问复杂度相同。线段树在预处理和空间上都更优，所以本题选它作主解；倍增的价值在于思路统一、代码短，且它是理解 ST 类结构的入口。

总结

本题的关键不在数据结构，而在找到能支撑合并的区间状态。

区间状态只需要三个数，这个结论来自交易位置的三分：

交易全在左段，用左段的最优值；
交易全在右段，用右段的最优值；
交易跨过中点，此时买入必在左、卖出必在右，只需左段最低价与右段最高价。

三种情形互斥且穷尽，所以合并式不会漏解，也不会引入非法解。这也是判断能不能用线段树或倍增的通用思路：先问「一段区间的答案能否由若干小段的答案拼出来」，能拼，才有资格上树或上表。

确定了合并运算之后，两种解法的分歧只在「怎么预存、怎么拆区间」：线段树按中点递归切分，倍增按 $2$ 的幂预存所有块。二者询问都是 $O(\log n)$ 。

实现上最容易写错的有三处。叶子 best 若不设成负无穷，递减区间会错答成 0；合并参数若左右颠倒，跨段项会算成「先卖后买」；用倍增时若套用常见的重叠 ST 表，同一段会被当成左右两半，同样配出非法交易。这三个错误都不会让程序崩溃，只能靠能暴露负答案和跨段最优的样例测出来。

【题目描述】

给定一个长度为 $n$ 的数列 $A_1, A_2, \dots, A_n$ ，其中 $A_i$ 表示第 $i$ 天的价格。

一笔交易的利润定义为「先买后卖」的差价：在时刻 $i$ 买入、时刻 $j$ 卖出（ $i < j$ ）可获得 $A_j - A_i$ 的利润。

现在有 $q$ 次询问，每次给定 $l, r$ ，请求出只在区间 $[l, r]$ 内交易时能获得的最大利润，即求

\max_{l \leqslant i < j \leqslant r} \left( A_j - A_i \right)

【输入】

第一行两个整数 $n, q$ ，分别表示天数与询问次数。

第二行 $n$ 个整数 $A_1, A_2, \dots, A_n$ 。

接下来 $q$ 行，每行两个整数 $l, r$ ，表示一次询问。

【输出】

对于每次询问输出一行一个整数，表示区间 $[l, r]$ 内的最大利润。

【数据范围】

$2 \leqslant n \leqslant 10^5$

$1 \leqslant q \leqslant 10^5$

$1 \leqslant A_i \leqslant 10^9$

$1 \leqslant l < r \leqslant n$

【输入样例】

text

1
2
3
4
5
66 4
5 3 1 3 4 3
1 6
1 4
3 6
4 5

【输出样例】

text

【样例解释】

询问 $[1,6]$ ：在第 3 天买入（价格 $1$ ）、第 5 天卖出（价格 $4$ ），利润 $4-1=3$ ；
询问 $[1,4]$ ：区间为 $5,3,1,3$ ，在第 3 天买入（ $1$ ）、第 4 天卖出（ $3$ ），利润 $3-1=2$ ；
询问 $[3,6]$ ：区间为 $1,3,4,3$ ，在第 3 天买入（ $1$ ）、第 5 天卖出（ $4$ ），利润 $3$ ；
询问 $[4,5]$ ：区间为 $3,4$ ，利润 $4-3=1$ 。

【提示】

注意利润可能为负数：当区间内价格严格递减时，最优仍必须先买后卖，此时答案是最小的负数（例如区间为 $4,3,2$ 时答案为 $-1$ ）。
每次询问相互独立，区间之外的价格不能参与交易。
直接对每次询问扫描区间是 $O(nq)$ ，无法通过；需要考虑能快速合并区间信息的数据结构。

【来源】

ROJ 原创（配套 1417 最大利润的区间询问加强版）