区间最大和 - 题目列表

形式化题目

给定长度为 $N$ 的正整数数列 $A_1, A_2, \dots, A_N$ ，以及 $Q$ 个询问，每个询问给出整数 $T$ （保证 $0 \leqslant T \leqslant \sum_{i=1}^{N} A_i$ ）。

对每个询问，求最大的 $k$ （允许 $k = 0$ ，此时规定 $\sum_{i=1}^{0} A_i = 0$ ），满足

\sum_{i=1}^{k} A_i \leqslant T

并且要求算法在线：必须即时回答每一个询问，不能等收齐全部询问后再统一处理。

样例： $A = (1, 2, 3, 4, 5)$ ，四个询问 $T = 0, 6, 8, 15$ 的答案依次是 $0, 3, 3, 5$ 。

记前缀和 $S_i = \sum_{j=1}^{i} A_j$ （ $S_0 = 0$ ），题目就是：对每个 $T$ 求最后一个满足 $S_k \leqslant T$ 的下标 $k$ 。

解法总览

所有解法都建立在同一个观察上： $A_i$ 全是正整数，所以 $S$ 严格递增，可行性 $f(i) = [S_i \leqslant T]$ 一定是“前面一段全真、后面全假”。也就是说，可行的位置构成一个前缀，边界唯一。

	解法一：在线倍增跳跃（正式主解）	解法二：离线排序 + 双指针
单次询问	$O(\log N)$ ，独立回答	均摊 $O(1)$ ，但要先排序
总体	$O(N + Q\log N)$	$O(N + Q\log Q)$
是否满足题面「在线」	满足	不满足
核心机制	从大到小试跳 $2^i$ ，能跳就跳	$T$ 越大答案越大，指针只向右走
代码	`main.cpp` / `main.py`	`main-offline.cpp` / `main-offline.py`

两者是替代关系而不是层层优化：解法二不是“把解法一改快一点”，它换掉的是整个前提——允许先看到全部询问。正式主解取解法一，因为题面把“在线”写成了硬要求。

同目录的 brute.cpp 是朴素版：每个询问从 $k = 0$ 一格一格往右走， $O(NQ)$ ，只用来对拍和暴露瓶颈，不参与正式解法。

解法一：在线倍增跳跃（binary jump）

思路

朴素做法的瓶颈：每次询问都从位置 $0$ 重新一格一格试，单次 $O(N)$ 。 $N = Q = 10^5$ 时是 $10^{10}$ 步，必然超时。瓶颈在于——答案的位置本来就是我们要求的，我们没有任何“入口”可以一步跳到它附近，只能逐格逼近。

能利用的只有一条信息： $f(i) = [S_i \leqslant T]$ 关于 $i$ 单调。而「已知一个单调分界点、要在 $O(\log N)$ 内定位它」恰好是倍增跳跃的标准场景：

站在位置 $x = 0$ （ $S_0 = 0 \leqslant T$ ，一定可行）；
从最大的 $i$ 开始，尝试一次跳 $2^i$ 个位置。若跳过去之后仍有 $S_{x + 2^i} \leqslant T$ ，就跳；否则这一档步长永久放弃；
$i$ 依次减小到 $0$ ，最后停留的位置就是答案。

第一步的起点之所以能固定为 $0$ ，正是“ $k$ 可以为 $0$ ”这个约定给的；而跳跃之所以能“能跳就跳”，靠的是下面的性质。

为什么从大到小试跳，终点一定是最后一个可行位置：记最后一个可行位置为 $R$ （即 $S_R \leqslant T < S_{R+1}$ ）。第 $i$ 轮开始前始终有

x \leqslant R, \qquad R - x < 2^{i+1}

初始 $x = 0$ ， $R \leqslant N < 2^{\text{maxk}+1}$ ，成立。
若 $2^i \leqslant R - x$ ，跳过去落在 $R$ 左侧或正好落在 $R$ ， $S_{x+2^i} \leqslant S_R \leqslant T$ 必然通过，跳完剩余距离 $< 2^{i+1} - 2^i = 2^i$ 。
若 $2^i > R - x$ ，跳过去一定越过 $R$ ， $S_{x+2^i} > T$ ，检查失败，不跳，剩余距离仍 $< 2^i$ 。

每轮结束都把“剩余距离 $< 2^{i+1}$ ”收紧成“剩余距离 $< 2^i$ ”，到 $i = 0$ 时剩余距离 $< 1$ ，只能有 $x = R$ 。

