蓝桥杯算法笔记|差分学习

！前情回顾

前缀和18437蓝桥账户中心

练习代码：

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int n,q;cin>>n>>q;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int sum[n];sum[0]=a[0];
  for(int i=1;i<n;i++){
    sum[i]=sum[i-1]+a[i];
  }
  while(q--){
    int l,r;
    cin>>l>>r;
    if(l==1)
    cout<<sum[r-1]<<'\n';
    else
    cout<<(sum[r-1]-sum[l-2])<<'\n';
  }
  return 0;
}

还需注意：

注意if-else的情况，注意边界。

一、差分数组

定义：

差分数组是原始数组相邻元素之间的差所构成的数组。对于给定的数组 nums，其差分数组 diff 定义为：diff[i] = nums[i] - nums[i - 1]（i > 0），diff = nums。

差分代码：

a[0]=0;
for(int i=1;i<=n;i++){
diff[i]=a[i]-a[i-1];
}

作用：

1、高效的区间修改：

差分数组可以在 O(1) 的时间复杂度内完成对原始数组某个区间的元素增减操作。

例如，要对区间 [i, j] 内的所有元素增加 val，只需执行 diff[i] += val 和 diff[j ] -= val（如果 j 1 < diff.length）。

//区间【l，r】内所有元素都加上x
 diff[i] += val 
 diff[j ] -= val

2、快速计算前缀和：

通过差分数组可以快速计算原始数组的前缀和。例如，要计算 nums 到 nums[i] 的前缀和，只需计算 diff 到 diff[i] 的累加和。

做题疑问：

 1、我的疑问是怎么才能实现让他输入多组数据

 2、同时满足当数组a【】只有一个1：从i=1开始

我的代码：

#include <bits/stdc++.h>
using namespace std;
//我的疑问是怎么才能实现让他输入多组数据
void fun(int n,int m){
int a[n+3];a[0]=0;
  for(int i=1;i<=n;i++){ cin>>a[i];}
  //求差分数组
  int d[n+3];d[0]=0;
  for(int i=1;i<=n;i++){d[i]=a[i]-a[i-1];}
  //区间更新就是给差分数组的从d【x】+z；d【y-1】-z；再用差分数组求求前缀和输出
  while(m--){
    int x,y,z;cin>>x>>y>>z;
    d[x]=d[x]+z;
    d[y+1]=d[y+1]-z;
    }
 
    for(int i=1;i<=n;i++){a[i]=a[i-1]+d[i];} 
    for(int i=1;i<=n;i++){cout<<a[i]<<' ';}
     cout<<'\n';}

int main()
{
  // 请在此输入您的代码
  int n,m;
  while(cin>>n>>m)fun(n,m);
  return 0;
}

 错因警告：

【刚开始过不了是因为，空格得用单引号'  '之内的，而不是双引号“ ”之内的，并且定义a【n】d【n】时，数组越界了，改用n+3够用了】 

 错因警告：

【记得看题目给的范围要求，因为用了int没有用long long导致正确率只有四分之一】