首页 > 其他分享 >浅谈差分

浅谈差分

时间:2024-03-02 20:22:47浏览次数:25  
标签:y2 浅谈 int 差分 lca x2 x1

1.前言

前置芝士:

  • 基本树上操作,lca。(用于树上差分。)

如有错误,欢迎各位大佬指出。(顺便复习一下远古算法。)

2.什么是差分

我们先给定一个数组 \(a\),长度为 \(n\),我们可以构造一个差分数组 \(b\),使得对于任意的 \(i(1\le i \le n)\),\(\displaystyle\sum_{j = 1}^{i} b_j=a_i\)。

那么如何构建一个普通的差分数组呢?

不难想到,我们假定 \(a_0=0\),则此时,对于任意的 \(b_i\),我们令它等于 \(a_i-a_{i-1}\),则当我们算 \(\displaystyle\sum_{j=1}^{i}b_j\) 时,所有 \(a_1,a_2...a_{i-1}\) 都会抵消掉,只剩下 \(a_i\),也正好满足了我们的前提条件。

3.差分数组的最普通应用

首先,我们先引入一个例题 P2367 语文成绩。题目意思大概就是说先给你一个序列,然后在进行区间加,最后求得区间的最小值即可。

而对于这种区间加减的操作,正是差分能够大展拳脚的地方。

我们先维护一个差分数组 \(b\)(以后皆假设差分数组为 \(b\)。),先将它全部初始化为0。假设当前我们面临的操作是将 \([l,r]\) 这个区间全部加上 \(x\)。由于差分的前缀和便是原数组,所以我们可以一开始将 \(b_l+x\),但是当你在算前缀和的时候,对于 \(r+1\) 及以后的前缀和,他都会多算一个 \(+x\),所以,为了将其抵消掉,我们需要将 \(b_{r+1}-x\)。

最后,处理完这些询问之后,我们在最后求一次前缀和即可。

可以发现,差分修改操作时间复杂度为 \(O(1)\),查询时间复杂度为 \(O(n)\)。

最后贴上一份代码:

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[5000005],c[5000005];
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	while(q--)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		c[l]+=x,c[r+1]-=x;//由于是差分,将c[l]+x,但为了抵消掉它对后面的贡献,我们将 c[r+1]-x 
	}
	int minn=INT_MAX;
	for(int i=1;i<=n;++i)
	{
		c[i]+=c[i-1];//求前缀和 
		a[i]+=c[i];//原数组记得加上 
		minn=min(minn,a[i]);//最小值 
	}
	cout<<minn<<endl;
}

4.差分数组的二维形式

我们上述的,全都是一个序列(一维)的情况,但是,差分仍然可以扩展到二维。(对于其定义,与一维相类似,这里不做过多赘述)

假设我们当前修改的二维区间为 \((x1,y1)\) 到 \((x2,y2)\),加上 \(x\)(\(x1\le x2,y1\le y2\))。显然,我们一开始仍然需要将起始位置 \(b_{x1,y1}+x\)。但随即我们可以发现,对于所有 \(x1-n,y1-n\) 它的值都被加上了 \(x\),但这个区间实际只能管到 \((x2,y2)\),所以,对于 \((x1,y2+1)\) 以及 \((x2+1,y1)\) 以后的所有格子都是当前加不到的,所以我们又将 \(b_{x1,y2+1}-x,b_{x2+1,y1}-x\)。但随即我们又可以发现,虽然减是减了,但对于 \((x2+1,y2+1)\) 及以后的值,在差分算前缀和时被减了两次,所以我们需要将 \(b_{x1+1,y2+1}+x\)。

下面配上一个图方便理解。(图略丑,勿喷。)

在这里插入图片描述

假设我们要区间加 \((2,2)-(4,4)\),其中黄色表示被 \(c_{x1,x2}\) 影响到的范围,蓝色表示 \(c_{x1,x2}\) 加后多影响到的地方,及 \(b_{x1,y2+1}-x,b_{x2+1,y1}-x\) 影响到的地方,绿色表示被黄色蓝色一起影响,最终被多减了一次,需要加 \(x\) 的区域。

大概就是:

void chafen(int x1,int y1,int x2,int y2,int x)
{
	b[x1][y1]+=x;
	b[x1][y2+1]-=x;
	b[x2+1][y1]-=x;
	b[x1+1][y2+1]+=x;
}

最后还是给一个比较简单的例题吧。P3717 [AHOI2017初中组]cover,虽然可以不用二维差分做,但当一个练习的板子题还是挺好的。

5.树上差分

这是一种非常常考也非常实用的一种差分形式。

我们先给出一种最基本的树上差分形式。即我们现在要完成的是将 \(x-y\) 的路径上的所有节点 \(+x\)。

然后我们给出树上差分的定义,即我们假设第 \(i\) 个点的点权为 \(a_i\),然后我们维护差分数组 \(b\) 表示对于任意节点 \(i\),使得 \(i\) 的所有子节点的 \(b\) 之和(包括他本身)为 \(a_i\)。

