跳转至

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

  • 线段树中节点的数量取决于insert的数量
  • merge函数内本质是修改节点的属性(sum,lc,rc)，并没有新增节点
  • 每调用一次insert，就有一条从根走到叶子节点长度为\(logn\)的路径，就会新建\(logn\)个节点
  • insert一共被调用了\(4m\)次，故线段树开\(4nlogn\)
1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
const int N = 1E5 + 10;
const int LOGN = 20;
...
struct Node{
    int lc, rc;
    int ma;
} tree[4 * LOGN * N];
  • 使用树上差分时，注意lca和lca的父亲是减法，不能跟两节点x、y一样做加法
1
2
3
4
5
6
7
8
9
for(int i = 1; i <= m; i++){
    int x, y, z, lca;
    cin >> x >> y >> z;
    lca = getLCA(x, y);
    insert(x, 1, N, z, 1);
    insert(y, 1, N, z, 1);
    insert(lca, 1, N, z, -1);
    insert(anc[lca][0], 1, N, z, -1);
}
  • 线段树合并需要多棵线段树在同一个数组内，否则“return py”向一个数组返回了另一个数组的下标，无意义
  • 小技巧：一个线段树数组中可以通过保留多个根节点，在同一个数组中开多棵线段树。还省空间，每棵线段树的空间是动态的。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 错误
Node tree[N][LOGN * N];
// 正确
Node tree[4 * LOGN * N];

int merge(int px, int py, int l, int r){
    if(px == 0) return py;
    if(py == 0) return px;
    if(l == r){
        tree[px].ma += tree[py].ma;
        return px;
    }
    int mid = (l + r) >> 1;
    tree[px].lc = merge(tree[px].lc, tree[py].lc, l, mid);
    tree[px].rc = merge(tree[px].rc, tree[py].rc, mid + 1, r);
    push_up(px);
    return px;
}