Fork me on GitHub

线段树类·数据结构的简单运用--基础篇

Posted on | Edited on | In

引言

线段树？顾名思义，就是一个节点维护某个区间的信息的数据结构

线段树有许多迷人的性质，我认为它是最美妙的数据结构了

它可以有很多的扩展变形：动态开点，可持久化线段树，树套树，线段树分治等…

实现方式的不一样也会带来不一样的效果

黑科技技巧更是有很多呢

那就来研究一下吧qwq

前置技能：静态线段树维护

静态线段树维护是一切线段树的基础了

首先，线段树肯定是需要维护区间信息的

最核心的思想就是由小区间信息合并成大区间信息

而通常表示至少长度为2的区间的节点一般有两个子区间，并且长度均匀分配

前置技能0：数据表示方法

在静态线段树中，数据需要怎么储存呢？

首先我们需要一些静态的空间

1
2
const int N = 2e5 + 10;
int val[N << 2]；

这里的$N <<2$是因为实际线段树节点是$2*N-1$个的，为了防止叶子节点爆炸，还需要再多一倍

那么接下来，看看节点的表示方法

首先假设线段树的范围是$[1,n]$，我们默认1号节点维护了$[1,n]$区间信息

剩下对于每个节点t（包含1）

都可以构造一种表示方法使得空间被完美利用

1
2
#define LD (t << 1)
#define RD (t << 1 | 1)

枚举一下情境就会发现这样表示是一定可以把空间利用完全的

前置技能1：维护信息

前置技能1-1：向上维护标记

怎么从左右儿子获得当前区间的全部信息呢？

用一个函数来实现

1
2
3
4
void pushup(int t) {
  //do something
  //example : maxv[t] = max(maxv[LD], maxv[RD]);
}

只需要找到对应的信息合并方式就可以了

如果需要维护的信息比较复杂，有一个办法：分解成很多个可以维护简单信息

前置技能1-2：向下传递标记

这个思想是因为每次我们不能把左右标记传到叶子节点

因为这样的话复杂度就炸裂了

所以考虑怎么优化？

我们需要用到一个叫做lazy标记的东西

这个东西可以储存我们还没有下放的标记

可以让我们在用到这个区间信息的时候再来慢慢下传

有一个结论，任意一个区间在线段树上最多被分成log个区间

所以复杂度就有保证了

本人习惯实现两个函数分别表示维护当前层的更新信息和将标记下传到子节点

1
2
3
4
5
6
7
8
9
10
11
12
int lazy[N << 2];
void pushnow(int t, int tag) {
  //用 tag 更新 t 的信息
  //维护 tag 和 lazy[t] 
}
void pushdown(int t) {
  if (lazy[t]) {
    pushnow(LD, lazy[t]);
    pushnow(RD, lazy[t]);
    lazy[t] = 0;
  }
}

前置技能2：建树

建树，顾名思义，就是把这个线段树给建出来

具体实现方法是递归建树，因为线段树的左右儿子节点维护的区间的并就是当前节点维护的区间

那么我们就可以递归分配左右儿子区间了

因为要保证树高，所以每次分配的时候以当前区间$[l,r]$的中间节点$mid = (l + r) >> 1$作为分界线

如果建树的时候需要初始化一些信息就随机应变咯

1
2
3
4
5
6
7
8
9
10
void build(int t, int l, int r) {
  if (l == r) {
    //do something
    return;
  }
  int mid = (l + r) >> 1;
  build(LD, l, mid);
  build(RD, mid + 1, r);
  pushup(t);
}

前置技能3：单点修改

唔，现在需要改一个点的信息？怎么办？

可以直接按照区间的范围递归找到那个你需要找的点，因为线段树最多只有log层，所以复杂度是有保证的

1
2
3
4
5
6
7
8
9
10
void modify_point(int t, int l, int r, int pos, int tag) {
  if (l == r) {
    pushnow(t, tag);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) modify_point(LD, l, mid, pos, tag);
  else modify_point(RD, mid + 1, r, pos, tag);
  pushup(t);
}

前置技能4：单点查询

现在要查询一个点的信息？

有些毒瘤手段先不说……

就暴力递归就可以了，和单点查询一样的思路

1
2
3
4
5
6
7
void query_point(int t, int l, int r, int pos) {
  if (l == r) return something_you_need;
  int mid = (l + r) >> 1;
  if (pos <= mid) return query_point(LD, l, mid, pos);
  else return query_point(RD, mid + 1, r, pos);
  //询问的时候不需要更新当前的信息，因为没有改变qwq
}

