当前位置: 首页 > news >正文

浅说树上差分——点差分

我们前面也学过差分,现在的话我们就把他放到树上来做。因为这是树,所以会有点和边之分,所以树上差分也会分为 点差分边差分

引入

树上差分其实和线性差分没有什么区别,只不过是放到了树上的两点,而他们之间的最简路径就是可以类比成线性的两点之间的线段。
在这里插入图片描述
所以我们如果要对一条曲线进行操作的话,就是在树上跑差分,那么树上差分数组究竟是什么呢,他又代表着什么意思呢?这是一个值得深思的问题,也是困扰我很久的问题。

树上差分数组本质上存储的是 操纵方式,而不是简单的差值。例如一个点 x x x 的差分数组 p [ x ] = − 3 p[x]=-3 p[x]=3 代表这个点或这个点所对应的边被减去了3,而不是这个点或这个边等于-3,这是一个易错也易混的点。

相同的,对线性差分数组进行求前缀和的话,我们就可以得到真实的答案的值,那么类似的,在 树上差分数组中求子树和,就可以的到这个点的操纵方式,不过为什么要求子树和,而不求其它的,我也不知道,我也不敢问。
在这里插入图片描述

点差分

如果我们现在要对树上的一条路径上的点进行统一操作,比如说 +1 或 -2,我们应该如何完成?
首先是不是很容易想到暴力 dfs ?但是这样的时间复杂度是 O ( n 2 ) \cal O(n^2) O(n2) 的,不优秀。但是我们在学什么,是不是在学差分,那为什么不从差分的视角来考虑考虑?

如果我们要对一条 A → B A \rightarrow B AB 的路径进行+1的修改操作,那么首先我们肯定要在点 A A A B B B 两个位置进行修改对吧,又因为我们最后是通过求子树和来求得每个点的修改方式,所以不能影响 点 A A A 和 点 B B B 所对应的子树,所以我们可以非常明了的得到
p [ A ] + + , p [ B ] + + p[A]++,p[B]++ p[A]++,p[B]++
然后我们的目光不断向上看,发现基本上都没有问题,但是在他们的最近公共祖先那里除了岔子,为什么呢?因为二者是从两端慢慢爬上来的,这就会导致他们的 LCA 会被增加两次,所以我们又可以得到
p [ l c a ( A , B ) ] − − p[lca(A,B)]-- p[lca(A,B)]
我们继续往上看,发现点 A A A 和点 B B B 的最近公共祖先的父亲在计算子树和的时候任然会被增加一次,但是他应该是不能被修改的,所以我们还可以得到
p [ f a ( l c a ( A , B ) ) ] − − p[fa(lca(A,B))]-- p[fa(lca(A,B))]
继续往上看,发现没有问题了,说明我们的操作就成功的完成了!(看不懂的,看下面的图示)
在这里插入图片描述
我们把上述的公式总结一下就是 两个点自己加,他们的lca和lca的爸爸都要减,把它写成代码就是

//dp 为倍增数组,lca为求最近公共祖先的函数
int root=lca(a,b);
p[a]++,p[b]++;
p[root]--,p[dp[root][0]]--;

那么当我们要求所有的答案的时候,也就是要求子树和的时候,我们就可以使用一个时间复杂度为 O ( n ) \cal O(n) O(n) 的 dfs 函数来求解:

