技术标签： 数据结构进阶
树上差分就是说；
其实树上的问题真的和线性的问题是很像的只不过是迭代方式发生了一个变化；
线性的前缀和：前缀和；
线性的差分：差分；
线性的这两个东西的结合：线段树；
在树上就分别是：
开一个数组表示这个节点的子树上的权值之和；
树上差分；
树链剖分；
第一个树上面的前缀和就不讲了，很简单；
来个树上差分；
首先我们要知道树上差分维护的是一条边的值；
倞阶指南上面有两幅图画的好；
每次求边的值的时候会把大半棵树遍历一遍；
在那条边的两个节点上打上+1的标记然后在LCA上打上-2的标记；
int dfs(int u, int father)
{
int res = d[u];
//此处的D就是差分标记的数组；代表的是这个点跟他爸爸相连的边的权值；
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j != father)
{
int s = dfs(j, u);
res += s;
}
}
return res;
}
树链剖分，就是说，一个区间里面，如果既要完成前缀和也要完成差分的功能的话那么就只能用线段树树状数组分块等方法，而在一个树上如果既要完成差分又要完成前缀和那么就应该用树链剖分和线段树；
线段树里面的每个点的u表示的是原来树上的一条边；
现在是主要内容，我们通过两次dfs求出各种前置的必要的信息，然后将对于每个节点，他的子树里面最大的那个就是重儿子，连接他和重儿子以及重儿子的儿子一直到底的那条边叫做重链；
重链的所有长度必然大于等于轻链的长度，这里运用了贪心选择的性质，不然的话我们就可以使用调整法来进行一个替换，然后第二次dfs的时候我们保证每次都先去遍历重儿子，然后第二次dfs遍历出来的顺序就是线段树里面的真实顺序，然后这样子我们就能保证同一条重链一定都是连在一起的，这样子就可以最小化线段树的修改次数不用 O ( N ) O(N) O(N)的modify了，时间复杂度是 O ( n ∗ l o g n ∗ l o g n ) O(n*logn*logn) O(n∗logn∗logn)；
树链剖分的函数主要能分成三个部分，第一个是线段树操作函数，第二个是树链剖分链操作函数，第三个是树链剖分树操作函数；
本质上就是寻找一种方法将树的迭代顺序拆成是一条链，然后就能便于我们去维护各种区间内的值；
例题在acwing上面有；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100010,M=N*2;
int n,m;
int w[N],h[N],e[M],ne[M],idx;
int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N];
struct seg{
int l,r;
ll add,sum;
}tr[N*4]文章浏览阅读320次，点赞5次，收藏4次。IDE是Integrated Development Environment的缩写，即集成开发环境。它是为了方便开发人员进行软件开发而专门设计的应用软件。IDE提供了编辑器、编译器、调试器、自动化工具等多种工具，可以集成由不同的厂商提供的各种工具，成为最佳的开发环境
文章浏览阅读3.3k次。原因：文件名使用了操作系统设备保留字，如com、con、lpt等_filestream 将不会打开 win32 设备(如磁盘分区和磁带机)。请避免在路径中使用“\\
文章浏览阅读4.2w次，点赞167次，收藏2.1k次。为准备第十三届蓝桥杯大赛（软件类）省赛。个人博客www.tothefor.com知识点蓝桥杯JAVA-1.入门必知、正常输入输出和快速输入输出蓝桥杯JAVA-2.数组操作蓝桥杯JAVA-3.自定义类排序、进制转换、保留小数位数蓝桥杯JAVA-4.常用数据类型蓝桥杯JAVA-5.位运算技巧和原理蓝桥杯JAVA-6.大数（整数、小数）处理蓝桥杯JAVA-7.集合（容器）在竞赛中的使用..._蓝桥杯java-知识点汇总复习
文章浏览阅读5k次。有时候我们的电脑连接无线网络不能上网时，可能是因为ip地址获取不到的问题，这个时候可以自己设置无线网络ip地址。下面是学习啦小编整理的电脑设置无线网络ip地址的方法，供您参考。电脑设置无线网络ip地址的方法WIN7电脑点击右小脚网络连接图标，进入网络设置界面，如图2，接着点击无线网络，如果是有线的就点击有线网络。点击底下属性栏目进入下步骤，点击TCP IP 协议则进入设置界面此时大家在这里要注意的..._无线网ip地址怎么设置
文章浏览阅读2.5k次，点赞2次，收藏4次。robo 3T的小bug这个mongodb客户端，每次查询数据只有50行，虽然有向下翻页的功能但实际上点击后会被重置，还是只有前50条解决办法DBQuery.shellBatchSize = 500;当前窗口最大查询数量修改到500（只有当前窗口生效）在查询结束语句后加上.toArray()db.getCollection('example').find({}).toArray()..._robo 3t 只能显示50条数据
文章浏览阅读166次。直接上流程图和之前的博文类似，可参考Android N Data Disconnection For Long Connection转载请注明出处。_default mobile data
文章浏览阅读3.9k次。MySQL如何更改数据库名字_mysql update数据库名称
文章浏览阅读9w次，点赞24次，收藏65次。windows上最好用的文件管理软件 Directory Opuswindows 自带的文件管理软件就不用提了，垃圾的一比。而市面上比较流行的文件管理软件 xyploer，total commander 之类我都使用过，其中 total commander 的确是神器，但是界面太难看，还有学习路径比较陡峭，最后还是放弃了。后来我使用了 windows 上的资源管理器增强软件 clover 感觉..._directory ops
文章浏览阅读212次。1.1AWT容器1.1.1Window和FrameWindow独立存在不依赖于任何其他容器。Window有两个子类：Frame和Dialog。一、窗体Frame：带有标题，而且可以调整大小。1.Frame的构造方法： 1）. Frame() 构造的新实例 Frame初始时不可见。 2）. Frame(GraphicsConfiguration gc) 构造一个新的，最初看不见的 F..._awt容器定义
文章浏览阅读656次，点赞24次，收藏12次。包含最全MySQL、Redis、Java并发编程等等面试题和答案，用于参考~
文章浏览阅读175次。Spring Cloud Alibaba 介绍Sping体系Spring 以 Bean（对象） 为中心，提供 IOC、AOP 等功能。Spring Boot 以 Application（应用） 为中心，提供自动配置、监控等功能。Spring Cloud 以 Service（服务） 为中心，提供服务的注册与发现、服务的调用与负载均衡等功能。Sping Cloud介绍官方介绍 Tools for building common patterns in distributed systems_sprngcloud alba
文章浏览阅读3.2k次，点赞4次，收藏21次。我这里是根据之前在测试数据类项目过程中的一些总结经验和掉过个坑，记录一下，可以给其他人做个参考，没什么高深的东西，但是如果不注意这些细节点，后期也许会陷入无尽的扯皮当中。1 需求实现的准确度根据产品需求文档描述发现不明确不详细的或者存在歧义的地方一定要确认，例如数据表中的一些字段，与开发和产品确认一遍，如有第三方相关的，要和第三方确认，数据类项目需要的是细心，哪怕数据库中的一个字段如果没有提前对清楚，后期再重新补充，会投入更大的精力。2 数据的合理性根据业务场景/常识推理，提..._基础字段的测试点