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并不知道它的答案是否正确，你能帮助他吗？
Solution
分块。块内直接统计，单点的sum树状数组暴力加起来
为了方便修改，g[a][i]表示点a对块[i]的贡献
另外，好坑啊这题会爆long long
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #define MAXN 100007 using namespace std; typedef unsigned long long LL; int n,m,init,num,head[MAXN],g[MAXN][330],cnt=0; LL c[MAXN],d[MAXN],sum[MAXN],blocks[330]; int dfn_clock=0,in[MAXN],out[MAXN],a[MAXN]; LL read() { LL x=0,f=1;char c=getchar(); 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; } struct Node { int next,to; }Edges[MAXN*2]; void addedge(int u,int v) { Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; } int lowbit(int x){return x&-x;} void add(int pos,int x) { while(pos<=n) { c[pos]+=x; pos+=lowbit(pos); } } LL query(int pos) { LL res=0; while(pos>0) { res+=c[pos]; pos-=lowbit(pos); } return res; } void dfs(int u,int f) { dfn_clock++;in[u]=dfn_clock; sum[u]=d[u]; a[(u-1)/init]++; for(int i=0;i<num;i++) g[u][i]+=a[i]; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==f)continue; dfs(v,u); sum[u]+=sum[v]; } blocks[(u-1)/init]+=sum[u]; out[u]=dfn_clock; a[(u-1)/init]--; } void Change(int a,int b) { add(in[a],b-d[a]); for(int i=0;i<num;i++) blocks[i]+=(b-d[a])*g[a][i]; d[a]=b; } void Query(int a,int b) { LL res=0; if((a-1)/init==(b-1)/init) for(int i=a;i<=b;i++) res+=query(out[i])-query(in[i]-1); else { for(int i=(a-1)/init+1;i<=(b-1)/init-1;i++) res+=blocks[i]; for(int i=a;i<((a-1)/init+1)*init+1;i++) res+=query(out[i])-query(in[i]-1); for(int i=b;i>=((b-1)/init)*init+1;i--) res+=query(out[i])-query(in[i]-1); } printf("%llu ",res); } int main() { memset(head,-1,sizeof(head)); n=read(),m=read(); init=(int)sqrt(n+0.1); num=(n-1)/init+1; for(int i=1;i<=n;i++) d[i]=read(); int root; for(int i=1;i<=n;i++) { int u=read(),v=read(); if(!u){root=v;continue;} addedge(u,v); addedge(v,u); } dfs(root,0); for(int i=1;i<=n;i++) add(in[i],d[i]); for(int i=1;i<=m;i++) { int opt=read(),a=read();LL b=read(); if(opt==1)Change(a,b); else Query(a,b); } return 0; }