前置技能5：区间修改

比单点修改稍微复杂一点，现在我们需要修改一整个区间的信息？怎么办？

假设我们在考虑一个节点t，并且需要修改的区间$[ql,qr]$并没有包含t的区间$[l,r]$怎么办？

如果$qr\le mid$，则这个修改只对t的左边儿子区间有影响，向左递归问题

如果$mid<ql$，则这个修改只对t的右边儿子区间有影响，向右递归问题

还剩一种情况，就是t的左右区间各包含了一部分的$[ql,qr]$怎么办？，那么就同时暴力递归到左右两个子区间就可以了，因为有一个刚才提到的结论：任意一个区间在线段树上最多被分成log个区间

所以复杂度还是有保证的

注意一定要在递归成子区间之前下传标记并更新子区间信息哦！！，不然的话可能会出现神奇的错误（比如说当下传的时候有一些特殊的限制…..过会再讲）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void modify_segment(int t, int l, int r, int ql, int qr, int tag) {
  if (ql <= l && r <= qr) {
    pushnow(t, tag);//初学者可以仔细理解一下这个pushnow的作用,dalao跳过
    return;
  }
  pushdown(t);//向下传递一波标记
  int mid = (l + r) >> 1;
  if (qr <= mid) modify_segment(LD, l, mid, ql, qr, tag);
  else if (ql > mod) modify_segment(RD, mid + 1, r, ql, qr, tag);
  else {
    modify_segment(LD, l, mid, ql, mid, tag);
    modify_segment(RD, mid + 1, r, mid + 1, qr, tag);
  }
  pushup(t);//向上更新一波信息
}

前置技能6：区间查询

只要理解了区间修改查询就不是问题啦

还需要注意一下，因为区间查询的时候下传的标记都是完整的（覆盖了整个区间），所以区间信息不需要重新向上维护，因为$pushnow$函数已经把这个区间的信息维护了

1
2
3
4
5
6
7
8
9
10
11
12
13
int query_segment(int t, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return something_you_need;
  pushdown(t);
  int mid = (l + r) >> 1;
  if (qr <= mid) return query_segment(LD, l, mid, ql, qr);
  else if (ql > mid) return query_segment(RD, mid + 1, r, ql, qr);
  else {
    int res;
    //合并res和query_segment(LD, l, mid, ql, mid)的信息
    //合并res和query_segment(RD, mid + 1, r, mid + 1, qr)的信息
  	return res;
  }
}

前置技能拓展：动态开点线段树

动态开点是什么？就是不给每个节点分配固定的内存

因为如果分配内存可能会对内存空间造成极大的浪费

所以我们每次只给需要用到的区间分配内存并建立节点

应用于线段树合并和主席树和一些神奇的东西

因为主席树和一般的动态开点线段树有不小的区别，所以在这里不包含主席树的维护方式，后面单独讲解

前置技能拓展0：数据表示方法

因为线段树不再是静态的了，显然是不能给每个节点分配静态的儿子

所以考虑用数组记录下来

因为需要动态分配内存，所以我们还需要一个指针记录分配到哪里了，并且需要一个指针记录根节点是什么

1
2
int rt, tot = 0;//rt 根节点 tot 当前指针
int ls[N], rs[N]，;//一个节点的左右儿子

前置技能拓展1：插入节点信息

和静态线段树略有不同的是

动态开点线段树需要判断当前节点存不存在并分配内存

而且单次只会插入一个位置的信息

1
2
3
4
5
6
7
8
9
10
11
void insert(int &t, int l, int r, int pos) {
  if (!t) t = ++tot;
  if (l == r) {
    //do something
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) insert(ls[t], l, mid, pos);
  else insert(rs[t], mid + 1, r, pos);
  pushup(t);
}

前置技能拓展2：动态开点线段树的合并

有的时候我们在维护一些联通块的信息的时候需要用到动态开点线段树的合并

这样就可以快速合并两个联通块的信息了

这个算法的核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isleaf(int t) {
  return !ls[t] && !rs[t];
}
int merge(int x, int y) {
  if (!x || !y) return x + y;
  if (isleaf(x) && isleaf(y)) {
    //把y的信息合并到x上
    return x;
  }
  pushdown(x), pushdown(y);
  ls[x] = merge(ls[x], ls[y]);
  rs[x] = merge(rs[x], rs[y]);
  pushup(x);
  return x;
}

