P4760 K个元素和（入门）

解题思路

想象你面前摆着一排写着数字的糖果卡片，老师请你把"连续 K 张卡片"上的数字加起来，还要把每一种连续取 K 张的方法都算出来。如果每次都从第一张开始重新加一遍，n 个数要被重复加很多次，太慢了。

聪明的小朋友会请出"前缀和"这个法宝。什么是前缀和呢？我们先算出"前 1 张的和、前 2 张的和、前 3 张的和……"存进数组 pre，pre[i] 表示前 i 张卡片数字的总和。有了它，想知道从第 L 张到第 R 张的总和，只需要一步：pre[R] - pre[L-1]。也就是说，用"前 R 张的和"减去"前 L-1 张的和"，中间剩下的正好就是第 L 张到第 R 张，一次减法就搞定，不用重新一个个加。

回到本题：我们要输出所有长度为 K 的连续子段的和，这样的子段一共有 n-K+1 个。让起点 i 从 1 走到 n-K+1，对每个起点用 pre[i+K-1] - pre[i-1] 求出这一段的数字和，数字之间用空格隔开。

拿样例试一试：n=10，K=3，数字是 2 1 3 6 4 5 8 7 0 9。第一个子段 2+1+3=6，第二个 1+3+6=10，第三个 3+6+4=13……最后一个 7+0+9=16，输出 6 10 13 15 17 20 15 16，和题面一模一样。

还需要注意两点：第一，n 最大有 500000，前缀和数组要开成 500005，多留一点余量；第二，很多个数字加起来可能很大，要用 long long 来存，防止溢出算错。

参考代码

// 求所有连续且长度为K的子段和，输出每个子段和，用前缀和加速
#include <iostream>
int main() {
    int n, K;
    std::cin >> n >> K;
    long long pre[500005] = {0}; // pre[i] 表示前 i 个数的和
    for (int i = 1; i <= n; ++i) {
        long long x;
        std::cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    // 从 i 开始的长度为 K 的子段和 = pre[i+K-1] - pre[i-1]
    for (int i = 1; i + K - 1 <= n; ++i) {
        if (i > 1) std::cout << ' ';
        std::cout << pre[i + K - 1] - pre[i - 1];
    }
    std::cout << '\n';
    return 0;
}

复杂度分析

先花 O(n) 的时间建好前缀和数组，再花 O(n) 的时间枚举所有长度为 K 的子段并输出，所以总时间复杂度是 O(n)。因为要多开一个 pre 数组存前缀和，空间复杂度也是 O(n)。n 最大 500000，大约 100 万次基本运算，1 秒内完全能跑完，这也是前缀和比"每次从头加"快得多的原因。