好毒瘤的题。能看出来是离线分块，具体细节还是挺让人难受的，，，主要是坑点太多了
给定一棵树，两种操作：
1.修改点权
2.求编号在$[l,r]$之间的$sum$和。$sum$指子树权值和。
$n leq 1e5$
坑一：此题答案可能会爆long long，要用ull。。
我们最开始想到要对编号分块，维护$sum$。预处理出每次修改点权的时候会对每个块分别作出多少贡献（其实就是每个块里有多少是它的祖先）。这个复杂度是$O(sqrt n)$的。
坑二：然后我们发现$n sqrt n$的long long数组大概正好256MB的样子，要卡一卡。
块内的自然$O(1)$出答案，块外的由于修改时不能具体到一个点所以要单求。显然对于单求来说最优的是用树状数组$O(logn)$出解。
然而我们上限有$sqrt n$个点要求解，于是询问变成了$O(sqrt n logn)$的了。
坑三：这个复杂度会被卡掉。可能会说块不开$sqrt n$的，然而最优的$sqrt{frac n{log_2n}}$，均摊每次操作也要大概$2000$左右复杂度。
于是我们发现修改快，询问慢。我们能不能牺牲一些修改时间使询问更加快速呢？
然后我们再对dfs序使用分块，维护权值前缀和。这样修改时复杂度仍然是$O(sqrt n)$，只不过多了一倍常数在维护这个前缀和上。询问的时候，我们要求的是一个区间，只要知道两个单点，相减就行了。查询单点是$O(1)$的，有$sqrt n$个要查询，这样询问也变成$O(sqrt n)$的了。
于是就顺利解决了！真的是很妙很坑很毒瘤的一道题，，
P.S. 分块好久没写，想回去看一下以前数颜色的代码。然后发现我的bel数组一直是0？然后发现这样l和r的所在块一直一样，就一直在做暴力，然后我就是暴力A的？mmp，我把bel数组赋上值，然后寻思能快点，然后，，WA了。mmp
#include<cstdio> #include<cctype> #include<cmath> #include<iostream> using namespace std; const int N=100001; const int M=318; typedef unsigned long long ll; inline int read(){ int r=0,c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c)) r=r*10+c-'0',c=getchar(); return r; } struct Edge{ int to,nxt; }e[N*2]; int head[N],cnt=1; void add(int u,int v){ e[cnt]=(Edge){v,head[u]}; head[u]=cnt++; e[cnt]=(Edge){u,head[v]}; head[v]=cnt++; } int n,m,tot,dc=-1; int in[N],out[N],bel[N]; ll s[N],sum[M],S[N],Lz[M]; ll c[N][M],val[N],bk; void dfs(int u,int fa){ in[u]=++dc;S[dc]=S[dc-1]+val[u]; for(int i=1;i<=tot;i++) c[u][i]=c[fa][i]; c[u][bel[u]]++; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa)continue; dfs(v,u);s[u]+=s[v]; } out[u]=dc; } void modify(int u,ll v){ ll dt=v-val[u];val[u]=v; for(int i=1;i<=tot;i++) sum[i]+=c[u][i]*dt; int l=in[u],r=n; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++) S[i]+=dt; return; } for(int i=bel[l]+1;i<bel[r];i++) Lz[i]+=dt; for(int i=l;i<=bel[l]*bk;i++) S[i]+=dt; for(int i=(bel[r]-1)*bk+1;i<=r;i++) S[i]+=dt; int ans=0; } ll ask(int x){ return S[x]+Lz[bel[x]]; } void query(int l,int r){ ll ans=0; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++) ans+=ask(out[i])-ask(in[i]-1); printf("%llu ",ans); return; } for(int i=bel[l]+1;i<bel[r];i++) ans+=sum[i]; for(int i=l;i<=bel[l]*bk;i++) ans+=ask(out[i])-ask(in[i]-1); for(int i=(bel[r]-1)*bk+1;i<=r;i++) ans+=ask(out[i])-ask(in[i]-1); printf("%llu ",ans); } void init(){ n=read(),m=read(); bk=sqrt(n);tot=n%bk==0?n/bk:n/bk+1; for(int i=1;i<=n;i++) val[i]=s[i]=read(),bel[i]=(i-1)/bk+1; for(int i=1;i<=n;i++) add(read(),read()); dfs(0,0); for(int i=1;i<=n;i++) sum[bel[i]]+=s[i]; } void solve(){ while(m--){ int opt=read(),x=read(),y=read(); if(opt==1)modify(x,y); else query(x,y); } } int main(){ init(); solve(); }