2020-2021:teams:farmer_john:lichao_tree
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:lichao_tree [2020/05/14 01:14] 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|}} | ||
| 行 90: | 行 97: | ||
| </code> | </code> | ||
| ===区间=== | ===区间=== | ||
| - | 区间查询同样类似于普通线段树，仍以最大值为例，当前区间$now$的最大值$val(now)$即为$max(当前区间优势线段两端取值,max(val(ls),val(rs)))$ | + | 区间查询同样类似于普通线段树，仍以最大值为例，当前区间$now$的最大值$val(now)$即为$\max(当前区间优势线段两端取值,\max(val(ls),val(rs)))$ |
2020-2021/teams/farmer_john/lichao_tree.1589390062.txt.gz · 最后更改: 2020/05/14 01:14 由 bazoka13