换个说法：这个过程就是把 $R$ 按二进制从高位到低位拆开，逐位决定这一位取不取。同时也能看出，一旦某一步跳失败，后面的步长只会更小，永远不会再需要它，所以“放弃”是安全的。

与 rbook 倍增跳跃模板的对应：模板里

cpp

1bool check(int pos, int y) { return pos <= y; }

判定的是“有没有超过题目给的目标位置 $y$ ”。本题没有显式给出 $y$ ——可达边界是由 $T$ 隐式决定的，判定改成

cpp

1bool check(int pos, ll T) { return pos <= n && sum[pos] <= T; }

其余结构一字不差：先取 maxk = floor(log2 N)，再从 2^maxk 试到 $2^0$ 。

$N = 5$ ， $T = 8$ 时的三跳如下（S = [0, 1, 3, 6, 10, 15]，maxk = 2）：

轮次	尝试步长 $2^i$	落点 $x + 2^i$	$S_{\text{落点}}$	与 $T = 8$ 比较	是否跳	跳后 $x$
1	$4$	$4$	$10$	$10 > 8$	否	$0$
2	$2$	$2$	$3$	$3 \leqslant 8$	是	$2$
3	$1$	$3$	$6$	$6 \leqslant 8$	是	$3$

三轮结束停在 $x = 3$ ，与暴力结果一致： $S_3 = 6 \leqslant 8$ 而 $S_4 = 10 > 8$ 。

两处必须注意的边界：

check 里必须判 pos <= n。若只写 sum[pos] <= T，当 R = N 时越界读到 sum[N+1] 的未赋值区域（值为 $0$ ）会把不可行误判成可行。
maxk 只由 $N$ 决定，进来算一次即可，不能按 $T$ 或总和去算。

为什么这样就是在线的：主循环是“读一个 $T$ → 立即输出 → 读下一个 $T$ ”，全程没有“先收集询问”的步骤，任何时候中断都不会影响已给出的答案。

代码

C++ 版：

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/**
 * 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-18 16:43
 * update_at: 2026-10-18 16:43
 */
// main.cpp：区间最大和 —— 在线倍增（binary jump）。
// 思路：
//   1. A[i] 都是正数，前缀和 sum[i] = A[1] + ... + A[i] 严格递增，
//      所以 "sum[i] <= T" 关于 i 具有二分性：前面全可行，后面全不可行；
//   2. 于是可以用倍增跳跃：从位置 0 出发，从大到小试跳 2^i 个位置，
//      跳过去之后仍然满足 sum[pos] <= T 才真的跳，最后停下的位置就是最大的 k；
//   3. 每个询问 O(log N)，读到一个回答一个，不需要等后面的询问，所以是在线的。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n, q;
int maxk;         // 最大的 i，使得 2^i <= n，跳跃从 2^maxk 开始试
ll sum[MAXN];     // sum[i] = A[1] + ... + A[i]，sum[0] = 0；值域 1e5 * 1e9，要用 ll

// 得到最大的 k，使得 2^k <= n
int get_max_k(int n)
{
    int k = 0;
    while ((1LL << (k + 1)) <= n) k++;
    return k;
}

// 检查跳到位置 pos 之后是否仍然可行（前缀和不超过 T）
bool check(int pos, ll T)
{
    return pos <= n && sum[pos] <= T;
}

// 从位置 0 开始向右跳，求最后一个满足 sum[pos] <= T 的位置
int jump(ll T)
{
    int x = 0; // 当前停留位置，起点是 0：sum[0] = 0 一定可行
    for (int i = maxk; i >= 0; i--) {
        int len = (1 << i); // 本轮尝试的跳跃长度是 2^i
        int pos = x + len;  // 跳过去之后的位置
        if (check(pos, T)) {
            x = pos;        // 不越界且不超过 T 才真的跳
        }
    }
    return x;
}

int main()
{
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        ll a;
        scanf("%lld", &a);
        sum[i] = sum[i - 1] + a; // 前缀和
    }

    maxk = get_max_k(n);

    while (q--) {
        ll T;
        scanf("%lld", &T);
        printf("%d\n", jump(T)); // 读完一个询问马上回答
    }
    return 0;
}

Python 版（同一算法）：