具体来说就是如果当前两个节点都存在，就需要暴力合并两个节点的左儿子和右儿子

如果只有一个节点存在就可以直接返回了

需要特别注意一下如果两个节点都存在但是都没有左右儿子直接合并儿子会丢失信息，这个时候就需要直接合并了

暴力合并那一步看起来复杂度是错的

但是仔细想一想这个算法每一次运行用$O(1)$的代价删除1个节点

因为是动态开点，所以最开始最多有$nlog(n)$个节点，合并完后节点数是$[1,n]$的级别

所以复杂度是$O(nlog(n))$

接下来进入正题

各种各样的线段树类别

1.普通线段树

很简单的线段树，维护的区间就是在原序列中的区间

可以支持一些简单的操作：

  1. 区间修改（加，减，乘）
  2. 区间查询（和，最大值，最小值，gcd，lcm）

注意一下维护的顺序就行了，其实并不难

其实对于不同的操作，需要修改的只有维护信息的三个函数：$pushup,pushdown,pushnow$

也可以支持一些不那么简单的操作：

  1. 区间修改（区间开根号，区间位运算，区间取max，区间取min）
  2. 区间查询（中位数，带权中位数，历史最大值）

需要用到一些比较黑科技的东西，我也不太会

2.值域线段树

研究明白了值域线段树就可以初步感受到线段树的奥妙了

首先这里的值域不要过于死板地理解

值域可以是数的大小，时间，权值，甚至是相对大小关系？

存在无限的可能

值域线段树小探究：全序集维护

来科普一些简单的全序集维护知识吧

维护全序集，大概是需要支持：

  1. 插入一个数
  2. 删除一个数
  3. 查询一个数的排名
  4. 查询排名是k的数
  5. 查询一个数的前驱
  6. 查询一个数的后继

首先轻轻松松地离线离散化一下

然后我们发现实际上需要支持地操作只有前四个，因为后两个都是可以通过前面转化得到的

来看看怎么实现，因为线段树维护的是值域，所以我们只需要记录每个数的出现次数就可以了

1
int siz[N];

接下来：

简单的pushup
1
2
3
void pushup(int t) {
  siz[t] = siz[LD] + siz[RD];
}
插入
1
2
3
4
5
6
7
8
9
10
void insert(int t, int l, int r, int vl) {
  if (l == r) {
    siz[t]++;
    return;
  }
  int mid = (l + r) >> 1;
  if (vl <= mid) insert(LD, l, mid, vl);
  else insert(RD, mid + 1, r, vl);
  pushup(t);
}
删除

和插入差不多，就是$siz_t$减少1就可以了

查询一个数的排名

每次如果当前节点大小大于mid就需要加上左边的数的个数

1
2
3
4
5
6
int rank(int t, int l, int r, int vl) {
  if (l == r) return 1;
  int mid = (l + r) >> 1;
  if (vl <= mid) return rank(LD, l, mid, vl);
  else return siz[LD] + rank(RD, mid + 1, r, vl);
}
查询第k小

每次走到一个节点根据左儿子的大小判断一下该向哪边递归就可以了

注意返回的是离散后的下标，需要还原成本身的值

1
2
3
4
5
6
int kth(int t, int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (siz[LD] >= k) return kth(LD, l, mid, k);
  else return kth(RD, mid + 1, r, k - siz[LD]);//变成计算右儿子区间排名是k - siz[LD]的数
}
前驱&后继
1
2
3
4
5
6
int pre(int x) {//传入离散后的下标
  return kth(1, 1, n, rank(1, 1, n, x) - 1);
}
int nxt(int x) {//传入离散后的下标
  return kth(1, 1, n, rank(1, 1, n, x + 1));
}

比平衡树好写到不知道哪里去有没有qwq？

值域线段树虽然没有办法维护在原序列中的大小关系

但是却可以优化许多根值域有关的计算过程，常见于线段树优化DP或线段树分治

值域线段树还有许多奇妙的性质，后面慢慢探究

基于线段树实现的数据结构

1.主席树

也叫做可持久化线段树

最大的特点是必须离线且不支持修改，只支持查询

本身为什么叫可持久化线段树呢？

因为每棵树代表的节点维护了一个前缀的信息

这样就很方便进行区间查询（差分的思想）

但是如果暴力开线段树会发生什么？

空间复杂度$O(n^2)$不可承受

观察一下我们要维护的东西

因为是一个前缀，所以有很大一部分信息都是可以从前面一棵树继承过来的

