BZOJ_4765_普通计算姬_分块
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
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
10
9
对结点编号进行分块，树状数组维护dfs序。
先预处理出来i到根路径上经过了多少第j块内的点，预处理时间复杂度$O(n\sqrt n)$
修改时对所有块直接用刚才预处理出来的打标记，同时也要在树状数组上修改出来。
查询时整块直接加上标记，零散的在树状数组上暴力。
总时间复杂度$O(n\sqrt n logn)$，可过。
其实也可以对那些零散的修改$O(\sqrt n)$查询$O(1)$，能做到$O(n\sqrt n)$不过我写不过带log的。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define N 100050
typedef unsigned long long ll;
int size,block,L[N],R[N],pos[N],n,m;
int dep[N],fa[N],head[N],to[N<<1],nxt[N<<1],val[N],cnt,root,poi[N][350],dfn[N],son[N];
ll sum[N],tag[N],s[N],c[N];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void fix(int x,ll v) {
for(;x<=n;x+=x&(-x)) c[x]+=v;
}
ll inq(int x) {
ll re=0;
for(;x;x-=x&(-x)) re+=c[x]; return re;
}
void dfs(int x,int y) {
int i,j; fa[x]=y; dep[x]=dep[y]+1; sum[x]=val[x]; dfn[x]=++dfn[0];
poi[x][pos[x]]++;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
for(j=1;j<=block;j++) poi[to[i]][j]=poi[x][j];
dfs(to[i],x);
sum[x]+=sum[to[i]];
}
}
son[x]=dfn[0];
}
void modify(int x,int y) {
int i;
for(i=1;i<=block;i++) tag[i]+=1ll*y*poi[x][i];
}
ll query(int x,int y) {
int p=pos[x],q=pos[y],i;
ll ans=0;
if(p==q) {
for(i=x;i<=y;i++) ans+=inq(son[i])-inq(dfn[i]-1);
}else {
for(i=p+1;i<q;i++) ans+=s[i]+tag[i];
for(i=x;i<=R[p];i++) {
ans+=inq(son[i])-inq(dfn[i]-1);
}
for(i=L[q];i<=y;i++) {
ans+=inq(son[i])-inq(dfn[i]-1);
}
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
int i,x,y,opt,j; size=sqrt(n);
block=n/size;
for(i=1;i<=block;i++) {
L[i]=R[i-1]+1; R[i]=size*i;
for(j=L[i];j<=R[i];j++) {
pos[j]=i;
}
}
if(R[block]!=n) {
block++; L[block]=R[block-1]+1; R[block]=n;
for(i=L[block];i<=n;i++) pos[i]=block;
} for(i=1;i<=n;i++) scanf("%d",&i[val]);
for(i=1;i<=n;i++) {
scanf("%d%d",&x,&y);
if(x) {
add(x,y); add(y,x);
}else root=y;
}
dfs(root,0);
for(i=1;i<=n;i++) s[pos[i]]+=sum[i],fix(dfn[i],val[i]);
while(m--) {
scanf("%d%d%d",&opt,&x,&y);
if(opt==1) {
modify(x,-val[x]); fix(dfn[x],-val[x]);val[x]=y;
modify(x,val[x]); fix(dfn[x],val[x]);
}else {
printf("%llu\n",query(x,y));
}
}
}