前缀和+差分+蓝桥双周赛：字符迁移

本文主要是介绍前缀和+差分+蓝桥双周赛：字符迁移，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前缀和：

首先需要知道前缀和的概念：即数组该位置之前的元素之和。

还有一个重要的点，在进行前缀和的运算时，下标从1开始，设数组a[0]=0;

比如a[5] = {0,1,2,3,4};

求a[1]的前缀和：a[1];

求a[2]的前缀和：a[1]+a[2];

......

为什么下标要从1 开始：为了方便后面的计算，避免下标转换，设为零，不影响结果

前缀和的作用： 快速求出元素组中某段区间的和

一维数组的前缀和问题:

求数组a中（l，r）区间的和 --->用到前缀和

1. 需要定义两个数组，第一个为原始数组(a[])，第二个为前缀和数组(s[])

   //初始化原数组
   int a[1000005] = {0};
   for (int i = 1; i <= n; i++) {cin>>a[i];
   }

2. 公式：s[i] = s[i-1]+a[i]

   //前缀和的计算
   int s[1000005] = {0};
   for (int i = 1; i <=n ; i++) {s[i] = s[i-1]+arr[i];
   }

3. 输入区间范围(l,r)，s[r]-s[l-1]的结果就是所求区间的和

   sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
   sum[l-1]=a[1]+a[2]+a[3]+a[l-1];sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
   

   while (m-- !=0){int l,r;cin>>l>>r;cout<< s[r]-s[l-1] ;
   }

差分问题：

首先明白差分的概念：差分其实就是前缀和的逆运算

差分的作用：如果对某个区间需要每个元素加上C则需要使用差分来减少时间复杂度

给定a[1],a[2]....a[n];构造擦划分数组b[N];使得a[i] = b[i]+b[2]+....+b[i];

差分的重点是：构造辅助数组b[]

解释

b[1] = a[1] b[2] = a[2] - a[1] b[3 ]= a[3] - a[2] ... b[n] = a[n] - a[n-1]

两个数组：a[],b[]，a[]称为b[]的前缀和，b[]称为a[]的差分

差分的下标也是从1开始;

核心操作：

将a[L~R]全部加上C，等价于：b[L] +=C, b[R+1] -=C;

一维数组的差分问题：

1. 首先初始化数组s[]

   int b[100005] = {0};
   for (int i = 1; i <=n ; i++) {cin>>a[i];
   }

2. 按照上面构造数组方式构造b[]数组(两种方法)，公式：b[i] = a[i]-a[i-1]

   //构造差分数组
   for (int i = 1; i <=n ; i++) {b[i] = a[i]-a[i-1];
   }
   //插入方法：假设a[]中全部为0 则b[]也全部为0，可以执行插入操作
   for(int i = 1; i <= n; i++){insert(i,i,a[i])
   }

   插入操作：

   void insert(int l,int r,int c){b[l] +=c;b[r+1] -=c;
   }

3. 将所求区间（l,r）在b[]数组划分出来并加上c,公式：b[l] +=c,b[r+1] -=c;

   int l,r,c;
   cin>>l>>r>>c;
   b[l] +=c;
   b[r+1] -=c;

   因为a[]数组是b[]数组的前缀和，b[]是a[]的差分，所以在b[]的某个区间上+c会影响的a区间上的结果

由于差分可以让一个序列中某个区间内的所有值均加上或减去一个常数。

可以将对a数组任意区间的同一操作优化到O(1)。实现算法的优化。

下面是题目

原题用暴力的解法是没法通过的，所以我用的差分的方法写。

#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
typedef long long ll;
ll a[N],b[N],n,m,l,r,k;
string s;
char c[N];int main()
{cin>>n>>m;cin >> s;for(int i=1;i<=n;i++){a[i] = s[i-1] - 'a';b[i] = a[i] - a[i-1];
}while(m--){cin>>l>>r>>k;b[l] += k;b[r+1] -= k;}for(int i=1;i<=n;i++)a[i] = a[i-1] + b[i];for(int i = 1;i<=n;i++){c[i] = (a[i])%26 + 'a';cout<<c[i];}return 0;
}

这篇关于前缀和+差分+蓝桥双周赛：字符迁移的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---