http://www.elijahqi.win/archives/3696
Description
“奋战三星期，造台计算机”。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些
。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题
：给定一棵n个节点的带权树，节点编号为1到n，以root为根，设sum[p]表示以点p为根的这棵子树中所有节点的权
值和。计算姬支持下列两种操作:
1 给定两个整数u,v，修改点u的权值为v。
2 给定两个整数l,r，计算sum[l]+sum[l+1]+….+sum[r-1]+sum[r]
尽管计算姬可以很快完成这个问题，可是小G并不知道它的答案是否正确，你能帮助他吗？
Input
第一行两个整数n,m，表示树的节点数与操作次数。
接下来一行n个整数，第i个整数di表示点i的初始权值。
接下来n行每行两个整数ai,bi，表示一条树上的边，若ai=0则说明bi是根。
接下来m行每行三个整数，第一个整数op表示操作类型。
若op=1则接下来两个整数u,v表示将点u的权值修改为v。
若op=2则接下来两个整数l,r表示询问。
N<=10^5,M<=10^5
0<=Di,V<2^31,1<=L<=R<=N,1<=U<=N Output
对每个操作类型2输出一行一个整数表示答案。
Sample Input
6 4
0 0 3 4 0 1
0 1
1 2
2 3
2 4
3 5
5 6
2 1 2
1 1 1
2 3 6
2 3 5
Sample Output
16
10
9
HINT
Source
按照序列分块 1~n设f[i][x]表示如果修改了x 会对i块产生几次的影响
然后建立dfs序 用树状数组维护子树和
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll unsigned long long
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
return x*f;
}
const int N=1e5+10;
struct node{
int y,next;
}data[N<<1];
ll s[N],sum[N],size[N];
int h[N],n,m,nn,in[N],out[N],st[375],f[N][375],num,a[N],bl[N],rt,nm;
inline void add(int x,ll v){
while(x<=n) s[x]+=v,x+=x&-x;
}
inline ll query(int x){
static ll tmp;tmp=0;
while(x) tmp+=s[x],x-=x&-x;return tmp;
}
inline void dfs(int x,int fa){
++st[bl[x]];in[x]=++num;add(in[x],a[x]);size[x]=a[x];
for (int i=1;i<=nm;++i) f[x][i]=st[i];
for (int i=h[x];i;i=data[i].next){
int y=data[i].y;if (y==fa) continue;
dfs(y,x);size[x]+=size[y];
}out[x]=num;--st[bl[x]];sum[bl[x]]+=size[x];
}
int main(){
freopen("bzoj4765.in","r",stdin);
n=read();m=read();nn=sqrt(n);nm=(n-1)/nn+1;
for (int i=1;i<=n;++i) a[i]=read();
for (int i=1;i<=n;++i) bl[i]=(i-1)/nn+1;
for (int i=1;i<=n;++i){
int x=read(),y=read();
if (!x) {rt=y;continue;}
data[++num].y=y;data[num].next=h[x];h[x]=num;
data[++num].y=x;data[num].next=h[y];h[y]=num;
}num=0;dfs(rt,0);
for (int owo=1;owo<=m;++owo){
int op=read(),x=read(),y=read();
if (op==1){
for (int i=1;i<=nm;++i) sum[i]+=(ll)f[x][i]*(y-a[x]);
add(in[x],y-a[x]);a[x]=y;
}else{
ll ans=0;
if (bl[x]==bl[y]){
for (int i=x;i<=y;++i) ans+=query(out[i])-query(in[i]-1);
printf("%llu\n",ans);
}else{
for (int i=bl[x]+1;i<bl[y];++i) ans+=sum[i];
for (int i=x;bl[i]==bl[x];++i) ans+=query(out[i])-query(in[i]-1);
for (int i=y;bl[i]==bl[y];--i) ans+=query(out[i])-query(in[i]-1);
printf("%llu\n",ans);
}
}
}
return 0;
}