【蓝桥第九场小白赛】（字符迁移-差分前缀和详解）

差分数组核心：区间变化前加后减

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL=long long;int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);LL n,q;cin>>n>>q;string s;cin>>s;//int diff[n+1]={0};//差分数组 diff 是一个自动数组，它的大小取决于变量 n。//未初始化的数组元素的值是不确定的，所以在更新差分数组时，可能会出现问题。vector<int> diff(n + 1, 0)while(q--){LL l,r,k;cin>>l>>r>>k;k%=26;diff[l-1]+=k;diff[r]-=k;}for(int i=1;i<=n;i++){diff[i]+=diff[i-1];}for(int i=0;i<n;i++){s[i]='a'+(s[i]-'a'+diff[i])%26;}cout<<s<<endl;return 0;}

假设有一个长度为5的数组 arr，初始值为 [0, 0, 0, 0, 0]，现在希望对其中的某个区间进行增加操作。

假设操作是 l = 2, r = 4, k = 3，即将数组中下标为1到下标为3的元素都增加3。

1. 首先创建一个大小为 n + 1 的差分数组 diff，这里 n 是数组 arr 的长度，所以 diff 的长度为6，初始值为 [0, 0, 0, 0, 0, 0]。

2. 然后，我们执行 diff[l - 1] += k 和 diff[r] -= k 这两行代码。

   • diff[2 - 1] += 3，即 diff[1] += 3，所以 diff 变为 [0, 3, 0, 0, 0, 0]。
   • diff[4] -= 3，所以 diff 变为 [0, 3, 0, 0, -3, 0]。

差分数组 diff 记录了每个位置的偏移量变化。

3. 最后对差分数组进行前缀和操作，得到最终的数组。即对于位置 i，最终的值为 arr[i] = arr[i - 1] + diff[i]。(同diff[i]+)
   • arr[0] = 0 + 0 = 0
   • arr[1] = arr[0] + 3 = 3
   • arr[2] = arr[1] + 0 = 3
   • arr[3] = arr[2] + 0 = 3
   • arr[4] = arr[3] - 3 = 0

最终得到的数组 arr 为 [0, 3, 3, 3, 0]。