526互联

loj144&145 dfs序+树状数组/线段树

发布时间 2023-11-22 09:13:00作者: lu1no

[https://loj.ac/p/144](loj144) [https://loj.ac/p/145](loj145) 两题非常相似，一题的权值修改是在点上的，一题的权值修改是在整棵子树上的。 首先我们要了解dfs序，并记录每个节点的子树大小sz，对于一个节点，在dfs序上sz长的区间全都是他的子节点以及他自己。 所以我们将一棵树映射到了一个区间上，并且可以发现，两题分别是点修改+区间修改和区间修改+区间查询，考虑树状数组和线段树。 ``` //loj144 #include using namespace std; typedef long long LL; typedef pair PII; const int mod = 998244353, INF = 1 << 30; const int N = 1e6 + 10; vector e[N]; LL v[N], sz[N]; int dfn[N]; int n, m, r, cnt; LL c[N]; //c数组是指每个下标管理的区间和

//点修 + 区间和
int lowbit(int x)
{
return x & (-x);
}

void add(int p, LL k)
{
for (; p <= n; p += lowbit(p)){
c[p] += k;
}
}

LL ask(int p) // 求[1, p]的前缀和
{
LL s = 0;
for (; p > 0; p -= lowbit(p)){
s += c[p];
}
return s;
}

void dfs(int u, int fa)
{
sz[u] = 1;
dfn[u] = ++ cnt;
for (int v: e[u]){
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}

int main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> m >> r;
for (int i = 1; i <= n; i ++){
cin >> v[i];
}

for (int i = 1; i < n; i ++){
    int a, b;
    cin >> a >> b;
    e[a].push_back(b);
    e[b].push_back(a);
}

dfs(r, 0);
for (int i = 1; i <= n; i ++){
    add(dfn[i], v[i]);
}

while (m --){
    int op; cin >> op;
    if (op == 1){
        int a;
        LL x;
        cin >> a >> x;
        add(dfn[a], x);
    }
    else if (op == 2){
        int a;
        cin >> a;
        LL ans = ask(dfn[a] + sz[a] - 1) - ask(dfn[a] - 1);
        cout << ans << endl;
    }
}
return 0;

}

//loj145

include<bits/stdc++.h>

using namespace std;

define lc p << 1

define rc p << 1 | 1

typedef long long LL;
typedef pair<int, int> PII;
const int mod = 998244353, INF = 1 << 30;
const int N = 1e6 + 10;
int w[N];
int dfn[N], sz[N], v[N];
int n, m, r, cnt;
vector e[N];
struct node{
int l, r;
LL sum, add;
}tr[N * 4];

// 区间修改 + 区间查询
void build(int p, int l, int r)
{
tr[p] = {l, r, w[l], 0};
if (l == r) return;
int m = (l + r) >> 1;
build(lc, l, m);
build(rc, m + 1, r);
tr[p].sum = tr[lc].sum + tr[rc].sum;
}

void pushup(int p)
{
tr[p].sum = tr[lc].sum + tr[rc].sum;
}

void pushdown(int p) // 懒节点下传
{
if (tr[p].add){
tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
tr[lc].add += tr[p].add;
tr[rc].add += tr[p].add;
tr[p].add = 0;
}
}

LL query(int p, int x, int y)
{
if (x <= tr[p].l && tr[p].r <= y) return tr[p].sum;

int m = (tr[p].l + tr[p].r) >> 1;
pushdown(p);
LL sum = 0;
if (x <= m) sum += query(lc, x, y);
if (y > m) sum += query(rc, x, y);
return sum;

}

void update(int p, int x, int y, LL k) //区间更新
{
if (x <= tr[p].l && tr[p].r <= y){
tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
tr[p].add += k;
return;
}
int m = (tr[p].l + tr[p].r) >> 1;
pushdown(p);
if (x <= m) update(lc, x, y, k);
if (y > m) update(rc, x, y, k);
pushup(p);
}

void dfs(int u, int fa)
{
sz[u] = 1;
dfn[u] = ++ cnt;
for (int v: e[u]){
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}

signed main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> m >> r;
for (int i = 1; i <= n; i ++){
cin >> v[i];
}

for (int i = 1; i < n; i ++){
    int a, b;
    cin >> a >> b;
    e[a].push_back(b);
    e[b].push_back(a);
}
dfs(r, 0);

for (int i = 1; i <= n; i ++) w[dfn[i]] = v[i];
build(1, 1, n);

while (m --){
    int op; cin >> op;
    if (op == 1){
        int a;
        LL x;
        cin >> a >> x;
        update(1, dfn[a], dfn[a] + sz[a] - 1, x);
    }
    else if (op == 2){
        int a;
        cin >> a;
        LL ans = query(1, dfn[a], dfn[a] + sz[a] - 1);
        cout << ans << endl;
    }
}
return 0;

}