//mp为邻接表存储
void get(int x, int fa) {int len = mp[x].size();for (int i = 0; i < len; i++) {if (mp[x][i] == fa) continue;int t = mp[x][i];get(t, x);p[x] += p[t];//差分数组求子树和}
}

看完后是不是感觉非常简单,就只是在树上倍增的基础上对一个数组进行了一点点操作,那么好,我们上实战!

例题1——wwx的出玩

wwx给她的衣柜的有 n 个隔间,隔间编号为1到 n 。她有 k 天要和她的男朋友出去玩,第 i 次玩耍wwx会穿隔间 si 到隔间 ti 的衣服,每次穿这些衣服,都会给它们带来一个单位的损坏,你作为她的男朋友,请计算损坏程度最大的衣服的损坏程度是多少。

分析与解答

不难发现,这道题就是一道裸的点差分问题,所以我们直接套模板,顺便也把模板给你了。

#include<bits/stdc++.h>
using namespace std;
const int INF=1e5;
vector<int> mp[INF];
int ans,dp[INF][20],deep[INF],num[INF];//num为差分数组void prepare(int x,int fa){for (int j=1;(1<<j)<=deep[x]-1;j++){dp[x][j]=dp[dp[x][j-1]][j-1];} int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];deep[t]=deep[x]+1,dp[t][0]=x;prepare(t,x); }
}int lca(int x,int y){if (deep[x]<deep[y])swap(x,y);int index=__lg(deep[x]-deep[y]);for (int i=index;i>=0;i--){if (deep[dp[x][i]]>=deep[y])x=dp[x][i];if (deep[x]==deep[y])break;}if (x==y)return x;for (int i=18;i>=0;i--){if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];}return dp[x][0];
}void get(int x,int fa){int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];get(t,x);num[x]+=num[t];}ans=max(ans,num[x]);//求得最大值
}
int main(){int n,k;cin>>n>>k;for (int i=1;i<n;i++){int u,v;cin>>u>>v;mp[u].push_back(v);mp[v].push_back(u);} deep[1]=1;prepare(1,-1);for (int i=1;i<=k;i++){int s,t;cin>>s>>t;int root=lca(s,t);num[s]++,num[t]++,num[root]--,num[dp[root][0]]--;}get(1,-1);cout<<ans;return 0;
}

例题2——松鼠的新家

题目传送门

分析与解答

这道题其实也是裸题,我们稍微分析一下就知道它的那个参观路线是可以被分成多个区间修改的,但是这样的话,他们的端点的位置,会被重复计算,所以要特判

#include<bits/stdc++.h>
using namespace std;
const int INF=3e5+10;
vector<int> mp[INF];
int ans,dp[INF][20],deep[INF];
int a[INF],num[INF];void prepare(int x,int fa){for (int j=1;(1<<j)<=deep[x]-1;j++){dp[x][j]=dp[dp[x][j-1]][j-1];} int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];deep[t]=deep[x]+1,dp[t][0]=x;prepare(t,x); }
}int lca(int x,int y){if (deep[x]<deep[y])swap(x,y);int index=__lg(deep[x]-deep[y]);for (int i=index;i>=0;i--){if (deep[dp[x][i]]>=deep[y])x=dp[x][i];if (deep[x]==deep[y])break;}if (x==y)return x;for (int i=18;i>=0;i--){if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];}return dp[x][0];
}void get(int x,int fa){int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];get(t,x);num[x]+=num[t];}ans=max(ans,num[x]);
}
int main(){int n;cin>>n;for (int i=1;i<=n;i++){scanf("%d",&a[i]);}for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);mp[u].push_back(v);mp[v].push_back(u);} deep[1]=1;prepare(1,-1);for (int i=1;i<n;i++){int s=a[i],t=a[i+1];int root=lca(s,t);num[s]++,num[t]++,num[root]--,num[dp[root][0]]--;}get(1,-1);for (int i=2;i<=n;i++){num[a[i]]--;}for (int i=1;i<=n;i++){printf("%d\n",num[i]);}return 0;
}

相关文章:

浅说树上差分——点差分

我们前面也学过差分&#xff0c;现在的话我们就把他放到树上来做。因为这是树&#xff0c;所以会有点和边之分&#xff0c;所以树上差分也会分为 点差分 和 边差分 。 引入 树上差分其实和线性差分没有什么区别&#xff0c;只不过是放到了树上的两点&#xff0c;而他们之间的…...

