【学习笔记 / 数据结构】线段树进阶

TheSky233 · 2022-07-17 16:33:32 · 算法·理论

扫描线

【洛谷模板题传送门】

思想

以一条法线从下往上扫描整个图形，图形面积并即为 \sum\limits_{i=1}^{n-1} len_i \times \left(h_{i+1}-h_i\right)，其中 len_i 为当前扫描线长度，h_k 为编号为 k 的线段的 y 坐标。

图示

如图：

从头开始扫。

扫到第二条，计算浅蓝色部分面积。

扫描线当前长度可以用线段树优化（区间修改）。

动态开点

【例题】：HDU6183 - Color it！

题意：给出以下操作：

数据保证 n,m \le 10^6,0\ge c \le 50,y1 \le y2。

思路

开 50 棵线段树维护当前颜色 y 坐标上最小的 x，查询 (x,y1,y2) 时，看那个颜色的线段树 (y1,y2) 区间的值是否 \le x 即可。

因为空间会爆炸，所以不能常规开线段树，用到什么区间就开那个区间的内存即可。

可持久化线段树 / 主席树

【洛谷模板题传送门】

主席树即为可持久化权值线段树，即在保留历史版本的前提下更新线段树，分析可得，修改的节点是一条链且必然产生新的根，未修改的连到过去版本即可。

使用动态开点。

大概长这样：

第 i 棵主席树保存的是离散化后 [1,i] 出现的次数。

区间查询时，运用前缀和的思想确定左右区间，递归求解。

所有笔记的代码：

• https://www.luogu.com.cn/paste/2lwa55o2

画图软件：

• \text{Microsoft Whiteboard}

编辑器：

• \text{CP Editor / Dev-C++}