首页 > 其他分享 >2.diff差分【模板】

2.diff差分【模板】

时间:2024-03-06 23:00:12浏览次数:28  
标签:int 样例 差分 数组 diff 模板 描述

  • [[#差分数组|差分数组]]
    • [[#差分数组#三个数组的关系|三个数组的关系]]
  • [[#题目描述|题目描述]]
  • [[#输入描述|输入描述]]
  • [[#输出描述|输出描述]]
  • [[#输入样例1|输入样例1]]
  • [[#输出样例1|输出样例1]]

差分数组

  • 如下叫做差分数组

\[d_{i} = a_{i} - a_{i-1} \]

  • 又有

\[\sum_{j=1}^{i} {d_{j}} = d_{1}+d_2+\dots+d_i \]

  • 而上述式子可以写作

\[d_{1}+d_2+\dots+d_{i}= (a_1-a_{0})+(a_2-a_1)+\dots+(a_{i-1}-a_{i-2})+(a_i-a_{i-1}) \]

  • 又因为 \(a_0=0\) 于是上式(左侧为一个前缀和数组)

\[\sum_{j=1}^{i} {d_{j}}=a_i \]

  • image.png|675
  • 差分数组可以实现后缀区间的修改,是静态的修改(修改完成之后进行询问,不可以边询问边修改)
  • 如果对 \(d_2\) 增加了 \(x\) ,那么 \(a_{2}、a_{3}、a_4\) 以后都会增加 \(x\) ,那么当在 \(d_4\) 处减少 x 后,就抵消了从 \(d_4\) 开始往后的修改,做到了只在 \(a_{2}、a_3\) 两个位置的修改(增加x)
  • image.png

三个数组的关系

  • image.png

  • 题目书写模板

  • 读入数组 => 求出差分数组 => 修改差分数组 => 更新原数组 => 求出前缀数组 => 打印结果

  • image.png

题目描述

给定一个长度为n的数组a,和两个整数p,q。

先进行p次区间加操作:将区间[l,r]的数字都加上�x。

再进行q次区间查询操作:求出[l,r]的数字之和。

对于每次区间查询操作,输出结果。

输入描述

第一行三个整数 n,p,q。(1≤n≤105,0≤p≤105,0≤10^5≤q)

第二行 n 个整数表示数组 a。(−109≤a_i​≤109)

接下来 p 行,每行三个整数 l,r,x。(1≤l≤r≤n,−109≤x≤109)

接下来q行,每行两个整数l,r。(1≤l≤r≤n)

输出描述

对于每次区间查询操作,输出结果。

输入样例1

5 1 2
1 1 1 2 2
1 4 2
1 3
1 5

输出样例1

9
15

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 9;
// 全局数组自动初始化为0
ll a[N], prefix[N], diff[N];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, p, q;
  cin >> n >> p >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) diff[i] = a[i] - a[i - 1];
  while (p--) {
    int l, r;
    ll x;
    cin >> l >> r >> x;
    diff[l] += x, diff[r + 1] -= x;
  }
  // 更新a
  for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + diff[i];
  // prefix
  for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << prefix[r] - prefix[l - 1] << '\n';
  }
  return 0;
}

标签:int,样例,差分,数组,diff,模板,描述
From: https://www.cnblogs.com/Phantasia/p/18057847

相关文章

  • 初中英语优秀范文100篇-099Keep patient when facing difficulties-面对困难时保持耐
    PDF格式公众号回复关键字:SHCZFW099记忆树1IstillrememberthefirsttimeIrodeabicyclewhenIwasseven.翻译我仍然记得我七岁时第一次骑自行车的情景简化记忆自行车句子结构主语I表示我谓语stillremember仍然记得宾语从句thefirsttimeIrodea......
  • 简单实现邮件模板功能
    系统中经常有需要发送提醒邮件的需求,而且邮件类型和内容往往又不同,有些还需要跟业务字段做关联。这种情况下,就需要用到邮件模板功能,可以通过在模板中定义业务字段标记,通过模板引擎或自定义代码来实现这些字段的填充。下面是一个自己写的简单的,字符串替换方式实现的邮件模板功能。......
  • Maven安装本地的jar包和创建带模板的自定义项目
    Maven安装本地的jar包如果没配置Maven的环境变量,需要先CD到maven的安装目录,因为没配置环境变量,mvn命令是无法在maven安装目录以外的目录运行。cdC:\Maven\apache-maven-3.6.3\bin然后执行下面命令格式如下:mvninstall:install-file//固定格式,maven的语法-Dfile=ali......
  • 二分搜索模板
    目录最基本的二分搜索寻找左边界的二分搜索寻找右边界的二分搜索统一记忆为闭区间,只需要修改nums[mid]==target时收缩哪边边界,以及越界情况最基本的二分搜索defbinary_search(nums:List[int],target:int):left=0right=len(nums)-1while(left<=right):......
  • WPF 样式与模板
    参考样式和模板如何为控件创建样式如何为控件创建模板ContentPresenter环境软件/系统版本说明WindowsWindows10专业版22H219045.4046MicrosoftVisualStudioMicrosoftVisualStudioCommunity2022(64位)-17.6.5Microsoft.NetSDK8.0.10......
  • P3369 【模板】普通平衡树
    原题链接题解1stl模拟,注意lowerbound的效果和pos的返回值code1#include<bits/stdc++.h>usingnamespacestd;vector<int>a;intmain(){intn;cin>>n;while(n--){intop,x;cin>>op>>x;if(op==1)a.inser......
  • 初中英语优秀范文100篇-097-I no longer fear difficulties-我不再害怕困难
    PDF格式公众号回复关键字:SHCZFW097记忆树1Iusedtobeafraidofspeakinginpublic.翻译我曾经害怕在公共场合发言简化记忆发言句子结构主语I表示我谓语usedtobeafraid使用usedto表示过去的习惯或常态,beafraid为系表结构,表示害怕的情感状态宾语of......
  • git diff去除^M的方法
     在使用Git进行版本控制时,有时候会遇到在文件中出现了^M字符的情况。这个问题通常出现在Windows操作系统中,并且会影响文件在不同操作系统之间的可移植性。^M字符是回车符的表示,在Windows操作系统中,每个文本行的结尾都是由回车符(\r)和换行符(\n)组成的,而在类Unix......
  • 给大家推荐一款基于Vue3通用型后台管理模板
    ​ 给大家推荐一款基于Vue3通用型后台管理模板这款Vue3后台管理模板介绍如下:        使用Vue3、Vite、ElementPlus、Pinia最新开发技术栈,拥有完整的Token登录鉴权、路由配置、界面简洁美观,可根据需要灵活配置主题、系统采用响应式布局,自适应各类屏幕尺寸、源代码有......
  • 代码模板
    贴这里,防丢。会更新算法模板,坑会慢慢填。写题模板/*Author:Rainypaster(lhy)Time:File:Email:[email protected]*/#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<bits/stdc++.h>usingna......