课堂笔记：前缀和、差分与约瑟夫环

一、前缀和

作用：快速求区间和，避免每次查询都遍历区间。
核心公式：
s[i] = s[i-1] + a[i]
区间和查询：sum(L,R) = s[R] - s[L-1]

代码模板：

const int N = 100005;
int a[N], s[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];   // 计算前缀和
    }
    int l, r;
    cin >> l >> r;
    cout << s[r] - s[l-1] << endl;  // 查询区间和
    return 0;
}

二、差分

作用：快速修改区间的值（例如区间整体加 k）。
核心公式：
差分数组：c[i] = a[i] - a[i-1]
还原原数组：a[i] = a[i-1] + c[i]（即差分数组的前缀和）

差分题目四步走：

1. 根据原数组计算差分数组 c[i] = a[i] - a[i-1]
2. 区间修改：对 [L,R] 整体加 k
c[L] += k;
c[R+1] -= k;
3. 还原原数组：a[i] = a[i-1] + c[i]
4. 在还原后的 a 数组中统计答案

代码模板（区间修改 + 还原）：

const int N = 100005;
int a[N], c[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[i] = a[i] - a[i-1];   // 初始化差分数组
    }
    int L, R, k;
    cin >> L >> R >> k;
    c[L] += k;
    c[R+1] -= k; 

    // 还原原数组并输出
    for (int i = 1; i <= n; i++) {
        a[i] = a[i-1] + c[i];
        cout << a[i] << " ";
    }
    return 0;
}

三、约瑟夫环问题

问题描述：n 个人围成一圈，从第 1 个人开始报数，数到 m 的人出列，输出出列顺序。
思路：用数组 a[i] 标记状态，1 表示在圈内，0 表示已出列。

代码（含环形处理）：

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, a[N];
int p, bs;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) a[i] = 1;  // 初始都在圈内
    int sy = n;  // 剩余人数

    while (sy > 0) {
        p++;                        // 向后移动
        if (p == n + 1) p = 1;      // 环形处理，回到开头
        if (a[p] == 0) continue;    // 已出列，跳过
        bs++;                       // 报数
        if (bs == m) {              // 报到 m
            cout << p << endl;
            a[p] = 0;               // 出列
            bs = 0;                 // 报数清零
            sy--;                   // 剩余人数减一
        }
    }
    return 0;
}

关键点：

• p：当前位置，每次循环先移动再判断。
• bs：当前报数，报到 m 后出列并清零。
• 环形处理：if (p == n + 1) p = 1; 让遍历循环。

总结对比

前缀和与差分互为逆运算：差分数组的前缀和还原原数组，原数组的差分得到差分数组。