前缀和 · 考级冲刺

前缀和是“用空间换时间”的经典技巧：预处理出“前 $i$ 项的和”，之后任意区间和都能 $O (1)$ 算出。

定义 $s_{i} = a_{1} + a_{2} + \dots + a_{i}$ ，约定 $s_{0} = 0$ 。那么区间 $[l, r]$ 的和就是 $s_{r} - s_{l - 1}$ ——一次减法搞定，不用再循环累加。

// 下标从 1 开始, s[0] = 0
for (int i = 1; i <= n; i++)
    s[i] = s[i - 1] + a[i];

// 查询区间 [l, r] 的和
long long query(int l, int r) {
    return s[r] - s[l - 1];
}

预处理 $O (n)$ ，每次查询 $O (1)$ 。若有 $q$ 次询问，朴素做法是 $O (n q)$ ，前缀和降到 $O (n + q)$ ，数据大时差距巨大。

坑：一是下标，用 $s_{r} - s_{l - 1}$ 时若下标从 $0$ 开始要仔细推边界，推荐数组从 $1$ 存、留出 $s_{0}$ ；二是和可能很大， $s$ 要开 long long 防溢出。二维前缀和同理，用容斥算矩形和。