那么我们考虑优化这个过程

事实证明，每次我们插入一个信息实际上需要修改的只有一条长度是$log(n)$的链

那么就把所有不需要新建的节点直接继承过来

因此需要动态开点

实现起来是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
void insert(int &t, int last, int l, int r, int pos) {
  t = ++tot;
  //t 从 last 继承一些信息
  if (l == r) return;
  ls[t] = ls[last];//继承儿子信息
  rs[t] = rs[last];
  int mid = (l + r) >> 1;
  //判断一下需要新建哪个节点？
  if (pos <= mid) insert(ls[t], ls[last], l, mid, pos);
  else insert(rs[t], rs[last], mid + 1, r, pos);
  pushup(t);
}

通常主席树维护的信息都是前缀可减的，不然是没有办法查询的

在这里举两个简单的例子，把刚才维护全序集的rank和kth照搬到区间上

其实很简单，只需要每次查询的时候做差就可以了

1
2
3
4
5
6
7
8
9
10
11
12
int rank(int t, int last, int l, int r, int vl) {
  if (l == r) return 1;
  int mid = (l + r) >> 1;
  if (vl <= mid) return rank(ls[t], ls[last], l, mid, vl);
  else return siz[ls[t]] - siz[ls[last]] + rank(rs[t], rs[last], mid + 1, r, vl);
}
int kth(int t, int last, int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) >> 1, sizl = siz[ls[t]] - siz[ls[last]];
	if (k <= sizl) return kth(ls[t], ls[last], l, mid, k);
  else return kth(rs[t], rs[last], mid + 1, r, k - sizl);
}

可以发现主席树维护和权值线段树的维护区别就只有一个范围的限制

但是主席树还有一些奇妙的用途？

先说几个常见的主席树套路：

可持久化原数组顺序，内层使用权值线段树

这样的主席树应该是最常见的

可以解决一些和至于有关的区间查询问题 ，就是权值线段树的简单扩展

可持久化值域，内层使用原数组顺序

这个思路很神奇

是从这道题中学习到的

有的时候我们不能直接维护有关值域的信息但是如果知道了当前的值是可以很方便地维护出原数组信息的时候

我们就可以考虑用可持久化值域的方法，并在内层树中消除掉值域的影响进行解题

主席树还有一些神奇的奇技淫巧……技巧篇给予讲解吧

2.树套树

感觉很套路但是绝对不想写的东西

其实理解起来并不难

有很多线段树套线段树，线段树套平衡树，主席树套线段树，线段树套主席树之类的东西

一般是一眼就告诉你要树套树，然后就不想写了

在这里给一个沙雕题的example

给你一个矩阵，让你每次把一个矩形的中心节点权值改变乘成矩形中最大最小权值的平均数

首先肯定是树套树维护的

先把变量定义好

1
2
3
#define LD(t) (t << 1) 
#define RD(t) (t << 1 | 1)
int maxv[N << 2][N << 2], minv[N << 2][N << 2];

然后把内层的pushup函数写一写

1
2
3
4
void pushup(int t, int id) {
  maxv[id][t] = max(maxv[id][LD(t)], maxv[id][RD(t)]);
  minv[id][t] = min(minv[id][LD(t)], minv[id][RD(t)]);
}

对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度$O(log(n))$

1
2
3
4
5
6
7
8
9
10
11
void modify_y(int t, int l, int r, int pos, int vl, int id) {
  if (l == r) {
    minv[id][t] = vl;
    maxv[id][t] = vl;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) modify_y(LD(t), l, mid, pos, vl, id);
  else modify_y(RD(t), mid + 1, r, pos, vl, id);
  pushup(t, id);
}

然后如果要更新不是叶子节点外层树对应的内层树怎么办？

考虑从外层树的儿子节点合并对应的信息，只需要修改有影响的一条链，复杂度$O(nlog(n))$

1
2
3
4
5
6
7
8
9
10
11
void update_y(int t, int l, int r, int pos, int id) {
  if (l == r) {
    minv[id][t] = min(minv[LD(id)][t], minv[RD(id)][t]);
    maxv[id][t] = max(maxv[LD(id)][t], maxv[RD(id)][t]);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) update_y(LD(t), l, mid, pos, id);
  else update_y(RD(t), mid + 1, r, pos, id);
  pushup(t, id);
}

内层树的查询就简单而套路了

