跳转至

dfs序线段树

线段树可以以 \(O(\log n)\) 的时间复杂度在线性数据结构上进行区间修改和查询。若要在树上对整个子树进行修改和查询，就可以使用 \(dfs\) 序线段树使操作的时间复杂度由 \(O(n)\) 降为 \(O(\log n)\) 。

该算法利用了 \(dfs\) 时，同一棵子树中每个节点的 dfs 序是连续的。若用访问时间代替节点本身的编号，就可以把一棵子树上所有的节点转换为一个连续的区间，就可以用线段树进行维护了。

例题

U142060 【模板】dfs序线段树

代码中，\(pre[u]\) 表示第 \(u\) 个节点的访问时间，\(id[t]\) 表示访问时间为t的节点编号(在线段树的 \(build\_tree\) 中使用)，\(sz[u]\) 表示以节点 \(u\) 为根的子树所包含的节点个数。

这样，操作以节点 \(u\) 为根的子树，就转化为了操作区间 \([pre[u], pre[u]+sz[u]-1]\) 。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 2E5 + 10;

inline int lc(int x){ return x << 1; }
inline int rc(int x){ return x << 1 | 1; }

int n, m, nn;
int w[N], id[N], dfn[N], sz[N], deep[N];
int sum[4 * N], tag[4 * N];

vector<int> adj[N];

void dfs(int u, int f){

    id[++nn] = u;
    dfn[u] = nn;
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }

}

void move_tag(int p, int l, int r, int t){
    sum[p] += t * (r - l + 1);
    tag[p] += t;
}

void push_up(int p){
    sum[p] = sum[lc(p)] + sum[rc(p)];
}

void push_down(int p, int l, int r){
    int mid = (r + l) >> 1;
    move_tag(lc(p), l, mid, tag[p]);
    move_tag(rc(p), mid + 1, r, tag[p]);
    tag[p] = 0;
}

void build(int p, int l, int r){

    if(l == r){
        sum[p] = w[id[l]];
        return;
    }

    int mid = (l + r) >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);

    push_up(p);

}

void add(int p, int l, int r, int ql, int qr, int k){

    if(ql <= l && r <= qr){
        sum[p] += k * (r - l + 1);
        tag[p] += k;
        return;
    }

    push_down(p, l, r);
    int mid = (l + r) >> 1;
    if(ql <= mid) add(lc(p), l, mid, ql, qr, k);
    if(qr > mid)  add(rc(p), mid + 1, r, ql, qr, k);
    push_up(p);

}

int query(int p, int l, int r, int ql, int qr){

    if(ql <= l && r <= qr){
        return sum[p];
    }

    push_down(p, l, r);
    int mid = (l + r) >> 1, res = 0;
    if(ql <= mid) res += query(lc(p), l, mid, ql, qr);
    if(qr > mid)  res += query(rc(p), mid + 1, r, ql, qr);

    return res;
}

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n - 1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }

    dfs(1, 0);
    build(1, 1, n);

    while(m--){
        int op, x, d;
        cin >> op >> x;
        if(op == 1){
            cin >> d;
            add(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, d);
        }
        else{
            cout << query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) << endl;
        }
    }

    return 0;
}

P6584 重拳出击

未AC