线段树优化建图学习笔记

• $线段树优化建图的作用$线段树优化建图的作用

$问题$问题

有 $N$N 个节点, 执行 $M$M 次以下连边操作, 倩输出以 $s$s 为起点的单源最短路:

1. $a\to b$a→b
2. $a\to [l,r]$a→[l,r]
3. $[l,r]\to b$[l,r]→b

$a,b,l,r\in [1,10^6]$a,b,l,r∈[1,106]

若暴力建图, 时空复杂度高达 $O\left(M{N}^2\right)$O(MN2),
于是 线段树优化建图 诞生了 .

• $线段树优化建图的实现$线段树优化建图的实现

建立两个 线段树, 分别为 入树 和 出树, 暂且称两者为 $In\_t$In_t, $Out\_t$Out_t .
按照以下 $5$5 条规则即可建出一个边数为 $O\left(MlogN\right)$O(MlogN) 的 “优秀” 图 .

1. $In\_t$In_t 从 下往上 连边, $Out\_t$Out_t 则从 上往下 连边 .
2. $In\_t$In_t 与 $Out\_t$Out_t 的叶子结点都对应 原节点, 所以两颗树的对应叶子结点之间连上 边权 为 $0$0 的 无向边.
3. 对于上述问题中的 $1$1 操作, $In\_t$In_t 中 $a$a 节点直接连向 $Out\_t$Out_t 中的 $b$b 节点 .
4. 对于上述问题中的 $2$2 操作, $In\_t$In_t 中 $a$a 节点连向 $Out\_t$Out_t 中 $logN$logN 个对应区间节点 .
5. 对于上述问题中的 $3$3 操作, $In\_t$In_t 中的 $logN$logN 个区间节点向 $Out\_t$Out_t 中的 $b$b 连边 .

某些问题只需要实现 $2$2, $3$3 操作其中之一 ,

• 若实现 $2$2 操作, 建一个 出树 即可 .
• 若实现 $3$3 操作, 建一个 入树 即可 .

题外话: 由于初学时不太清楚, 下方例题 $2$2 无脑建了两颗树, 导致 $2$2 个点始终超时 …

• $线段树优化建图的相关代码$线段树优化建图的相关代码

1. $建图$建图

这里给出 入树 建边, 出树 同理 (以下皆为动态开点) .

void Build(int &k, int l, int r, int opt){
        k = ++ node_cnt;
        T[k].l = l, T[k].r = r;
        if(l == r){
                Mp[opt][l] = k; // 原图中 l 对应线段树节点 k.
                return ;
        }
        int mid = l+r >> 1;
        Build(T[k].lt, l, mid, opt), Build(T[k].rt, mid+1, r, opt);
        if(opt == 0) Add(T[k].lt, k), Add(T[k].rt, k); // In_t 建边.
        else Add(k, T[k].lt), Add(k, T[k].rt);	// Out_t 
}

2. $叶子节点连边$叶子节点连边

注意是出树叶子到入树叶子连边 .

void Connect_0(int k){
        int l = T[k].l, r = T[k].r;
        if(l == r){
                Add(Mp[1][l], Mp[0][l]);
                return ;
        }
        Connect_0(T[k].lt), Connect_0(T[k].rt);
}

3. $点\to 区间连边$点→区间连边

void Connect(int k, int u, int L, int R){
        int l = T[k].l, r = T[k].r;
        if(L <= l && r <= R){
                if(l == r && u == Mp[1][l]) return ; // 判重边.
                Add(u, k); return ;
        }
        int mid = l+r >> 1;
        if(L <= mid) Connect(T[k].lt, u, L, R);
        if(R > mid) Connect(T[k].rt, u, L, R);
}

4. $区间\to 点连边$区间→点连边

void Connect_2(int k, int L, int R, int v){
        int l = T[k].l, r = T[k].r;
        if(L <= l && r <= R){
                if(l == r && v == Mp[0][l]) return ; //判重边.
                Add(k, v); return ;
        }
        int mid = l+r >> 1;
        if(L <= mid) Connect_2(T[k].lt, u, L, R);
        if(R > mid) Connect_2(T[k].rt, u, L, R);
}

5. $最短路$最短路

略.

• $线段树优化建图的应用$线段树优化建图的应用

1. NOI2019 弹跳
2. SNOI2017炸弹