题意：
一棵树，支持单点修改和询问以$[l,r]$为根的子树的权值和的和
只有我这种不会分块的沙茶不会做这道题吗？
说一点总结：
子树和当然上$dfs$序了，询问原序列一段区间所有子树和，对原序列分块，$sum_i$为一块的答案
查询很显然了，整块用$sum$，非整块暴力查子树
修改的话，预处理$f[i][j]$为点$j$对第$i$块的贡献，一遍$dfs$就可以预处理出来
然后，我的$BIT$用了$build$函数竟然比不用还慢
真的很好写
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef unsigned long long ll; const int N=1e5+5,M=320; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,Q,u,v,op,w[N]; int root; struct Edge{ int v,ne; }e[N<<1]; int cnt,h[N]; inline void ins(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt; } struct BIT{ ll c[N]; inline void add(int p,ll v){for(;p<=n;p+=(p&-p)) c[p]+=v;} inline ll sum(int p){ ll re=0; for(;p;p-=(p&-p)) re+=c[p]; return re; } }C; int block,m,pos[N]; int a[N],L[N],R[N],dfc; int f[M][N]; void dfs(int u,int fa){ L[u]=++dfc; a[pos[u]]++; for(int i=1;i<=m;i++) f[i][u]+=a[i]; for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa) dfs(e[i].v,u); R[u]=dfc; a[pos[u]]--; } ll subtree(int x){return C.sum(R[x])-C.sum(L[x]-1);} ll sum[N]; void Change(int x,int v){ C.add(L[x],v-w[x]); for(int i=1;i<=m;i++) sum[i]+=(ll)(v-w[x])*f[i][x]; w[x]=v; } ll Query(int l,int r){ ll re=0; if(pos[l]==pos[r]) for(int i=l;i<=r;i++) re+=subtree(i); else{ int _=pos[l]*block; for(int i=l;i<=_;i++) re+=subtree(i); for(int i=(pos[r]-1)*block+1;i<=r;i++) re+=subtree(i); for(int i=pos[l]+1;i<pos[r];i++) re+=sum[i]; } return re; } int main(){ freopen("in","r",stdin); n=read();Q=read(); block=sqrt(n); m=(n-1)/block+1; for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=n;i++){ u=read();v=read(); if(u) ins(u,v); else root=v; pos[i]=(i-1)/block+1; } dfs(root,0); for(int i=1;i<=n;i++) C.add(L[i],w[i]); for(int i=1;i<=m;i++){ int l=(i-1)*block+1,r=min(i*block,n); for(int j=l;j<=r;j++) sum[i]+=subtree(j); } while(Q--){ op=read();u=read();v=read(); if(op==1) Change(u,v); else printf("%llu ",Query(u,v)); } }
MashiroSky怎么这么快啊.....发现他一开始子树和写在dfs里我也改成那样啦怎么还是这么慢><.......
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef unsigned long long ll; const int N=1e5+5,M=350; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,Q,u,v,op,w[N]; int root; struct Edge{ int v,ne; }e[N<<1]; int cnt,h[N]; inline void ins(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt; } struct BIT{ ll c[N]; inline void add(int p,ll v){for(;p<=n;p+=(p&-p)) c[p]+=v;} inline ll sum(int p){ ll re=0; for(;p;p-=(p&-p)) re+=c[p]; return re; } }C; int block,m,pos[N]; int a[N],L[N],R[N],dfc; int f[M][N]; ll subtree(int x){return C.sum(R[x])-C.sum(L[x]-1);} ll sum[N]; ll dfs(int u,int fa){ L[u]=++dfc; a[pos[u]]++; C.add(L[u],w[u]); ll s=w[u]; for(int i=1;i<=m;i++) f[i][u]+=a[i]; for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa) s+=dfs(e[i].v,u); R[u]=dfc; a[pos[u]]--; sum[pos[u]]+=s; return s; } void Change(int x,int v){ C.add(L[x],v-w[x]); for(int i=1;i<=m;i++) sum[i]+=(ll)(v-w[x])*f[i][x]; w[x]=v; } ll Query(int l,int r){ ll re=0; if(pos[l]==pos[r]) for(int i=l;i<=r;i++) re+=subtree(i); else{ int _=pos[l]*block; for(int i=l;i<=_;i++) re+=subtree(i); for(int i=(pos[r]-1)*block+1;i<=r;i++) re+=subtree(i); for(int i=pos[l]+1;i<pos[r];i++) re+=sum[i]; } return re; } int main(){ freopen("in","r",stdin); n=read();Q=read(); block=300; m=(n-1)/block+1; for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=n;i++){ u=read();v=read(); if(u) ins(u,v); else root=v; pos[i]=(i-1)/block+1; } dfs(root,0); while(Q--){ op=read();u=read();v=read(); if(op==1) Change(u,v); else printf("%llu ",Query(u,v)); } }