python

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#!/usr/bin/env python3
# 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-18 16:43
# update_at: 2026-10-18 16:43
#
# 在线倍增（binary jump）：
#   sum[i] = A[1] + ... + A[i] 严格递增，"sum[i] <= T" 具有二分性，
#   所以从位置 0 出发，从大到小试跳 2^i，跳过去仍然可行就跳，最后停下处即答案。
#   每读到一个 T 就立刻回答，符合题面的"在线"要求。

import sys


def jump(sum_: list[int], n: int, top: int, t: int) -> int:
    """返回最大的 k，满足 sum_[k] <= t。"""
    pos = 0  # 当前停留位置；sum_[0] = 0 一定可行
    for i in range(top, -1, -1):
        nxt = pos + (1 << i)  # 本轮尝试跳 2^i 个位置
        if nxt <= n and sum_[nxt] <= t:
            pos = nxt  # 不越界且不超过 T 才真的跳
    return pos


def solve() -> None:
    read = sys.stdin.buffer.readline
    n, q = map(int, read().split())

    sum_ = [0] * (n + 1)  # sum_[i] = A[1] + ... + A[i]
    a = list(map(int, read().split()))
    for i in range(1, n + 1):
        sum_[i] = sum_[i - 1] + a[i - 1]

    top = n.bit_length() - 1  # 最大的 i，使得 2^i <= n

    out = []
    for _ in range(q):
        t = int(read())          # 一次只处理一个询问
        out.append(str(jump(sum_, n, top, t)))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

复杂度

预处理：前缀和 $O(N)$ ，求 maxk 为 $O(\log N)$ 。
每个询问恰好枚举 maxk + 1 = O(\log N) 档步长，每档 $O(1)$ 判定。
总计 $O(N + Q \log N)$ ， $N = Q = 10^5$ 时约 $1.7 \times 10^6$ 次操作；空间 $O(N)$ 存前缀和。

解法二：离线排序 + 双指针

思路

如果允许先看完所有询问，还有一条更省的路： $T$ 越大，答案 $k$ 越大。因为 $S$ 递增， $T_1 \leqslant T_2$ 时 $\{k : S_k \leqslant T_1\} \subseteq \{k : S_k \leqslant T_2\}$ ，两个答案都是各自集合的最大值，后者不会更小。

于是把询问按 $T$ 升序排好，答案也就排好了序，可以用一个只向右走、永不回退的指针 k 边推边答：

text

1
2
3
4k = 0
按 T 升序枚举询问 t:
    while k + 1 <= N and S[k+1] <= t:  k += 1
    该询问的答案就是 k

排序打乱了原顺序，因此每个询问要带着自己的原始编号 id 一起排，算完后写回 ans[id]，最后按 0..Q-1 顺序输出。

这个思路和“排序 + 双指针”家族的题是一样的：把询问之间的无序变成有序，就能消除重复扫描。代价是不能在线。

代码

C++ 版：

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/**
 * 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-18 16:43
 * update_at: 2026-10-18 16:43
 */
// main-offline.cpp：区间最大和 —— 离线做法：把询问按 T 排序 + 双指针。
// 思路：
//   1. 前缀和 sum[i] 严格递增，所以对固定的 T，答案 k 就是"sum[k] <= T"的最后一个 k；
//   2. T 越大答案 k 越大，于是把全部询问按 T 从小到大排序，
//      维护一个只会向右走的指针 k，边加边回答：sum[k+1] <= T 就一直 k++；
//   3. 排完序后每个位置最多被 k 扫过一次，总时间 O(N + Q log Q)，
//      但要求先读入所有询问再统一回答，因此是离线的。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n, q;
ll sum[MAXN];     // sum[i] = A[1] + ... + A[i]，sum[0] = 0
int ans[MAXN];    // ans[id]：第 id 个询问（按读入顺序编号）的答案

struct Query {
    ll t;         // 询问值 T
    int id;       // 原始读入顺序，用于把答案放回原位
};
Query query[MAXN];

// 按 T 从小到大排序：排序后答案 k 单调不减
bool cmp(Query a, Query b)
{
    return a.t < b.t;
}