1
2
3
4
5
6
7
8
9
10
11
pi query_y(int t, int l, int r,int ql, int qr, int id) {
  if (ql <= l && r <= qr) return pi(maxv[id][t], minv[id][t]);
  int mid = (l + r) >> 1;
  if (qr <= mid) return query_y(LD(t), l, mid, ql, qr, id);
  else if (ql > mid) return query_y(RD(t), mid + 1, r, ql, qr, id);
  else {
    pi ansl = query_y(LD(t), l, mid, ql, mid, id);
    pi ansr = query_y(RD(t), mid + 1, r, mid + 1, qr, id);
    return pi(max(ansl.first, ansr.first), min(ansl.second, ansr.second));
  }
}

外层树修改的时候需要判断一下当前节点是不是叶子，如果是叶子直接更新y

否则先递归问题再调用$update_y$函数

1
2
3
4
5
6
7
8
9
10
void modify_x(int t, int l, int r, int x, int y, int vl) {
  if (l == r) {
    modify_y(1, 1, n, y, vl, t);
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) modify_x(LD(t), l, mid, x, y, vl);
  else modify_x(RD(t), mid + 1, r, x, y, vl);
  update_y(1, 1, n, y, t);
}

外层树的查询就是如果被查询区间包含调用内层查询，否则递归问题，简单而套路

1
2
3
4
5
6
7
8
9
10
11
pi query_x(int t, int l, int r, int xl, int xr, int yl, int yr) {
  if (xl <= l && r <= xr) return query_y(1, 1, n, yl, yr, t);
  int mid = (l + r) >> 1;
  if (xr <= mid) return query_x(LD(t), l, mid, xl, xr, yl, yr);
  else if (xl > mid) return query_x(RD(t), mid + 1, r, xl, xr, yl, yr);
  else {
    pi ansl = query_x(LD(t), l, mid, xl, mid, yl, yr);
    pi ansr = query_x(RD(t), mid + 1, r, mid + 1, xr, yl, yr);
    return pi(max(ansl.first, ansr.first), min(ansl.second, ansr.second));
  }
}

树套树也有很多变形

但无非就是外层处理到内层递归的简单套路，多写几道题体会一下就可以了

只要代码实现练习到位是很简单的

所以千万不要怕这个东西

3.李超树

李超树是一种用来维护线段/函数的神奇数据结构

简单李超树支持查询一个x对应的所有y值的相关信息

用线段树来存储每个区间的相对最优解

这里用到了一个永久化标记的思想，这个在技巧篇讲……

这个东西很好啊，每个节点记录区间的相对最优解之后

直接dfs到叶子节点把路径上经过的所有节点的权值全部取max就可以了

正确性非常显然，但是怎么维护呢？

我们假设当前要更新的是一个节点$p_t$，那么如果$p_t$的k大于拿来更新的$val$的k

如果在$mid$处$p_t$大于$val$，那么显然在$[mid+1,r]$这个区间里val不可能比$p_t$更优

所以就把$val$递归到左区间更新

如果在$mid$处$p_t$小于$val$，那么在$[l,mid]$这个区间$p_t$不可能比$val$更优

所以就把$p_t$递归到右区间，再把$p_t$替换成val就可以了

只需要按照k的大小关系分类讨论一下就可以了

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
struct Line {
  double k, b;
} p[(MAXN << 2) + 10];
double calc(int x, Line a) {
  return a.k * (double) x + a.b;
}
bool cmp(int x, Line a, Line b) {
  return calc(x, a) > calc(x, b); 
}
void modify(int t, int l, int r, Line vl) {
  if (l == r) {
    if (cmp(l, vl, p[t])) p[t] = vl;
    return;
  }
  int mid = (l + r) >> 1;
  if (p[t].k <= vl.k) {
    if (cmp(mid, vl, p[t])) {
      modify(LD, l, mid, p[t]);
      p[t] = vl;
    } else {
      modify(RD, mid + 1, r, vl);
    }
  } else {
    if (cmp(mid, vl, p[t])) {
      modify(RD, mid + 1, r, p[t]);
      p[t] = vl;
    } else {
      modify(LD, l, mid, vl);
    }
  }
}
double query(int t, int l, int r, int pos) {
  if (l == r) return calc(pos, p[t]);
  int mid = (l + r) >> 1;
  if (pos <= mid) return max(calc(pos, p[t]), query(LD, l, mid, pos));
  else  return max(calc(pos, p[t]), query(RD, mid + 1, r, pos));
}

4.ZKW线段树

我觉得严格意义来说这个算是奇技淫巧