All in大模型!智能座舱语音交互决胜2025

大模型加速上车&#xff0c;AI智能座舱竞争更显白热化。 诚然&#xff0c;在语言大模型为核心的多模态能力加持下&#xff0c;智能语音助理能够理解复杂的语言指令&#xff0c;实现知识问答、文本生成等&#xff0c;以及根据上下文进行逻辑推理&#xff0c;提供更智能、准确的…...

windows git bash 使用zsh 并集成 oh my zsh

参考了 这篇文章 进行配置&#xff0c;记录了自己的踩坑过程&#xff0c;并增加了 zsh-autosuggestions 插件的集成。 主要步骤&#xff1a; 1. git bash 这个就不说了&#xff0c;自己去网上下&#xff0c;windows 使用git时候 命令行基本都有它。 主要也是用它不方便&…...

Git进阶笔记系列(01)Git核心架构原理 | 常用命令实战集合

读书笔记&#xff1a;卓越强迫症强大恐惧症&#xff0c;在亲子家庭、职场关系里尤其是纵向关系模型里&#xff0c;这两种状态很容易无缝衔接。尤其父母对子女、领导对下属&#xff0c;都有望子成龙、强将无弱兵的期望&#xff0c;然而在你的面前&#xff0c;他们才是永远强大的…...

IDEA导入Maven工程不识别pom.xml

0 现象 把阿里 sentinel 项目下载本地后&#xff0c;IDEA 中却没显示 maven 工具栏。 1 右键Maven Projects 点击IDEA右侧边栏的Maven Projects&#xff0c;再点击&#xff1a; 在出现的选择框中选择指定的未被识别的pom.xml即可&#xff1a; 2 Add as maven project 右键p…...

AT8870单通道直流电机驱动芯片

AT8870单通道直流电机驱动芯片 典型应用原理图 描述 AT8870是一款刷式直流电机驱动器&#xff0c;适用于打印机、电器、工业设备以及其他小型机器。两个逻辑输入控制H桥驱动器&#xff0c;该驱动器由四个N-MOS组成&#xff0c;能够以高达3.6A的峰值电流双向控制电机。利用电流…...

计算机视觉算法实战——实体物体跟踪

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​​​​​ ​ 1. 领域介绍✨✨ 实体物体跟踪&#xff08;Object Tracking&#xff09;是计算机视觉领域中的一个重要研究方向&#x…...

网络协议如何确保数据的安全传输?

网络协议作为计算机网络通信的基石&#xff0c;其设计不仅旨在实现数据的有效传输&#xff0c;更在于确保数据在传输过程中的安全性。对于网络协议如何保障数据安全传输&#xff0c;是很多企业和网络IT部门的重点&#xff0c;本文将从多方面概述相关方法。 加密与解密机制 1. …...

在elasticsearch中,document数据的写入流程如何?

本文将为您介绍文档内容是如何写入ES集群中。 数据写入ES集群的流程图如下 流程介绍 用户携带数据发起POST请求指向集群9200端口。9200端口将数据写入请求发给主分片。主分片会对数据进行分片计算分发给具体分片。&#xff08;计算方式&#xff1a;hash % primary_number_sha…...

【优选算法】6----查找总价格为目标值的两个商品

这道题相对于前寄到算法题较为容易~ 同样也是使用了双指针的算法哦~ ----------------------------------------begin-------------------------------------- 题目解析&#xff1a; 题目也是很简单地一句话&#xff0c;但是意图还是很明确~ 讲解算法原理&#xff1a; 同样的&…...

99.8 金融难点通俗解释:净资产收益率(ROE)

目录 0. 承前1. 简述2. 比喻&#xff1a;养母鸡赚钱2.1 第一步&#xff1a;投资母鸡2.2 第二步&#xff1a;母鸡下蛋2.3 第三步&#xff1a;计算赚钱2.4 第四步&#xff1a;计算ROE 3. 生活中的例子3.1 好的ROE3.2 一般的ROE3.3 差的ROE 4. 小朋友要注意4.1 ROE高不一定好4.2 R…...

