题目链接

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(n\sqrt 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\n", 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\n", ask(l, r));

    }

    return 0;

}

巴特西

bzoj 4765 普通计算姬 dfs序 + 分块