我们接着昨天的讲。懒标记是线段树中一个十分重要的知识点，在线段树中进行区间修改时，暴力的做法是递归到叶子结点修改信息，复杂度达到了O(n) ，不过我们可以将这些修改操作攒起来，到了合适的时候一起修改，这就是懒标记。
对于线段树上的每一个结点，引入一个标记，记录这个结点对应的区间需要加但还未加的值，等到这个结点的 sum 需要被查询的时候，再加上去。懒标记的一个重要部分就是懒标记的下传。因为线段树的结点是从下往上更新的，然而 Lazytag 是从上往下更新，所以我们将原线段树的更新操作定义为 pushup() 函数， 将 lazytag 的更新定义为pushdown() 函数：
void push_up(ll rt)
{// 将下层数据向上更新
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int l,int r,int rt)
{// 将当前标记下传
int mid=(l+r)>>1;
sum[rt<<1]+=(mid-l+1)*add[rt],sum[rt<<1|1]+=(r-mid)*add[rt];// 更新左右子的 sum
add[rt<<1]+=add[rt],add[rt<<1|1]+=add[rt];// 更新左右子的标记
add[rt]=0;// 当前标记清零
}
每次，在调用或经过这个结点的时候，首先 pushdown 以更新这个结点的数据确保准确，并保证在下层结点修改的时候，是在准确数据的基础上修改；也就是说，在更新当前结点（比如区间加的时候），要保证它的祖先路径上的结点的 lazytag 全部下传清零。对于下层的子结点作修改之后，要在递归结尾 pushup 来把数据更新回来。因为不需要递归更新（只需要随着路径调用 pushdown），所以复杂度降至 O(log2n)。
讲完了线段树的区间查询操作和懒标记，我们再来简单看一下线段树的区间加操作和区间乘操作。加法和乘法的优先级不同。因此简单的两个同级 lazytag 并不能正确维护线段树。所以我们要分别考虑两个 lazytag： add 和 mul 。区间加法时，直接更新 add 标记和区间和即可；区间乘法更新时，不仅我们要更新当前区间和，还要根据乘法分配律更新当前区间的 add标记，即为(sum × mul + add) × v = sum × mul × v + add × v
接下来我们看一下两个线段树的模板题，具体的思路翻翻前面的内容就都会了，我就不讲了，直接上代码吧：洛谷P3372 【模板】 线段树1 洛谷P3373 【模板】线段树2
//P3372
#include <iostream> #include <cstdio> #include <iomanip> #include <algorithm> #include <cmath> #define RE register #define N 100010 #define INF 0x3f3f3f3f using namespace std; int a[N]; int n,m; struct tree { int l,r; long long pre,add; }t[4*N]; void build(int p,int l,int r) { t[p].l=l,t[p].r=r; if(l==r) { t[p].pre=a[l]; return ; } int mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); t[p].pre=t[p*2].pre+t[p*2+1].pre; } void spread(int p) { if(t[p].add) { t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1); t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1); t[p*2].add+=t[p].add; t[p*2+1].add+=t[p].add; t[p].add=0; } } void change(int p,int x,int y,int z) { if(x<=t[p].l&&y>=t[p].r) { t[p].pre+=(long long) z*(t[p].r-t[p].l+1); t[p].add+=z; return ; } spread(p); int mid=(t[p].l+t[p].r)>>1; if(x<=mid) change(p*2,x,y,z); if(y>mid) change(p*2+1,x,y,z); t[p].pre=t[p*2].pre+t[p*2+1].pre; } long long ask(int p,int x,int y) { if(x<=t[p].l&&y>=t[p].r) return t[p].pre; spread(p); int mid=(t[p].l+t[p].r)>>1; long long ans=0; if(x<=mid) ans+=ask(p*2,x,y); if(y>mid) ans+=ask(p*2+1,x,y); return ans; } int q,x,y,z; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); for(int i=1;i<=m;i++) { cin>>q; if(q==1) { cin>>x>>y>>z; change(1,x,y,z); } else { cin>>x>>y; cout<<ask(1,x,y)<<'/n'; } } return 0; }
//P3373
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define RE register
#define N 100010
#define ll long long
using namespace std;
int n,m,MOD;
int a[N];
struct tree
{
ll pre,add,mul;
int l,r;
}t[N*4];
void update(int p)
{
t[p].pre=(t[p<<1].pre+t[p<<1|1].pre)%MOD;
}
void pushdown(int p)
{
t[p<<1].pre=(t[p<<1].pre*t[p].mul+t[p].add*(t[p<<1].r-t[p<<1].l+1))%MOD;
t[p<<1|1].pre=(t[p<<1|1].pre*t[p].mul+t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1))%MOD;
t[p<<1].mul=(t[p<<1].mul*t[p].mul)%MOD;
t[p<<1|1].mul=(t[p<<1|1].mul*t[p].mul)%MOD;
t[p<<1].add=(t[p<<1].add*t[p].mul+t[p].add)%MOD;
t[p<<1|1].add=(t[p<<1|1].add*t[p].mul+t[p].add)%MOD;
t[p].add=0;
t[p].mul=1;
}
void build(int p,int l,int r)
{
t[p].l=l;t[p].r=r;t[p].mul=1;
if(l==r)
{
t[p].pre=a[l]%MOD;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
}
void changem(int p,int x,int y,int k)
{
if(x<=t[p].l&&t[p].r<=y)
{
t[p].add=(t[p].add*k)%MOD;
t[p].mul=(t[p].mul*k)%MOD;
t[p].pre=(t[p].pre*k)%MOD;
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) changem(p<<1,x,y,k);
if(y>mid) changem(p<<1|1,x,y,k);
update(p);
return;
}
void changea(int p,int x,int y,int k)
{
if(x<=t[p].l&&t[p].r<=y)
{
t[p].add=(t[p].add+k)%MOD;
t[p].pre=(t[p].pre+k*(t[p].r-t[p].l+1))%MOD;
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) changea(p<<1,x,y,k);
if(y>mid) changea(p<<1|1,x,y,k);
update(p);
return;
}
ll ask(int p,int x,int y)
{
if(x<=t[p].l&&t[p].r<=y)
return t[p].pre;
pushdown(p);
ll ans=0;
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) ans=(ans+ask(p<<1,x,y))%MOD;
if(y>mid) ans=(ans+ask(p<<1|1,x,y))%MOD;
return ans;
}
int q,x,y,k;
int main()
{
cin>>n>>m>>MOD;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++)
{
cin>>q>>x>>y;
if(q==1)
{
cin>>k;
changem(1,x,y,k);
}
if(q==2)
{
cin>>k;
changea(1,x,y,k);
}
if(q==3)
cout<<ask(1,x,y)<<'/n';
}
return 0;
}
线段树其实也就那么回事，背一背就背下来了，关键还是得多做题，多巩固，否则学了等于没学。老师上课例题多的是，我会挑几道有代表性的来讲解，剩下的大家回家可以自行练习：
洛谷P2023 维护序列
● 实现一个数据结构，支持：
● 区间加
● 区间乘
● 区间求和
算法分析
● 我们需要同时维护两个懒标记。
● 这时候需要注意两个懒标记之间的影响。也就是在区间乘的时候，不光需要修改维护的和，还需要修改区间加的懒标记。
● 懒标记下放的时候要注意，先下放乘再下放加。
核心代码：
void push_down(int x,int l,int r)
{
int v=tree[x].mul,tree[x].mul=1;
tree[lc].mul*=v,tree[rc].mul*=v;
tree[lc].add*=v,tree[rc].add*=v;
tree[lc].sum*=v,tree[rc].sum*=v;
v=tree[x].add,tree[x].add=0;
tree[lc].add+=v,tree[rc].add+=v;
tree[lc].sum+=v*(mid-l+1);
tree[rc].sum+=v*(r-mid);
}
洛谷P1438 无聊的数列
● 实现一个数据结构，支持：
● 区间加等差数列
● 区间求和
● 1 ≤ n, q ≤105
算法分析：
● 维护懒标记的时候维护两个信息：首项和公差。
● 加等差数列对区间和带来的影响可以直接计算，下放懒标记的时候 也可以直接计算。
● 还可以用线段树维护一个原数列的差分数列
● [l,r]加一个k为首项，d为公差的等差数列的操作就可以分为：
● 将a[l]加上k
● 将a[l+1..r]加上d
● 将a[r+1]减去(r-l)*d+k
● 求x项的值就是区间[1,x]求和
poj 2828 线段树上二分 ● 有 n 个人来排队，第 i 个人来的时候会排在 p[i] (0<=p[i]<=i) 个人后面，同时它会被分配一个数字 v[i]。 ● 现在告诉你 n 对（p[i], v[i]）, 最后按照队伍顺序输出每个人的数字。 ● n<=2e5 【样例输入】 4 0 77 1 51 1 33 2 69 【样例输出】 77 33 69 51 算法分析： ● 考虑模拟做法，数组和指针维护都是O（n^2）。 ● 正难则反。倒着考虑每个人，就可以确定每个人的位置。 ● 比如第 n 个人，一定在 p[n]+1 位置上。 ● 然后考虑如何放第 n-1 个人的位置。 ● 如果 p[n-1]+1 < p[n]+1, 也就是说第 n-1 个人的位置没有因为第 n 个人的进入而改变，因此可以放在 p[n-1]+1 处。 ● 如果 p[n-1]+1 >= p[n]+1, 也就是说第 n-1 个人在第 n 个人进入后向后移了一位，因此第 n-1 个人的位置应在 p[n-1]+2 处。 ● 可以总结为第 n-1 个人的位置在除了第 n 个人的位置外的第 p[n-1]+1 处。 ● 接着考虑第 n-2 个人的位置，可以分析得应该在除了第 n 个人和第 n-1 个人外的 p[n-2]+1 处。 ● 因此我们发现，我们如果只考虑相对位置，这个问题是个规模逐渐减小的递归问题。 ● 问题规模为 n 时，确定第 n 个人的位置，删除这个位置后，问题变成 n-1规模的同样的问题，与n 无关。只是在最后输出需要考虑绝对位置，留出n 所在的空位。 ● 于是问题就变成了： 一开始有 n 个位置，每次查询第 p[i]+1 个空位置，然后将该位置变成非空。 ● 一个简单的想法就是用线段树维护一个全 1 的数组 a。 ● 查找第 x 个空位置就是找一个下标 i 使得 a[1…i] 的前缀和等于 x。 ● 由于 a 是单增的，所以我们可以二分下标 i。 ● 用线段树维护区间和，每次二分时查询即可。 ● 时间复杂度为 O(n logn logn) ● 注意：线段树本身就有分治的性质。 ● 使用分治套分治时我们要思考能否减少冗余计算，只使用一层分 治解决问题。 ● 于是我们可以直接在线段树上二分。
剩下的题目大家可以自己练习使用：洛谷P1471 方差、线段树离线查询（https://acm.hdu.edu.cn/showproblem.php?pid=3333）
接下来我们来讲一下可持久化线段树。可持久化线段树又被称为主席树。可持久化是指更新的同时保留了历史版本，可以获得所有的历史版本。本质上是多颗线段树，不过这些线段树共同使用了一部分枝干。可持久化线段树和线段树的实现有很大差别。线段树的left和right表示区间的左右边界，而可持久化线段树的left和right 表示该节点的左右儿子。每更新一次，新建log(n)条边。
洛谷P3834 区间第k小 ● 长度为 n 的数组，每次查询一段区间里第 k 小的数。 ● 1 ≤ n, q ≤105 ● 我们先考虑一个比较简单的问题：如何维护全局第 k 小？ ● 可以建一棵权值线段树，维护一列数中数的个数，然后在线段树上二分 解决。 ● 维护前缀第 k 小？ ● 把这个权值线段树可持久化，这样我们就可以随时拎出来一个前缀。 ● 区间第 k 小？ ● 相当于两个线段树相减，同样可以用可持久化线段树维护。 ● 时间复杂度 O(nlogn)。 ●假设数列1 2 4 3 2 1 4，求区间 [4,7] 的第 3 小。 ●用 i=7 时的线段树减去 i=3 时的线段树，具体方法是对应节点的权值相减。（如下图）
然后我们再来看一下可持久化线段树单点加的算法：
int add(int pre,int o,int l,int r,int p,int v)
{
if(l==r)
{
tree[o].sum=tree[pre].sum+v;
return 0;
}
if(p<=mid)
{
rson=tree[pre].child[1];
tot++;
lson=add(tree[pre].child[0],tot,l,mid,p,v);
}
else
{
lson=tree[pre].child[0];
tot++;
rson=add(tree[pre].child[1],tot,mid+1,r,p,v);
}
push_up(o);
return o;
}
其实，我们也可以通过可持久化线段树来构造出一个可持久化并查集，不过平常用不大到，大家理解原理即可。
● 实现一个可持久化并查集，不光要支持所有并查集的操作， 还需要支持访问历史版本。 ● 1 ≤ n, 1 ≤105 ● 首先科普一个关于并查集的知识点： ● 按秩合并 + 路径压缩：O(α(n))（反阿克曼函数） ● 只用按秩合并或只用路径压缩：O(log n) ● 在某些情况下，我们只能用按秩合并不能用路径压缩，比如可持久化。
● 用可持久化线段树，我们可以实现数组的可持久化。也就是维护一个数组，支持单点修改数组元素和访问历史版本。
● 并查集，其实无非是维护 fa 和按秩合并所需的 dep，将这两个数组都可持久化，我们就可以实现并查集的可持久化。
● 不能路径压缩，因为那样的话 fa 会进行很多修改。
● 时间复杂度 O(n log2 n)，两个 log n 一个来自按秩合并并查集，一个来自可持久化线段树。
最后，可持久化线段树的模板题和代码供大家参考：
可持久化线段树模板题：洛谷P3919
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+50;
int n,m,len,a[N],b[N],tmp,pre[N],rt[N],tot;
map<int,int> mp;
struct segtree
{
int ls,rs,val;
}tree[N<<4];
inline int read()
{
int val=0,f=1;
char ch=0;
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
val=(val<<1)+(val<<3)+(ch^48);
ch=getchar();
}
return val*f;
}
int clone(int x)
{
tot++;
tree[tot]=tree[x];
return tot;
}
void pushup(int x)
{
tree[x].val=tree[tree[x].ls].val+tree[tree[x].rs].val;
}
int build(int t,int l,int r)
{
t=++tot;
if(l==r)
{
tree[t].val=a[l];
return t;
}
int mid=(l+r)>>1;
tree[t].ls=build(tree[t].ls,l,mid);
tree[t].rs=build(tree[t].rs,mid+1,r);
return t;
}
int update(int x,int l,int r,int pos,int c)
{
x=clone(x);
if(l==r)
{
tree[x].val=c;
return x;
}
int mid=(l+r)>>1;
if(pos<=mid) tree[x].ls=update(tree[x].ls,l,mid,pos,c);
else tree[x].rs=update(tree[x].rs,mid+1,r,pos,c);
return x;
}
int query(int x,int l,int r,int pos)
{
if(l==r) return tree[x].val;
int mid=(l+r)>>1;
if(pos<=mid) return query(tree[x].ls,l,mid,pos);
return query(tree[x].rs,mid+1,r,pos);
}
int main(void)
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
rt[0]=build(0,1,n);
for(int i=1;i<=m;i++)
{
int xxj=read(),op=read(),x=read();
if(op==1)
{
int y=read();
rt[i]=update(rt[xxj],1,n,x,y);
}
else
{
printf("%d/n",query(rt[xxj],1,n,x));
rt[i]=rt[xxj];
}
}
return 0;
}
然后，我们来看一下下一个知识点：树状数组。
树状数组是什么？就是用数组来模拟树形结构。设序列为A[1]~A[8]，树状数组为C。下图中有一棵满二叉树，满二叉树的每一个叶子结点对应A[]中的一个元素。
树状数组都有什么用呢？树状数组可以解决大部分基于区间上的更新以及求和的问题，时间复杂度为O(logn)。通俗的讲，树状数组可以动态维护一个序列，并且支持单点修改、查询前缀和的操作，而且树状数组可以解决的问题都可以用线段树解决，但是树状数组并不能解决一些复杂的区间问题。
树状数组上的结点更新 ● 更新a[i]影响哪些位置呢？a[i]包含于C[i]、C[i+2
k1
]、C[(i+2
k1
)+2
k2
]……
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int value)
{
while(i<=n)
{
c[i]+=value;
i+=lowbit(i);
}
}
树状数组中查询前缀和的操作我们可以用一个名为SUM的数组来进行存储，前缀和SUM[i] = C[i]+C[i-2k1]+C[(i-2k1)-2k2] + …..，如：SUM[7]=C[7]+C[6]+C[4]
int getsum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
然后我们再来看一下树状数组的构建方法，其中，最简单的方法就是把每个数据都依次插入到树状数组中，这样的话时间复杂度为O(nlogn)
for(int i=1;i<=n;i++)
{
cin>>a[i];
update(i,a[i]);
}
树状数组在信息可减的情况下，可以进行各种差分：比如单点加，区间查询；区间加，单点查询；区间加，区间查询等。
先来看一下单点加，区间查询。在查询区间[l,r]的时候，差分为前r个数的和减去前i-1个数的和，用代码表示便为：getsum(r)-getsum(l-1)。而区间加，单点查询则是指，利用差分进行建树，D[i]=A[i]-A[i-1]，规定A[0]=0；接着，把区间[l,r]中的每个数加k，差分则为D[i]加k，D[r+1]减k，而查询单点的时候只需要查询对应这个点的前缀和即可。最后的区间加，区间查询则是维护原数组的差分数组D[i]=A[i]-A[i-1]，于是A[i]=∑ij=1，前缀和∑ni=1A[i]=n*∑ni=1D[i]-∑ni=1（D[i]*(i-1)），而且需要维护两个树状数组，sum1[i]=D[i]，sum2[i]=D[i]*(i-1)。其实在一维树状数组的基础上我们也可以推导出二维的树状数组，即单点修改，矩形求和，直接多一层for循环即可，因为树状数组自带完美的差分。
上例题：
逆序对： ● 给出一个序列，求逆序对个数 ● 逆序对即i < j且a[i] > a[j]的对 算法分析： ● 按值域开树状树组？如果数值非常大，直接开数组显然是不行了，这时的解决办法就是离散化。 ● 按数值由大到小排序，这样得到的下标值即是离散化结果，等效于原序列的数值。把这些下标值当成原序列，按照树状数组求逆 序对的原理做。 ● 每次把这个数的位置加入到树状数组中，因为是排完序之后，所以之前加入的一定比后加入的大，然后再查询当前这个数前面的 位置。
然后我们再来看一下倍增算法求LCA。倍增算法我们之前也提到过，不过只说了运用倍增思想的一个ST算法，并没有将倍增思想去展开，今天我们将围绕LCA展开倍增算法的求解过程。
要求LCA，首先我们需要了解树的存储。一般来说，一棵树在程序里都是用邻接表来存储的，常见的实现方式大体有两种：第一，使用C++标准模板库（STL）中的vector（容器）来进行存储，这个知识点我们在之前也详细讲到过；第二，把邻接表使用多个数组来模拟的（一般是head，to，nxt三个数组，即所谓的“链式前向星”）。
了解完了树，我们再来看看LCA究竟是什么。LCA（
Lowest/Least Common Ancestors
）是指两个点的最近公共祖先。通常有四种快速求LCA的办法：tarjan求LCA、RMQ、树上倍增、树剖（树链剖分），今天我们主要来讲第三种——树上倍增。
举个栗子，如果要求下图中的点4和点5的LCA（最近公共祖先），最粗暴的方法就是先dfs一次，处理出每个点的深度，然后把深度更深的那一个点（4）一个点一个点地往上跳，直到到某个点（3）和另外那个点（5）的深度一样。然后两个点一起一个点一个点地往上跳，直到到某个点（就是最近公共祖先）两个点“变”成了一个点。
接下来我们看一下倍增方法的思路：
● 倍增的话就是一次跳2^i 个点。 ● 我们先预处理up[x][i]表示从x往上跳2^i步后会到哪里，以及每个点的深度。 预处理复杂度O(nlog2n) ● 如何查询呢？ ● 分两步走： ● 将u和v移动到同样的深度。 ● u和v同时向上移动，直到重合。第一个重合的点即为LCA。 ● 移动到同样深度 ● 令u为深度较大的点。我们从log2n到0枚举，令枚举的数字为j。如果从 u向上跳2^j步小于了v的深度，不动；否则向上跳2^j步。这样一定能移动到和v同样的深度。 ● 假设一共要跳k步，上面的算法相当于是枚举k的每个二进制位是0还是1。 ● 从同样的深度移动到同一个点 ● 和上一步类似。很快就会发现一个很严重的问题：两个点按照这样跳，不能保证一定是最近 的。 ● 从log2n到0枚举，令枚举的数字为j。如果两 个点向上跳2^j将要重合，不动；否则向上跳 2^j步。 ● 通过这种方法，u和v一定能够到达这样一种 状态——它们当前不重合，如果再往上跳一 步，就会重合。所以再往上跳一步得到的就 是LCA。 ● 我们注意到，在整个倍增查找LCA的过程中，从u到v的整条路径都被扫描 了一遍。如果我们在倍增数组f[i][j]中再记录一些别的信息，就可以实现树路径信息的维护和查询。
这就是倍增求LCA的具体思路，时间原因（作者太困了），这里的练习题就留给大家回家做了。
对了，把你们日思夜想的模板代码先放上，但是复制达咩！！
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define RFOR(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
inline int read()
{
int x=0,y=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*y;
}
int next[10000],head[2000],to[2000],in_num[2000];
int tot,n,m;
int dep[1000],f[1000][21];
void add_edge(int u,int v){
next[++tot]=head[u],head[u]=tot,to[tot]=v;
next[++tot]=head[v],head[v]=tot,to[tot]=u;
}
void pre(int u,int fa){
dep[u]=dep[fa]+1;
for(int i=0;i<=19;i++){
f[u][i+1]=f[f[u][i]][i];
}
for(int i=head[u];i;i=next[i]){
int v=to[i];
if(v==fa) continue;
f[v][0]=u;
pre(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--){
if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y) return y;
}
for(int i=20;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int dis(int x,int y){
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int main(){
int x,y;
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++)
{
scanf("%d%d",&x,&y);
add_edge(x,y);
in_num[y]++;
}
int root;
for(int i = 1;i <= n;i ++)
if(in_num[i] == 0)
root = i;
pre(root,0);
return 0;
}
LCA模板题：洛谷P3379 求树上两个点的距离
接下来我们进入今天的倒数第三个算法——树上差分。众所周知，差分是前缀和的逆运算，所以我们先简单说一下在树上的前缀和。从根向下到某点的前缀和指的是从根到该点的路径上点（或者边，根据题目要求来定）的权值之和。
而树上差分即为树上前缀和的逆运算：
树上差分的定义是某个结点对它到根结点的路径上的每个点的贡献，并且分为点差分和边差分。点差分是点带权值的树，边差分也同理。其中某个结点的权值即为它子树所有结点的差分之和。
我们先来看点差分：
● 有n次修改操作，每次把u..v的所有点权都加x，最后问点权最大的为多少。 ● diff[u]+=x,diff[v]+=x,diff[lca(u,v)]-=x,diff[fa(lca)]-=x;
然后是边差分：
● 给你一棵树，有n次修改操作，每次把u..v的路径权值加x，最后问从ux..uy的路径权值和。 ● diff[u]+=x,diff[v]+=x,diff[lca(u,v)]-=2*x;
LCA+点差分模板题：洛谷P3128 【USACO15DEC】Max Flow P
不知不觉，来到了今天的倒数第二个算法（北京时间2022年7月27日22:50）：树链剖分。树链剖分其实就是将“树”分割成多条“链”，然后利用数据结构来维护这些“链”（本质上其实是一种优化后的暴力）。关于树链剖分其实有很多种，今天老师在课堂上主要讲解了两种：重链剖分和长链剖分。其实作者自我感觉剖分的难点关键在于代码部分，理论知识很好理解，代码才是重点，所以请大家在学习剖分的时候以代码为主，理论为辅。
话不多说，我们先来到重链剖分。何为重链剖分？在揭开谜底之前，大家需要先了解一些概念：
● 重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点。
● 轻儿子：父亲节点中除了重儿子以外的儿子。 ● 重边：父亲结点和重儿子连成的边。 ● 轻边：父亲节点和轻儿子连成的边。 ● 重链：由多条重边连接而成的路径。 ● 轻链：由多条轻边连接而成的路径。
接下来，我们来看一下重链剖分的思想：
● 首先，对每个点求出其大小sz、深度d、父节点fa以及大小最大的儿子son，然后son[x]称为x的重儿子，其余的叫轻儿子。 ● 接着，每个点和其重儿子（如果有的话）中间的边涂黑，称为重边，有公共点的重边形成链，这些链就形成了一个树剖。和轻儿子连接的边叫轻边。特殊的，如果一个点不是其父节点的儿子且这个这个点是叶子节点，那么这个点单独是一条链。 ● 最后，维护出每个点的链顶。
光说是不管用的，关键得进行实际的操作才能明白重链剖分的含义，先举个栗子：
● 黑色节点是重儿子，其余节点是轻儿子。 ● 红边是重边，黑边是轻边。 ● 叶节点没有重儿子，非叶节点有且只有1 个重儿子。 ● 并不是轻儿子之后全是轻儿子，比如2后面就有6和11两个重儿子。 ● 可以这样理解：当一个节点选了重儿子之后，并不能保证它的轻儿子就是叶节点，所以就以这个轻儿子为根，再去选这个轻儿子的轻重儿子。
接下来我们来看一下重链剖分的性质：
● 任意一个点到根的路径上，不会经过超过log(n)条重链，换句话说，轻边数量不超过logn。 ● 这是由于，一个轻儿子的子树大小不会超过其父节点子树大小一半，也就是说，每次向上经过一条轻边，子树大小就要至少翻倍。 ● 这句话的另一种表达形式就是：所有点的轻儿子子树大小之和是O(nlogn)的，这一性质其实跟重链剖分关系不大，只不过在做一些问题的时候会有用处。
那么重链剖分能做什么呢？
求LCA： ● 由于每个点到根的路径经过轻边数量是logn的，那么其到根的路径就是logn条重链的前缀拼成的。 ● 类似的两个点间的路径就是logn条重链的区间拼成的。 ● 如何提取出这些重链的区间？若两个点在同一条链上则结束；否则跳那个链顶深度更大的点，跳到链顶的父节点。 ● 你发现这样顺便就求出了LCA……（最后两个点在同一条链上的时候，深度较浅的那个点就是LCA）
大家可能会有这样的问题：为什么每次跳的不是深度更大的节点而是所在链顶深度更大的往上跳？因为如果先跳深度更大的，有可能会跳过头。加入深度更大的先跳，那么x会先跳，然后x会跳到不知道哪里去……但如果先跳y的话，它会先跳到自己，然后再跳到它的父亲——根结点，然后它和x就在同一条重链上了。
其实长链剖分和重链剖分类似，只不过把最“重”的子结点换成了子树深度最大的子结点而已，这里就不说了（实在太困了）。
最后一步：上例题和代码。
重链剖分例题：洛谷P3384 【模板】轻重链剖分/树链剖分 ● 1 x y z，表示将树从x到y结点最短路径上所有节点的值都加上z。 ● 2 x y，表示求树从x到y结点最短路径上所有节点的值之和。 ● 3 x z，表示将以x为根节点的子树内所有节点值都加上z。 ● 4 x，表示求以x为根节点的子树内所有节点值之和。 长链剖分例题：K级祖先问题 ● 多次询问一个点x的第k级祖先。要求O(nlogn)+O(1)。 ● 长链剖分，在链顶处维护倍增中的up数组，以及其向上、向下（沿重链）走1<=i<=链长步，到达哪个点； ● 每次对于询问的k，若距离链顶不足k，可以直接算；否则跳到链顶重新算k，找到一个最大的不超过k的2的幂次，比如t，然后通过倍增数组跳t步，然后可以发现此时所在点y，其所在链长肯定大于等于t，因此仍然能够直接求出。
重链剖分代码：
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,rt;
int x,y;
int head[500010];
int to[1000010];
int next[1000010];
int son[500010];
int size[500010];
int top[500010];
int d[500010];
int f[500010];
int tot;
void add(int x,int y)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x)//处理出每个点的重儿子son[]，子树大小size[]，深度d[]及父节点f[]
{
size[x]=1;
d[x]=d[f[x]]+1;
for(int i=head[x];i;i=next[i])
{
if(to[i]!=f[x])
{
f[to[i]]=x;
dfs(to[i]);
size[x]+=size[to[i]];
if(size[to[i]]>size[son[x]])
{
son[x]=to[i];
}
}
}
}
void dfs2(int x,int tp)//处理出每个点所在重链的链头top[]
{
top[x]=tp;
if(son[x])
{
dfs2(son[x],tp);
}
for(int i=head[x];i;i=next[i])
{
if(to[i]!=f[x]&&to[i]!=son[x])
{
dfs2(to[i],to[i]);
}
}
}
//如果两个点不在同一条重链上，那么直接把链头深的点跳到链头，
//重复这个过程，直到两个点处在同一条重链上，直接输出深度浅的点就是lca了
int lca(int x,int y){
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
{
swap(x,y);
}
x=f[top[x]];
}
return d[x]<d[y]?x:y;
}
int main()
{
scanf("%d%d%d",&n,&m,&rt);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(rt);
dfs2(rt,rt);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d/n",lca(x,y));
}
}
长链剖分代码：
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,rt;
int x,y;
int head[500010];
int to[1000010];
int next[1000010];
int son[500010];
int mx[500010];
int top[500010];
int d[500010];
int f[500010];
int tot;
void add(int x,int y)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x)//长链剖分求lca的过程和重链剖分一样，只有这里略有不同
{
d[x]=d[f[x]]+1;
mx[x]=d[x];
for(int i=head[x];i;i=next[i])
{
if(to[i]!=f[x])
{
f[to[i]]=x;
dfs(to[i]);
mx[x]=max(mx[to[i]],mx[x]);
if(mx[to[i]]>mx[son[x]])
{
son[x]=to[i];
}
}
}
}
void dfs2(int x,int tp)
{
top[x]=tp;
if(son[x])
{
dfs2(son[x],tp);
}
for(int i=head[x];i;i=next[i])
{
if(to[i]!=f[x]&&to[i]!=son[x])
{
dfs2(to[i],to[i]);
}
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
{
swap(x,y);
}
x=f[top[x]];
}
return d[x]<d[y]?x:y;
}
int main()
{
scanf("%d%d%d",&n,&m,&rt);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(rt);
dfs2(rt,rt);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d/n",lca(x,y));
}
}
终于的终于，在最后的最后，我们来到了今天的第last个算法——搜索！！！现在是北京时间：2022年7月27日23:20，作者的灵魂已经无了。但话说回来，搜索可是作者学的最好的算法之一（doge）。关于搜索，相信现在在屏幕面前的许多大佬都已经再熟悉不过了，尤其是再OI的赛场上有题没思路时一言不合就开始暴搜，结果想不到加了几个剪枝就AC了（bushi）。
众所周知，一共有两种搜索方式，dfs（深度优先搜索，depth first search）和bfs（广度优先搜索，breadth first search）以及bdfs（百度优先搜索，baidu first search）。我们先来看一下这两种搜索方式的具体代码的基本框架。
dfs的基本框架
void dfs(int dep)
{
if(到达终止条件)
{
输出
return ;
}
for(每种递归方式)
{
if(满足条件)
{
标记已经被遍历过
dfs(下一个状态);
标记为未被遍历过
}
}
}
bfs的基本框架
void bfs(int x,int y)
{
入队列
while(队列不空)
{
队首元素cur出队
if(队首元素cur是目标状态)
{
return ;
}
for(遍历每种规则)
{
由cur产生新状态nxt
if(nxt合法且没出现过)
{
nxt入队列
}
}
}
}
没啥可说的，上例题吧：
例1：
给出两个素数p1,p2，x满足如下条件：
(1) x以p1结尾；
(2) x是p2的倍数；
(3) x是满足条件(1),(2)的所有数中 的最小值。
给出t组p1,p2，计算所有x之和。
范围：5 < p1,p2 < 1,000,000; t < 100,000。
例如：p1 = 19， p2 = 23，则x = 1219。
核心代码：
void dfs(int step,long long cur)
{
if(ok)
{
return ;
if(step==cnt)
{
ok=true;
tmp=cur*p2;
return ;
}
for(int x=0;x<10;x++)
{
if((cur+x*mi[step])*p2%mi[step+1]==p1%mi[step+1])
{
dfs(step+1,cur+x*mi[step]);
}
}
}
}
例2 洛谷P2730 魔板（请大家自行去读题并AC（doge）） ● bfs ● 只要按照A→C的顺序来扩展新状态，求得的操作序列一定字典序最早。 ● 用string类型存储状态。 ● 考虑使用 STL map 来判重，也可以用hash（模大质数）或者康拓展开。 ● 用map存储起点状态到当前状态所需的最少步数，以及到达它的上一个状态与上一个操作代号。
bfs的模板性是极强的，每次只要稍微更改几个地方就可以，但dfs则不是，dfs的代码不仅需要按题目来定，而且由于它是递归算法，在数据量大的时候还会添加许多的优化，在搜索上面称为剪枝（为啥这样叫可以去bdfs）。
搜索的剪枝最基本的有可行性剪枝、最优性剪枝、记忆化剪枝。可行性剪枝就是在这个不可能成为合法解的时候剪枝，最优性剪枝就是在这个不可能成为最优解的时候剪枝，记忆化剪枝就是记录搜索过的每一个状态，当重复搜索到相同的状态的时候直接放回结果。
例3 poj3009 ● 在二维平面内有一个冰壶开始在起点S，要到终点T，推冰壶冰 壶会一直走到出界，碰到障碍物会停下，并且障碍物会消失，求最少多少步完成。 ● 爆搜，每次枚举往那个方向走，然后一直走过去，注意回溯，当你从上一层递归回来的时候你要把撞掉的障碍物复原回去。 ● 最优性剪枝 ● 当你在搜索时要最优化某个值时，你可以记录ans表示当前最优值，如果你在搜索时还没搜完答案却超过了ans，那么就退出即可。 ● 这个题记录ans表示最小多少步能够完成，在搜索时判断当前步数和ans即可。
剪枝也有许多需要注意的地方，比如说我们剪枝的时候，会计算出一些作为条件的变量，计算这些变量会产生一定的效果，但是计算他们也会消耗一定的时间，我们称作“代价”。如果一个剪枝的代价大于它所能产生的优化，那么就是不好的。
小结：
（1）深搜的常用方法：
①剪枝
②记忆化搜索
③改变搜索顺序
④预处理信息
（2）可行性与最优化剪枝：
①如果判断下不能做到了，退出。
②如果已经不可能再优了，退出。
接下来请允许我隆重介绍一下迭代加深搜索：
算法概要：
● 所谓的迭代加深，是一种dfs和bfs的融合体
● dfs之前的一大缺点就是我们不知道要搜多深。迭代加深搜索里面，每次搜索对深度有一定的限制，依次加深，从而达到目的。
代码：
inline void dfs(int cur,int dep)
{
if(cur==end)
{
//do something;
}
else if(dep<lim)
{
dfs(new_state,dep+1);
}
else
{
return ;
}
}
int main()
{
for(lim=1;lim<=n;lim++)
{
dfs(start,0);
}
return 0;
}
迭代加深搜索练习题：骑士精神 洛谷P2324
其实，这道题还有另外一种做法：二进制搜索。
（备注：现在是2022年7月28日00:00）
二进制搜索听起来十分的高大上，其实就是通过枚举二进制数来进行搜索。比如6的二进制表示就是110,11的二进制表示是1011。考虑一个n为二进制数，当对应位是0/1时表示不同状态。
最后，我再介绍一个折半搜索就收工辣！！！折半搜索，顾名思义，就是运用了二分的思想，就是先搜索前一半，再搜索后一半，然后把两半合起来求得答案，这样有时候是比搜一个整体来的优秀。给个例题吧：
洛谷P4799：
洛谷P4799 ● N场比赛M元钱，如果总票价不超过预算，有多少种观赛方案 ● N<=40 算法分析： ● 可以把这个序列分为两段[1,n/2]和[n/2+1,n]分别搜这两段，用两个数组分别存储每次的答案。 ● 折半搜索的统计/组合答案是最复杂的部分，这个题我们应该如何统计呢？ ● 先将第一个数组排序，然后枚举第二个数组的每一个数设为w， 算出总钱数-w也就是剩余的钱数，然后找出第一个数组中第一个大于剩余的钱数的位置，因为第一个数组已经排好序，所以在这个位置之前的数都会小于剩余的钱数，答案就出来了。
什么？！竟然有人问我代码？代码是什么？？我可什么都不知道，啊那个现在是2022年7月28日凌晨0点5分，终于…终于…终于……（作者已挂）
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/277433.html