Java设计模式—观察者模式

观察者模式 目录 观察者模式1、什么是观察者模式&#xff1f;2、观察者模式优缺点及注意事项&#xff1f;3、观察者模式实现&#xff1f;4、手写线程安全的观察者模式&#xff1f; 1、什么是观察者模式&#xff1f; - 实例&#xff1a;现实生活中很多事物都是依赖存在的&#x…...

人工智能在数字化转型中的角色:从数据分析到智能决策

引言 在数字化转型浪潮中&#xff0c;人工智能&#xff08;AI&#xff09;正迅速崛起&#xff0c;成为推动企业创新和变革的关键力量。面对日益复杂的市场环境和激烈的行业竞争&#xff0c;企业亟需借助技术手段提高运营效率、优化决策过程&#xff0c;并增强市场竞争力。而AI…...

论文阅读 Multi-view Classification Using Hybrid Fusion and Mutual Distillation

Multi-view Classification Using Hybrid Fusion and Mutual Distillation Intro 多视角问题可以分为两类&#xff1a; Structured。固定视角&#xff0c;或预先定义的视角的问题。unstructured。 本文的三大contributions&#xff1a; 引入了混合的多视角融合策略。使用了…...

AIGC浪潮下,图文内容社区数据指标体系如何构建?

文章目录 01 案例&#xff1a;以图文内容社区为例实践数据指标体构建02 4个步骤实现数据指标体系构建1. 明确业务目标&#xff0c;梳理北极星指标2. 梳理业务流程&#xff0c;明确过程指标3. 指标下钻分级&#xff0c;构建多层级数据指标体系4. 添加分析维度&#xff0c;构建完…...

”彩色的验证码,使用pytesseract识别出来的验证码内容一直是空“的解决办法

问题&#xff1a;彩色的验证码&#xff0c;使用pytesseract识别出来的验证码内容一直是空字符串 原因&#xff1a;pytesseract只识别黑色部分的内容 解决办法&#xff1a;先把彩色图片精确转换成黑白图片。再将黑白图片进行反相&#xff0c;将验证码部分的内容变成黑色&#…...

前端Vue2项目使用md编辑器

项目中有一个需求&#xff0c;要在前端给用户展示内容&#xff0c;内容有 AI 生成的&#xff0c;返回来的是 md 格式&#xff0c;所以需要给用户展示 md 格式&#xff0c;并且管理端也可以编辑这个 md 格式的文档。 使用组件库 v-md-editor。 https://code-farmer-i.github.i…...

OpenVela 架构剖析:从内核到应用

目录 一、总体架构概述 二、 内核层 2.1. OpenVela架构的内核基础 2.2. 内核层的主要职责 2.3. OpenVela对NuttX的扩展与优化 三、系统服务层 2.1. 进程管理 2.2. 内存管理 2.3. 文件系统 2.4. 网络通信 四、框架层 4.1. 模块化设计 4.2. API接口 4.3. 组件和服务…...

vue视频流播放,支持多种视频格式,如rmvb、mkv

先将视频转码为ts ffmpeg -i C:\test\3.rmvb -codec: copy -start_number 0 -hls_time 10 -hls_list_size 0 -f hls C:\test\a\output.m3u8 后端配置接口 import org.springframework.core.io.Resource; import org.springframework.core.io.UrlResource; import org.spring…...

记一个Timestamp时区问题的坑

resultSet.getTimestamp(“kpi_collect_time”)查出来的Timestamp居然是带时区的&#xff0c; 如果该Timestamp不是UTC时区的&#xff0c;Timestamp.toInstant().atZone(ZoneId.of(“UTC”))会把Timestamp转成UTC时区 使用Timestamp.toLocalDateTime()可以直接把时区信息抹除 …...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...