题目链接
Description
"奋战三星期，造台计算机"。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题：
给定一棵(n)个节点的带权树，节点编号为(1)到(n)，以(root)为根，设(val[p])表示以点(p)为根的这棵子树中所有节点的权值和。计算姬支持下列两种操作:
-
给定两个整数(u),(v)，修改点(u)的权值为(v)。
-
给定两个整数(l,r)，计算(val[l]+val[l+1]+cdots+val[r-1]+val[r])
尽管计算姬可以很快完成这个问题，可是小G并不知道它的答案是否正确，你能帮助他吗？
注：原题面中标识符为(sum)，为以下表述清楚，在此擅改为(val).
题解
参考
https://www.cnblogs.com/ljh2000-jump/p/6514792.html
http://blog.csdn.net/qq_33229466/article/details/70837585
1 - dfs序
首先，(val)的计算依赖于(dfs)序。
(val[p])即为(dfs)序上的(l[p])到(r[p])这段区间的节点权值和。
2 - 分块
如何处理(val)的和？
给定的([l,r])区间在树上的分布毫无规律可言，因此只能分块。
通过分块维护每一块的和(sum)，不完整的块暴力算，完整的块直接统计和。
3 - 修改造成的影响
修改单点权值对子树和会造成什么影响？
修改点(u)的权值，会改变其所有祖先的子树和。
故，预处理出一个信息：用(f[u][i])表示在第(i)块中有多少个点是(u)的祖先。
有了这个信息，修改点(u)的权值对第(i)块的影响就是：sum[i] += f[u][i]*delta;
这个信息怎么获得呢？
(dfs)时，进一个点(u)时给其所在块的计数(+1)，出的时候再(-1).
每次(dfs)到一个点，遍历所有的块，(f[u][i])即为此时计数器的值。
时间复杂度：(O(nsqrt n))
4 - 不完整的块
上面说到，不完整的块暴力算，即对于块内的每个点(i)，直接计算(val[i])，也即(dfs)序上的(l[i])到(r[i])这段区间的节点权值和。
于是，我们现在的问题就是：单点修改，区间查询。
法一：树状数组
维护每个节点的权值。
对于每个操作：
修改：(O(logn))
查询：对不完整的块中的每个点都进行一次查询：(O(sqrt n*logn))
法二：分块
维护前缀和序列。
修改点(i)的权值，即相当于修改区间([i,n])的值。
用(tag)表示每一块的整体的增量。
对于每个操作：
修改：(O(sqrt n))
查询：对不完整的块中的每个点都进行一次查询：(O(sqrt n*1)=O(sqrt n))
Code
以下两个版本其实大同小异，差别就在(add)和(query)的不同实现...。
Ver 1
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
#define maxm 320
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
struct node { int to, ne; }edge[maxn<<1];
int ne[maxn], l[maxn], r[maxn], t[maxn], f[maxn][maxm], bl[maxn], v[maxn], vv[maxn];
int tot, nb, n, blo, cnt, m;
LL c[maxn], val[maxn], tag[maxm], pre[maxn];
ULL sum[maxm];
void addEdge(int u, int v) {
edge[tot] = {v, ne[u]};
ne[u] = tot++;
}
void dfs(int u, int fa) {
++t[bl[u]];
F2(i, 1, nb) f[u][i] = t[i];
l[u] = ++cnt;
for (int i = ne[u]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (v!=fa) dfs(v,u);
}
r[u] = cnt;
--t[bl[u]];
}
inline int lowbit(int x) { return x & (-x); }
inline void add(int x, LL v) { while (x<=n) c[x]+=v, x+=lowbit(x); }
inline LL query(int x) { LL ret=0; while (x) ret+=c[x], x-=lowbit(x); return ret; }
void init() {
F2(i, 1, n) val[i] = query(r[i]) - query(l[i]-1);
F2(i, 1, nb) {
F2(j, (i-1)*blo+1, min(i*blo, n)) sum[i] += val[j];
}
}
void modify(int u, int x) {
LL delta=x-v[u];
add(l[u], delta);
F2(i, 1, nb) sum[i] += f[u][i]*delta;
v[u] = x;
}
ULL ask(int ll, int rr) {
ULL ret=0;
F2(i, ll, min(bl[ll]*blo, rr)) ret += query(r[i])-query(l[i]-1);
if (bl[ll]!=bl[rr]) {
F2(i, (bl[rr]-1)*blo+1, rr) ret += query(r[i])-query(l[i]-1);
}
F(i, bl[ll]+1, bl[rr]) ret += sum[i];
return ret;
}
int main() {
scanf("%d%d", &n, &m); blo = sqrt(n);
F2(i, 1, n) {
scanf("%d", &v[i]);
bl[i] = (i-1)/blo+1;
}
nb = bl[n];
int rt;
memset(ne, -1, sizeof ne);
F(i, 0, n) {
int u, v;
scanf("%d%d", &u, &v);
if (!u) rt = v;
else addEdge(u, v), addEdge(v, u);
}
dfs(rt, -1);
F2(i, 1, n) add(l[i], v[i]);
init();
F(i, 0, m) {
int op, l, r;
scanf("%d%d%d", &op,&l,&r);
if (op==1) modify(l, r);
else printf("%llu
", ask(l, r));
}
return 0;
}
Ver 2
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
#define maxm 320
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
struct node { int to, ne; }edge[maxn<<1];
int ne[maxn], l[maxn], r[maxn], t[maxn], f[maxn][maxm], bl[maxn], v[maxn], vv[maxn];
int tot, nb, n, blo, cnt, m;
LL val[maxn], tag[maxm], pre[maxn];
ULL sum[maxm];
void addEdge(int u, int v) {
edge[tot] = {v, ne[u]};
ne[u] = tot++;
}
void dfs(int u, int fa) {
++t[bl[u]];
F2(i, 1, nb) f[u][i] = t[i];
l[u] = ++cnt;
for (int i = ne[u]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (v!=fa) dfs(v,u);
}
r[u] = cnt;
--t[bl[u]];
}
inline void add(int l, int r, LL v) {
F2(i, l, min(r, bl[l]*blo)) pre[i] += v;
if (bl[l]!=bl[r]) {
F2(i, (bl[r]-1)*blo+1, r) pre[i] += v;
}
F(i, bl[l]+1, bl[r]) tag[i] += v;
}
inline LL query(int x) { return pre[x]+tag[bl[x]]; }
void init() {
F2(i, 1, n) val[i] = query(r[i]) - query(l[i]-1);
F2(i, 1, nb) {
F2(j, (i-1)*blo+1, min(i*blo, n)) sum[i] += val[j];
}
}
void modify(int u, int x) {
LL delta=x-v[u];
add(l[u], n, delta);
F2(i, 1, nb) sum[i] += f[u][i]*delta;
v[u] = x;
}
ULL ask(int ll, int rr) {
ULL ret=0;
F2(i, ll, min(bl[ll]*blo, rr)) ret += query(r[i])-query(l[i]-1);
if (bl[ll]!=bl[rr]) {
F2(i, (bl[rr]-1)*blo+1, rr) ret += query(r[i])-query(l[i]-1);
}
F(i, bl[ll]+1, bl[rr]) ret += sum[i];
return ret;
}
int main() {
scanf("%d%d", &n, &m); blo = sqrt(n);
F2(i, 1, n) {
scanf("%d", &v[i]);
bl[i] = (i-1)/blo+1;
}
nb = bl[n];
int rt;
memset(ne, -1, sizeof ne);
F(i, 0, n) {
int u, v;
scanf("%d%d", &u, &v);
if (!u) rt = v;
else addEdge(u, v), addEdge(v, u);
}
dfs(rt, -1);
F2(i, 1, n) vv[l[i]] = v[i];
F2(i, 1, n) pre[i] = pre[i-1] + vv[i];
init();
F(i, 0, m) {
int op, l, r;
scanf("%d%d%d", &op,&l,&r);
if (op==1) modify(l, r);
else printf("%llu
", ask(l, r));
}
return 0;
}