树链剖分学习笔记
2026-04-18 14:54:27
发布于：广东
31阅读
0回复
0点赞
rt,但是概念还没来得及写
树剖求LCA
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
vector<int> g[100009];
int fa[100009],dep[100009],son[100009],sz[100009],top[100009];
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
sz[u] = 1;
for(auto v:g[u]){
if(v == f) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]){
son[u] = v;
}
}
}
void dfs2(int u,int t){
top[u] = t;
if(son[u] == 0) return ;
dfs2(son[u],t);
for(auto v:g[u]){
if(v == fa[u]||v == son[u]) continue;
dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u = fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
signed main(){
cin>>n;
for(int i = 1;i<n;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
cout<<dep[u]+dep[v]-2*dep[lca(u,v)]<<'\n';//这里是求2点之间距离，求lca就是cout<<lca(u,v)<<'\n';
}
}
书剖+线段树求树上单点修改&路径sun,max查询（无lazy_tag）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc 2*i
#define rc lc+1
int n,q,tot,MX,SUM;
vector<int> g[30009];
int fa[30009],dep[30009],son[30009],sz[30009],top[30009],w[30009];
int id[30009],rid[30009];
int sum[120009],mx[120009];
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
sz[u] = 1;
for(auto v:g[u]){
if(v == f) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u] = v;
}
}
void dfs2(int u,int t){
top[u] = t;
id[u] = ++tot;
rid[tot] = u;
if(son[u] == 0) return ;
dfs2(son[u],t);
for(auto v:g[u]){
if(v == fa[u]||v == son[u]) continue;
dfs2(v,v);
}
}
void pushup(int i){
sum[i] = sum[lc]+sum[rc];
mx[i] = max(mx[lc],mx[rc]);
}
void build(int i,int l,int r){
if(l == r){
sum[i] = mx[i] = w[rid[l]];
return ;
}
int mid = l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(i);
}
void update(int i,int l,int r,int p,int x){
if(l == r){
sum[i] = mx[i] = x;
return ;
}
int mid = l+r>>1;
if(p<=mid) update(lc,l,mid,p,x);
else update(rc,mid+1,r,p,x);
pushup(i);
}
void query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
SUM+=sum[i];
MX = max(MX,mx[i]);
return ;
}
int mid = l+r>>1;
if(ql<=mid) query(lc,l,mid,ql,qr);
if(qr>mid) query(rc,mid+1,r,ql,qr);
}
void ask(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
query(1,1,n,id[top[u]],id[u]);
u = fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
query(1,1,n,id[u],id[v]);
}
signed main(){
cin>>n;
for(int i = 1;i<n;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1;i<=n;++i){
cin>>w[i];
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
cin>>q;
while(q--){
string op;
cin>>op;
if(op == "CHANGE"){//点p修改为x
int p,x;
cin>>p>>x;
update(1,1,n,id[p],x);
}else{
int u,v;
cin>>u>>v;
SUM = 0;
MX = -1e9;
ask(u,v);
if(op == "QMAX") cout<<MX<<'\n';//u->v max
else cout<<SUM<<'\n';//u->v sum
}
}
}
树上路径点权加&单点の子树和查询（含有lazy_tag）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc 2*i
#define rc lc+1
int n,q,tot,MX,SUM;
vector<int> g[100009];
int fa[100009],dep[100009],son[100009],sz[100009],top[100009],w[100009];
int id[100009],rid[100009];
int sum[400009],tag[400009];
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
sz[u] = 1;
for(auto v:g[u]){
if(v == f) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u] = v;
}
}
void dfs2(int u,int t){
top[u] = t;
id[u] = ++tot;
rid[tot] = u;
if(son[u] == 0) return ;
dfs2(son[u],t);
for(auto v:g[u]){
if(v == fa[u]||v == son[u]) continue;
dfs2(v,v);
}
}
void addtag(int i,int l,int r,int x){
sum[i]+=(r-l+1)*x;
tag[i]+=x;
}
void downtag(int i,int l,int r){
int mid = l+r>>1;
sum[lc]+=tag[i]*(mid-l+1);
tag[lc]+=tag[i];
sum[rc]+=tag[i]*(r-mid);
tag[rc]+=tag[i];
tag[i] = 0;
}
void pushup(int i){
sum[i] = sum[lc]+sum[rc];
}
void update(int i,int l,int r,int ql,int qr,int x){
if(r<ql||qr<l) return ;
if(ql<=l&&r<=qr){
addtag(i,l,r,x);
return ;
}
downtag(i,l,r);
int mid = l+r>>1;
update(lc,l,mid,ql,qr,x);
update(rc,mid+1,r,ql,qr,x);
pushup(i);
}
void query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
SUM+=sum[i];
return ;
}
downtag(i,l,r);
int mid = l+r>>1;
if(ql<=mid) query(lc,l,mid,ql,qr);
if(qr>mid) query(rc,mid+1,r,ql,qr);
}
void ask(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
query(1,1,n,id[top[u]],id[u]);
u = fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
query(1,1,n,id[u],id[v]);
}
void upd(int u,int v,int d){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(1,1,n,id[top[u]],id[u],d);
u = fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(1,1,n,id[u],id[v],d);
}
signed main(){
cin>>n;
for(int i = 1;i<n;++i){
int u,v;
cin>>u>>v;
u++,v++;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
cin>>q;
while(q--){
string op;
cin>>op;
if(op == "Add"){
int u,v,d;
cin>>u>>v>>d;
u++,v++;
upd(u,v,d);
}else{
int u;
cin>>u;
u++;
SUM = 0;
query(1,1,n,id[u],id[u]+sz[u]-1);
cout<<SUM<<'\n';
}
}
}
有帮助，赞一个