【每日一题】dfs序专题 求和

Description

Solution

以前牛客小白赛里也有类似的题目，简单地讲，在树上进行子树区间上的修改和求和问题可以转化为我们熟悉的序列问题。
思路：处理出dfs序，然后找到每个节点的子树区间在哪个访问内，剩下的就是树状数组单点修改，区间求和的操作啦。
时间复杂度：O(nlogn)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll T[N];
int a[N];
int lowbit(int x) {
  return x & (-x);
}
void update(int x, int add) {
  while(x < N) {
    T[x] += add;
    x += lowbit(x);
  }
}
ll query(int x) {
  ll res = 0;
  while(x) {
    res += T[x];
    x -= lowbit(x);
  }
  return res;
}
int L[N], R[N], rk[N];
struct Edge {
  int v, nextz;
}edge[N << 1];
int head[N], tot;
void addedge(int u, int v) {
  edge[tot].v = v;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
int cnt = 0;
void dfs(int u, int par) {
  rk[u] = ++cnt;
  L[u] = cnt;
  for(int i = head[u]; ~i; i = edge[i].nextz) {
    int v = edge[i].v;
    if(v == par) continue;
    //cout << u << ' ' << v <<' ' << par << '\n';
    dfs(v, u);
  }
  R[u] = cnt;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  memset(head, -1, sizeof(head));
  int n, m, k; cin >> n >> m >> k;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for(int i = 1; i <= n - 1; i++) {
    int u, v; cin >> u >> v;
    addedge(u, v); addedge(v, u);
  }
  dfs(k, -1);
  //cout << "flag" << '\n';
  for(int i = 1; i <= n; i++) {
    //cout << i << ' ' << rk[i] << '\n';
    update(rk[i], a[i]);
  }
  //cout << "flag" << '\n';
  while(m--) {
    int op, ql, qr; cin >> op >> ql;
    if(op == 1) {
      cin >> qr;
      update(rk[ql], qr);
    } else {
      //cout << ql << ' ' << R[ql] << ' ' << L[ql] << '\n';
      cout << query(R[ql]) - query(L[ql] - 1) << "\n";
    }
  }
  return 0;
}