求和（dfs序+树状数组）

题目：

给一棵以 $k$ 为根的有根树，点权 $v_i$ 。
$m$ 个操作，操作有两种类型：
$1\space a\space x$ ：表示将节点 $a$ 的权值加上 $x$ ；
$2\space a$ ：表示求 $a$ 节点的子树上所有节点的和（包括 $a$ 结点本身）；
$n、m≤1e6$

做法：

单点修改，求子树上的点权和。我们通过 $dfs$ 序可以将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。线段树或树状数组就行了。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
struct edge{
    int v, nxt;
}e[N<<1];
int tot, head[N];
int n, m, k, a[N];
int dfn[N], cnt, in[N], out[N];
ll T[N];
void init(void){
    tot = 0;
    memset(head, -1, sizeof head);
}
void addedge(int u, int v){
    e[tot] = (edge){v, head[u]};
    head[u] = tot++;
}
void dfs(int u, int p){
    dfn[++cnt] = u, in[u] = cnt;
    for (int i = head[u]; i != -1; i = e[i].nxt){
        int v = e[i].v;
        if (v == p) continue;
        dfs(v, u);
    }
    out[u] = cnt;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x, int y, int n){
    //printf("add x %d y %d\n", x, y);
    for (int i = x; i <= n; i += lowbit(i)) T[i] += y;
}
ll ask(int x){
    //printf("ask x %d\n", x);
    ll ans = 0;
    for (int i = x; i >= 1; i -= lowbit(i)) ans += T[i];
    return ans;
}
int main(void){
    init();
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n-1; ++i){
        int u, v; scanf("%d%d", &u, &v);
        addedge(u, v), addedge(v, u);
    } 
    dfs(k, k);
    for (int i = 1; i <= n; ++i) add(in[i], a[i], cnt);
    for (int i = 1; i <= m; ++i){
        int op, x, y;
        scanf("%d", &op);
        if (op == 1){
            scanf("%d%d", &x, &y);
            add(in[x], y, cnt);
        }else{
            scanf("%d", &x);
            printf("%lld\n", ask(out[x])-ask(in[x]-1));
        }
    }   
    return 0;
}