int main()
{
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        ll a;
        scanf("%lld", &a);
        sum[i] = sum[i - 1] + a;
    }

    for (int i = 0; i < q; i++) {
        scanf("%lld", &query[i].t);
        query[i].id = i;
    }

    sort(query, query + q, cmp);

    int k = 0; // 双指针：当前已验证 sum[k] <= 当前 T 的最大位置
    for (int i = 0; i < q; i++) {
        // T 递增，k 只向右走，所以这里整体是线性的
        while (k + 1 <= n && sum[k + 1] <= query[i].t) k++;
        ans[query[i].id] = k;
    }

    for (int i = 0; i < q; i++) {
        printf("%d\n", ans[i]); // 按原始顺序输出
    }
    return 0;
}

Python 版（同一算法）：

python

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#!/usr/bin/env python3
# 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-18 16:43
# update_at: 2026-10-18 16:43
#
# 离线做法：把询问按 T 排序 + 双指针。
#   sum[i] 严格递增 => T 越大答案 k 越大，
#   于是按 T 升序处理询问，指针 k 只会向右走，边加边回答。
#   先读完所有询问再统一处理，因此是离线的。

import sys
from itertools import accumulate


def solve() -> None:
    read = sys.stdin.buffer.readline
    n, q = map(int, read().split())

    a = []
    while len(a) < n:  # 数组可能被拆成多行，读满 n 个为止
        a.extend(map(int, read().split()))
    sum_ = [0, *accumulate(a)]  # sum_[i] = A[1] + ... + A[i]

    queries = []
    while len(queries) < q:
        queries.extend(map(int, read().split()))

    # 按 T 升序排序，同时记住原始下标，最后要按原顺序输出
    order = sorted(range(q), key=lambda i: queries[i])

    ans = [0] * q
    k = 0  # 双指针：当前已验证 sum_[k] <= 当前 T 的最右位置
    for i in order:
        t = queries[i]
        while k + 1 <= n and sum_[k + 1] <= t:  # k 只向右走
            k += 1
        ans[i] = k

    sys.stdout.write("\n".join(map(str, ans)) + "\n")


if __name__ == "__main__":
    solve()

复杂度

排序： $O(Q \log Q)$ 。
双指针：k 从 $0$ 单调走到至多 $N$ ，全程 $O(N)$ ，均摊到每次询问是 $O(1)$ 。
总计 $O(N + Q \log Q)$ ，空间 $O(N + Q)$ 存前缀和与询问。

注意它不满足题面要求：必须先把 $Q$ 个询问全部读入才能排序，与“不能等待收到所有询问后再统一处理”直接冲突。所以它只能当作另一种思路来学，不能作为本题提交的正式答案。

复杂度对比

解法	时间	空间	在线	适用场景
`brute.cpp` 逐格走	$O(NQ)$	$O(N)$	是	只用于对拍
解法一倍增跳跃	$O(N + Q\log N)$	$O(N)$	是	本题正式解；任何“单调边界 + 可 $O(1)$ 判可行”的场景
解法二离线双指针	$O(N + Q\log Q)$	$O(N + Q)$	否	允许离线时，可去掉每问的 $\log$

两个正解的渐进总量其实同阶（ $\log N$ 与 $\log Q$ 同数量级），所以选择依据不是速度，而是题目许不许离线。真正要记住的区分是：倍增跳跃是“单点定位”技术，每问独立；离线双指针是“整体排序”技术，靠询问之间的单调关系省掉重复工作。

总结

一句话本质：题目要的不是“求和”，而是“在一条单调递增的前缀和数组上找最后一个不超过 $T$ 的位置”。一旦把它看成定位问题而不是累加问题， $O(NQ)$ 就自然变成 $O(Q\log N)$ 。

倍增跳跃的适用条件是这个仓库里反复出现的四条：数据是链式/线性的、判定函数 $f$ 具有二分性（单调）、 $f(i)$ 可以 $O(1)$ 求出、位置跳转可合并。本题由 $A_i > 0$ 一次性满足前两条， $f$ 就是一次前缀和比较，第四条由“跳 $2^i$ 等于连跳两次 $2^{i-1}$ ”保证。
与标准模板的唯一差别是 check 的判据来源：模板由题目直接给出目标位置，本题由 $T$ 隐式给出。
“在线”是题面写死的要求，它排除的正是“排序询问”这一整类做法；做题时先看这句话，再决定能不能用离线技巧。
边界只有三处： $T = 0$ 时答案为 $0$ 、 $T = \sum A$ 时答案为 $N$ 、check 必须判越界。
前缀和要用 long long： $10^5 \times 10^9 = 10^{14}$ 会溢出 int。