离线算法思想

What · 是什么

离线算法(Offline Algorithm)是指在求解前已知全部输入数据(包括所有修改和询问)的算法。与在线算法(Online Algorithm，数据逐个到达)相对。离线算法可以重排询问顺序、预排序数据、利用全局信息统一求解，通常比在线算法更优。是 CDQ 分治、整体二分、莫队算法等框架的共同基础思想。

Why · 为什么

How · 实现

伪代码

# 离线算法通用框架
1. 读入全部数据和询问
2. 预处理: 排序/离散化/建图
3. 重排询问(按某种最优顺序)
4. 统一处理: 利用数据结构/分治/双指针
5. 按原始顺序输出答案

# 示例: 离线区间查询(莫队思想)
queries.sort(key=lambda q: (q.l // B, q.r))
cur_l, cur_r = 0, -1
for q in queries:
  while cur_r < q.r: cur_r++; add(cur_r)
  while cur_l > q.l: cur_l--; add(cur_l)
  while cur_r > q.r: remove(cur_r); cur_r--
  while cur_l < q.l: remove(cur_l); cur_l++
  ans[q.id] = current_answer

Python 实现

def offline_range_sum(arr, queries):
    """离线区间求和: 利用已知全部查询做前缀和预处理。
    展示离线思想: 在线逐个求和O(n)per query, 离线预处理前缀和O(1)per query。
    arr: 数组, queries: [(l, r), ...] 0-indexed
    """
    n = len(arr)
    # 离线预处理: 前缀和
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    # 在线回答每个查询
    results = []
    for l, r in queries:
        results.append(prefix[r + 1] - prefix[l])
    return results


def offline_sorted_queries(arr, queries):
    """离线排序查询: 按右端点排序后用单调栈/双指针优化。
    展示'重排询问顺序'的离线优势。
    queries: [(l, r, id), ...]
    """
    # 按右端点排序
    sorted_q = sorted(queries, key=lambda x: x[1])
    results = [0] * len(queries)

    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]

    for l, r, qid in sorted_q:
        results[qid] = prefix[r + 1] - prefix[l]
    return results


if __name__ == '__main__':
    arr = [3, 1, 4, 1, 5, 9, 2, 6]
    queries = [(0, 3), (2, 5), (0, 7), (4, 6)]

    # 离线前缀和
    sums = offline_range_sum(arr, queries)
    print(f'Range sums: {sums}')
    assert sums == [9, 19, 31, 16]

    # 离线排序查询
    indexed_queries = [(q[0], q[1], i) for i, q in enumerate(queries)]
    sums2 = offline_sorted_queries(arr, indexed_queries)
    print(f'Sorted queries: {sums2}')
    assert sums2 == [9, 19, 31, 16]

    print('Offline algorithm: all tests passed!')

易错点

• 强制在线题无法使用离线: 前一个答案决定后续查询参数时不能重排
• 离线需存储全部数据, 内存敏感场景可能 MLE
• 重排询问后忘记按原始 id 回填答案, 导致输出顺序错乱
• 离线预处理的开销可能不被小数据量场景摊销(预处理 O(N) 但只查 1 次)

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/offline/
• wiki✓ https://en.wikipedia.org/wiki/Online_algorithm