当前位置: 首页 > 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()可以直接把时区信息抹除 …...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...