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

## 扫描线 [【洛谷模板题传送门】](https://www.luogu.com.cn/problem/P5490) ### 思想 以一条法线从下往上扫描整个图形，图形面积并即为 $\sum\limits_{i=1}^{n-1} len_i \times \left(h_{i+1}-h_i\right)$，其中 $len_i$ 为当前扫描线长度，$h_k$ 为编号为 $k$ 的线段的 $y$ 坐标。 ### 图示  如图： $\texttt{Step 1:}$  从头开始扫。 $\texttt{Step 2:}$  扫到第二条，计算浅蓝色部分面积。 $\texttt{Step 3-4}$   扫描线当前长度可以用线段树优化（区间修改）。 ## 动态开点 【例题】：HDU6183 - Color it！ 题意：给出以下操作： - $\texttt{0}$，代表清空所有颜色。 - $\texttt{1 x y c}$ 代表在坐标 $(x,y)$ 涂上第 $c$ 种颜色。 - $\texttt{2 x y1 y2}$ 代表统计 $x$ 轴上 $(1,x)$ 和 $y$ 轴上 $ (y1,y2)$ 的颜色数，一个点可以有多种颜色. - $\texttt{3}$ 代表结束。 数据保证 $n,m \le 10^6,0\ge c \le 50,y1 \le y2$。 ### 思路 开 $50$ 棵线段树维护当前颜色 $y$ 坐标上最小的 $x$，查询 $(x,y1,y2)$ 时，看那个颜色的线段树 $(y1,y2)$ 区间的值是否 $\le x$ 即可。 因为空间会爆炸，所以不能常规开线段树，用到什么区间就开那个区间的内存即可。 ## 可持久化线段树 / 主席树 [【洛谷模板题传送门】](https://www.luogu.com.cn/problem/P3834) 主席树即为可持久化权值线段树，即在保留历史版本的前提下更新线段树，分析可得，修改的节点是一条链且必然产生新的根，未修改的连到过去版本即可。 使用动态开点。 大概长这样： 第 $i$ 棵主席树保存的是离散化后 $[1,i]$ 出现的次数。 区间查询时，运用前缀和的思想确定左右区间，递归求解。 ------------ 所有笔记的代码： - <https://www.luogu.com.cn/paste/2lwa55o2> 画图软件： - $\text{Microsoft Whiteboard}$ 编辑器： - $\text{CP Editor / Dev-C++}$