图论算法|luogu P3178 [HAOI2015]树上操作
![图论算法|luogu P3178 [HAOI2015]树上操作](https://img.it610.com/image/info8/f531010f5afd4646a2a33fd0edbdc695.jpg)
文章图片
analysis 【图论算法|luogu P3178 [HAOI2015]树上操作】一看题，修改点和链查询子树点集的权值和，就是树链剖分了！
code
#include
using namespace std;
#define loop(i,start,end) for(register int i=start;
i<=end;
++i)
#define anti_loop(i,start,end) for(register int i=start;
i>=end;
--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((avoid read(T &x){
x=0;
char r=getchar();
T neg=1;
while(r<'0'||r>'9'){if(r=='-')neg=-1;
r=getchar();
}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';
r=getchar();
}
x*=neg;
}
inline void addl(int u,int v){
edge[cnt].e=v;
edge[cnt].nxt=head[u];
head[u]=cnt++;
}
void dfs1(int u,int f){
fa[u]=f;
dep[u]=dep[f]+1;
siz[u]=1;
for(int i=head[u];
i!=-1;
i=edge[i].nxt){
int v=edge[i].e;
if(v==f)continue;
dfs1(v,u);
siz[u]+=siz[v];
son[u]=((siz[son[u]][v])?v:son[u]);
//siz[0]==0
}
}
void dfs2(int u,int fa){
if(son[u]){
seg[son[u]]=++seg[0];
//seg[u]=++seg[0];
rev[seg[0]]=son[u];
//rev[seg[0]]=u;
top[son[u]]=top[u];
dfs2(son[u],u);
}
for(int i=head[u];
i!=-1;
i=edge[i].nxt){
int v=edge[i].e;
if(!top[v]){
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,u);
}
}
}
inline void pushdown(int l,int r,int rt){
if(!lazy[rt])return;
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
sum[rt<<1]+=lazy[rt]*(((r+l)>>1)-l+1);
//sum[rt<<1|1]+=lazy[rt]*(((r+l)>>1)-l+1);
sum[rt<<1|1]+=lazy[rt]*(r-(((l+r)>>1)+1)+1);
lazy[rt]=0;
}
inline void pushup(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
sum[rt]=num[rev[l]];
return;
}
int mid=l+((r-l)>>1);
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(int l,int r,int nl,int nr,int rt){
if(l<=nl&&nr<=r){
return sum[rt];
}
pushdown(nl,nr,rt);
int mid=(nl+((nr-nl)>>1));
//int mid=(l+((r-l)>>1));
ll _sum=0;
if(mid>=l)_sum+=query(l,r,nl,mid,rt<<1);
if(mid>1);
if(mid>=l)update(l,r,nl,mid,rt<<1,w);
if(mid 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法