前缀和练习

前缀和的精髓是一句话：预处理一次，之后每次查询都很快。建表要 $O(n)$，但建好后每次区间求和只要 $O(1)$。

假设一道题有 $q$ 次询问，每次问某段区间的和：

• 不用前缀和：每次现加，单次 $O(n)$，总共 $O(nq)$；
• 用前缀和：建表 $O(n)$，每次查询 $O(1)$，总共 $O(n+q)$。

当 $n$ 和 $q$ 都到 $10^5$ 时，前者约 $10^{10}$ 次运算必然超时，后者只有约 $2\times 10^5$ 次，轻松通过。

// 建表一次，回答 q 次询问
for (int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
while (q--) {
    int l, r; cin >> l >> r;
    cout << s[r] - s[l-1] << "\n";
}

判断“该不该用前缀和”的信号：题目多次询问区间和、且数组不再改动。若中途还要修改元素，前缀和就得重建，那就要换更高级的数据结构了。