DFS序线段树这道题的第2种操作不会代码实现
未完成
#include<iostream>
#include<cstdio>
#include<cstring>
#define Maxn 200000
using namespace std;
int head[Maxn+5],to[Maxn+5],nex[Maxn+5],tot;
int a[Maxn+5];
int q[Maxn+5],cnt;
int sum[Maxn+5];
int lazy[Maxn+5];
int s[Maxn+5],f[Maxn+5];//每个树上节点在q中的起点和终点
int up[Maxn+5];//每个区间有多少个正数
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void add(int x,int y)
{
to[++tot]=y;
nex[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int fa)
{
q[++cnt]=a[x];
s[x]=cnt;
for(int i=head[x];i!=-1;i=nex)
{
if(to==fa) continue;
dfs(to,x);
}
q[++cnt]=-a[x];
f[x]=cnt;
}
void build(int l,int r,int x)
{
if(l==r)
{
sum[x]=q[l];
return ;
}
int m=(l+r)>>1;
build(l,m,x2);
build(m+1,r,x2+1);
sum[x]=sum[x2]+sum[x2+1];
}
void pushdown(int x,int l,int r)
{
int m=(l+r)>>1;
lazy[x2]+=lazy[x];
lazy[x2+1]+=lazy[x];
sum[x2]+=lazy[x](m-l+1);
sum[x2+1]+=lazy[x](r-m);
lazy[x]=0;
}
void modify_point(int pos,int val,int l,int r,int x)
{
if(l==r)
{
sum[x]+=val;
return ;
}
int m=(l+r)>>1;
pushdown(x,l,r);
if(pos<=m)
{
modify_point(pos,val,l,m,x2);
}
else
{
modify_point(pos,val,m+1,r,x2+1);
}
sum[x]=sum[x2]+sum[x2+1];
}
int query(int L,int R,int l,int r,int x)
{
if(L<=l&&r<=R)
{
return sum[x];
}
int m=(l+r)>>1;
int ret=0;
pushdown(x,l,r);
if(L<=m)
{
ret+=query(L,R,l,m,x2);
}
if(R>m)
{
ret+=query(L,R,m+1,r,x2+1);
}
return ret;
}
int main()
{
init();
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
}
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,-1);
for(int i=1;i<=cnt;i++)
{
up=up[i-1];
if(q>0) up++;
}
build(1,cnt,1);
for(int i=1;i<=m;i++)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x,y;
scanf("%d %d",&x,&y);
modify_point(s[x],y,1,cnt,1);
modify_point(f[x],-y,1,cnt,1);
}
else if(op==2)
{
}
else
{
int x;
scanf("%d",&x);
printf("%d\n",query(1,s[x],1,cnt,1));
}
}
return 0;
}