数据结构：线段树再再续

Posted on Edited on In Views:

在前三篇博客的对线段树的介绍的基础上，我们再补充一些与线段树相关的内容。分为两部分

  • 线段树的优化建图
  • 猫树

线段树优化建图

在建图连边的过程中，我们有时会碰到这种题目，一个点向一段连续的区间中的点连边或者一个连续的区间向一个点连边，如果我们真的一条一条连过去，那一旦点的数量多了复杂度就爆炸了，这里就需要用线段树的区间性质来优化我们的建图了。

下面是一个线段树。

图1

每个节点都代表了一个区间，假设我们要向区间 连边。

图2

在一些题目中，还会出现一个区间连向一个点的情况，则我们将上面第一张图的有向边全部反过来即可，上面的树叫做入树，下面这个叫做出树。

图3

参考例题：

题目大意：

有 个点、 次操作。每一种操作为以下三种类型中的一种：

  • 操作一：连一条 的有向边，权值为 。
  • 操作二：对于所有 连一条 的有向边，权值为 。
  • 操作三：对于所有 连一条 的有向边，权值为 。

求从点 到其他点的最短路。

。

参考代码：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

using pil = pair<int, ll>;
using pli = pair<ll, int>;

int n, q, s, tot, rt1, rt2;
int pos[N];
ll dis[N << 3];
vector<pil> e[N << 3];
bitset<(N << 3)> vis;

struct seg {
  int l, r, lson, rson;
} t[N << 3];

inline int ls(int u) {  // 左儿子
  return t[u].lson;
}

inline int rs(int u) {  // 右儿子
  return t[u].rson;
}

void build(int &u, int l, int r) {  // 动态开点建造入树
  u = ++tot;
  t[u] = seg{l, r};
  if (l == r) {
    pos[l] = u;
    return;
  }
  int mid = (l + r) >> 1;
  build(t[u].lson, l, mid);
  build(t[u].rson, mid + 1, r);
  e[u].emplace_back(ls(u), 0);
  e[u].emplace_back(rs(u), 0);
}

void build2(int &u, int l, int r) {  // 动态开点建造出树
  if (l == r) {
    u = pos[l];
    return;
  }
  u = ++tot;
  t[u] = seg{l, r};
  int mid = (l + r) >> 1;
  build2(t[u].lson, l, mid);
  build2(t[u].rson, mid + 1, r);
  e[ls(u)].emplace_back(u, 0);
  e[rs(u)].emplace_back(u, 0);
}

void add1(int u, int lr, int rr, int v, ll w) {  // 点向区间连边
  if (lr <= t[u].l && t[u].r <= rr) {
    e[v].emplace_back(u, w);
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (lr <= mid) {
    add1(ls(u), lr, rr, v, w);
  }
  if (rr > mid) {
    add1(rs(u), lr, rr, v, w);
  }
}

void add2(int u, int lr, int rr, int v, ll w) {  // 区间向点连边
  if (lr <= t[u].l && t[u].r <= rr) {
    e[u].emplace_back(v, w);
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (lr <= mid) {
    add2(ls(u), lr, rr, v, w);
  }
  if (rr > mid) {
    add2(rs(u), lr, rr, v, w);
  }
}

void dij(int S) {
  priority_queue<pli, vector<pli>, greater<pli> > q;
  int tot = (n << 2);
  for (int i = 1; i <= tot; ++i) {
    dis[i] = 1e18;
  }
  dis[S] = 0;
  q.emplace(dis[S], S);
  while (!q.empty()) {
    pli fr = q.top();
    q.pop();
    int u = fr.second;
    if (vis[u]) continue;
    for (pil it : e[u]) {
      int v = it.first;
      ll w = it.second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.emplace(dis[v], v);
      }
    }
  }
}

int main() {
  scanf("%d%d%d", &n, &q, &s);
  build(rt1, 1, n);
  build2(rt2, 1, n);
  for (int i = 1, op, u; i <= q; ++i) {
    scanf("%d%d", &op, &u);
    if (op == 1) {
      int v;
      ll w;
      scanf("%d%lld", &v, &w);
      e[pos[u]].emplace_back(pos[v], w);
    } else if (op == 2) {
      int l, r;
      ll w;
      scanf("%d%d%lld", &l, &r, &w);
      add1(rt1, l, r, pos[u], w);
    } else {
      int l, r;
      ll w;
      scanf("%d%d%lld", &l, &r, &w);
      add2(rt2, l, r, pos[u], w);
    }
  }
  dij(pos[s]);
  for (int i = 1; i <= n; ++i) {
    if (dis[pos[i]] == 1e18) {
      printf("-1 ");
    } else {
      printf("%lld ", dis[pos[i]]);
    }
  }
  return 0;
}

拓展 - 猫树

众所周知线段树可以支持高速查询某一段区间的信息和，比如区间最大子段和，区间和，区间矩阵的连乘积等等。

但是有一个问题在于普通线段树的区间询问在某些毒瘤的眼里可能还是有些慢了。

简单来说就是线段树建树的时候需要做 次合并操作，而每一次区间询问需要做 次合并操作，询问区间和这种东西的时候还可以忍受，但是当我们需要询问区间线性基这种合并复杂度高达 的信息的话，此时就算是做 次合并有些时候在时间上也是不可接受的。

而所谓「猫树」就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。

构造一棵这样的静态线段树需要 次合并操作，但是此时的查询复杂度被加速至 次合并操作。

在处理线性基这样特殊的信息的时候甚至可以将复杂度降至 。

原理

在查询 这段区间的信息和的时候，将线段树树上代表 的节点和代表 这段区间的节点在线段树上的 LCA 求出来，设这个节点 代表的区间为 ，我们会发现一些非常有趣的性质：

  1. 这个区间一定包含 。显然，因为它既是 的祖先又是 的祖先。

  2. 这个区间一定跨越 的中点。由于 是 和 的 LCA，这意味着 的左儿子是 的祖先而不是 的祖先， 的右儿子是 的祖先而不是 的祖先。因此， 一定在 这个区间内， 一定在 这个区间内。

有了这两个性质，我们就可以将询问的复杂度降至 了。

实现

具体来讲我们建树的时候对于线段树树上的一个节点，设它代表的区间为 。

不同于传统线段树在这个节点里只保留 的和，我们在这个节点里面额外保存 的后缀和数组和 的前缀和数组。

这样的话建树的复杂度为 同理空间复杂度也从原来的 变成了 。

下面是最关键的询问了。

如果我们询问的区间是 那么我们把代表 的节点和代表 的节点的 LCA 求出来，记为 。

根据刚才的两个性质， 在 所包含的区间之内并且一定跨越了 的中点。

这意味这一个非常关键的事实是我们可以使用 里面的前缀和数组和后缀和数组，将 拆成 从而拼出来 这个区间。

而这个过程仅仅需要 次合并操作！

不过我们好像忽略了点什么？

似乎求 LCA 的复杂度似乎还不是 ，暴力求是 的，倍增法则是 的，转 ST 表的代价又太大……

堆式建树

具体来将我们将这个序列补成 的整次幂，然后建线段树。

此时我们发现线段树上两个节点的 LCA 编号，就是两个节点二进制编号的最长公共前缀 LCP。

稍作思考即可发现发现在 和 的二进制下 lcp(x,y)=x>>log[x^y]。

所以我们预处理一个 log 数组即可轻松完成求 LCA 的工作。

这样我们就构建了一个猫树。

由于建树的时候涉及到求前缀和和求后缀和，所以对于线性基这种虽然合并是 但是求前缀和却是 的信息，使用猫树可以将静态区间线性基从 优化至 的复杂度。