2020-2021:teams:farmer_john:lichao_tree
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:lichao_tree [2020/05/14 01:08] bazoka13 |
2020-2021:teams:farmer_john:lichao_tree [2020/06/12 19:21] (当前版本) admin review |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | **格式**： | ||
| + | - 画图有一些更好的工具，如 visio ppt geogebra [[https://www.processon.com/|process on]]，请勿手画 | ||
| + | - 公式两边接汉字请空格 | ||
| + | |||
| + | **内容**： | ||
| + | - 没有例题吗 | ||
| + | |||
| ======李超树====== | ======李超树====== | ||
| =====它能干什么===== | =====它能干什么===== | ||
| 行 5: | 行 12: | ||
| * 区间查询最值 | * 区间查询最值 | ||
| =====它是什么===== | =====它是什么===== | ||
| - | 根据用途不难看出，李超树是一种可以维护区间“优势线段”的线段树。至于优势线段，通俗地讲，从上向下看能看到覆盖长度最多的线段，如图： | + | 根据用途不难看出，李超树是一种可以维护区间“优势线段”的线段树。至于优势线段，通俗地讲，从上向下看能看到覆盖长度最长的线段。至于详细的定义，没有找到具体的说明，凭个人理解，可以认为是在某个区间内，如果某条线段在某些横坐标区间上的值都大于其他线段，并且这些区间总长度占当前总区间的比例最高，则该线段为“优势线段”。如图： |
| {{:2020-2021:teams:farmer_john:qq图片20200514003942.png?400|}} | {{:2020-2021:teams:farmer_john:qq图片20200514003942.png?400|}} | ||
| 行 39: | 行 46: | ||
| {{:2020-2021:teams:farmer_john:qq图片20200514005839.png?400|}} | {{:2020-2021:teams:farmer_john:qq图片20200514005839.png?400|}} | ||
| - | 假设虚线即为当前区间的终点，如果该处$k$的函数值较大，显然优势线段即为$k$，对于线段$a$，显然在中点左侧$a$仍有可能成为优势线段，而右侧则根本不可能，那只需要将$a$和$k$ $swap$，然后处理左侧部分即可。如果中点处$k$的函数值较小，跳过$swap$直接向下即可。 | + | 假设虚线即为当前区间的中点，如果该处$k$的函数值较大，显然优势线段即为$k$，对于线段$a$，显然在中点左侧$a$仍有可能成为优势线段，而右侧则根本不可能，那只需要将$a$和$k$ $swap$，然后处理左侧部分即可。如果中点处$k$的函数值较小，跳过$swap$直接向下即可。 |
| 代码： | 代码： | ||
| 行 89: | 行 96: | ||
| } | } | ||
| </code> | </code> | ||
| + | ===区间=== | ||
| + | 区间查询同样类似于普通线段树，仍以最大值为例，当前区间$now$的最大值$val(now)$即为$\max(当前区间优势线段两端取值,\max(val(ls),val(rs)))$ | ||
2020-2021/teams/farmer_john/lichao_tree.1589389688.txt.gz · 最后更改: 2020/05/14 01:08 由 bazoka13