然后,我们来处理树上差分。首先,我们可以把 \(x-y\) 的路径看做 \(x-lca(x,y)-y\) 的路径。(\(lca\) 的求法这里不做赘述。)然后,由于我们要将这一段的路径全部加 \(z\)。我们可以发现,当我们对 \(b_x,b_y\) 分别加上 \(z\),就可以满足将 \(x-\) 根节点的路径以及 \(y-\) 根节点的路径全部 \(+z\),但我们发现,不仅 \(fa_{lca(x,y)}-\) 根节点的路径多加了两遍 \(x\),而且 \(lca\) 这个节点被加了两次,但他只能被加一次,所以它也多加了一次。为了将这些效果抵消,我们可以在 \(b_{lca(x,y)}-z\),则对于 \(lca(x,y)-\) 根节点的路径,我们都被抵消了一次 \(z\)。但是,在抵消之后,\(fa_{lca(x,y}-\) 根节点的路径我们仍然多加了一次 \(z\),所以此时,我们需要将 \(b_{fa_{lca(x,y)}}-z\),便可以完美抵消掉了!

核心代码:

void tree(int x,int y,int z)
{
	b[x]+=z,b[y]+=z;
	b[lca(x,y)]-=z;b[fa[lca(x,y)]]-=z;
}

最后再奉上一个比较好想的例题:P6869 [COCI2019-2020#5] Putovanje

6.后记

虽然在维护序列时,我们完全可以用线段树树状数组等一列数据结构来代替差分这种查询较慢的结构,但差分终究还是一个好写好想的算法,是不容易出错的。毕竟,如果考场上你在面临树上路径的操作时,不会树上差分,打一个码量极大还容易错的的树链剖分就太吃亏了。

标签:y2,浅谈,int,差分,lca,x2,x1
From: https://www.cnblogs.com/SFsaltyfish/p/18049175

相关文章

  • 浅谈微服务
    1.为服务落地根基:高可用性服务可用性+伸缩性:集群+负载均衡2.单体架构——>单个分布式架构从自己连数据库获取数据——————>调用WebAPI获取数据点击查看代码stringurl="http://localhost:8080/api/users/all";//808180828083stringconten......
  • 浅谈计算几何
    从目前局势来看,@0616allen要被处刑了呢前置知识:维度:维度是一个非常抽象的东西。在生活中常用的是\(0\)到\(3\)维,其对应如下:\(0\)维:点\(1\)维:线\(2\)维:面\(3\)维:体每一维经过移动可以变成更高维,如点移动变成线,面移动变成体。这不就不怕二向箔了吗向量:向量,顾名......
  • 浅谈EK求网络流 & 最小费用最大流
    1.简介:网络流,指的是一种图上问题。首先我们要知道什么是网络。网络的性质如下:有且仅有一个点入度为0,且只有一个点出度为0,我们把入读为0的点叫做源点,出度为0的点为汇点。网络是一个有向图,且有边权。那么流是什么呢?考虑对于下面这个网络:其中\(s\)是源点,\(t\)......
  • 一维差分/前缀和
    算法笔记的第一篇文章前缀和:在做题时,我们经常会遇见这种问题:给你一个长度为\(n\)的序列\(a\),有\(q\)次询问,每次给出一个区间\(\left[L,R\right]\),请输出\(a_l+a_{l+1}+\cdots+a_r\)的和。对于这种问题,最为简单的方式莫过于\(\operatorname{O}(nq)\)暴力了。......
  • 差分和前缀和
    蓝桥杯第14届中的一道题所学:题目描述小蓝拥有n×n大小的棋盘,一开始棋盘上全都是白子。小蓝进行了m次操作,每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色,黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。输入格式输入的第一行包......
  • 浅谈Nacos
    主要功能和特点服务发现与注册:Nacos允许服务实例动态地注册和发现,当新的服务实例上线或下线时,注册中心能够实时感知并通知其他服务。服务中心原理动态配置管理:Nacos提供了一个集中化的配置管理平台,可以动态地管理和推送应用程序的配置,实现配置的实时更新和回滚。注册中心原......
  • 浅谈WPF之DataGrid动态生成列
    在日常开发中,DataGrid作为二维表格,非常适合数据的展示和统计。通常情况下,一般都有固定的格式和确定的数据列展示,但是在某些特殊情况下,也可能会需要用到动态生成列。本文以一些简单的小例子,简述在WPF开发中,如何动态生成DataGrid的行和列,仅供学习分享使用,如有不足之处,还请指正。 ......
  • 差分约束
    解决形如$a_i\lex_i-y_i\leb_i$的不等式组,其中$a_i,b_i$是给定的常数。我们尝试连接边通过$\operatorname{spfa}$解决。连接以下两条边,跑最短路。$$\Large{x_i\overset{-a_i}{\to}y_i}$$$$\Large{y_i\overset{b_i}{\to}x_i}$$例题:[P7515](https://www.luogu.com.c......
  • ES6中的class浅谈
    在ES6中引入了类(class)的概念,让JavaScript更加接近传统面向对象编程语言。类提供了一种用于创建对象的模板,其中包含了属性和方法的定义。1.定义类使用class关键字可以定义一个类,类名通常以大写字母开头。 1classPerson{234constructor(name,age,work......
  • 浅谈筛法
    浅谈筛法Euler筛Eratosthenes筛可以证明(不是“不难证明”),Eratosthenes筛的复杂度为\(\Theta(n\log\logn)\)。Eratosthenes筛的复杂度证明Dirichlet前缀和以P5495【模板】Dirichlet前缀和为例。给定\(a_1,a_2,\cdots,a_n\),求\(b_1,b_2,\cdots,b_n\),满足\[b_i......