李超线段树是一种通过线段树维护某处线段（或说斜率）进而维护凸包的数据结构工具。可以做到查询 $\mathcal{O}(\log n)$ ，区间修改 $\mathcal{O}(\log^2n)$ 。
其过程具体地说，修改时，分治找区间内最大的线段与该线段的交点，修改即可。
思维难度不是很高。
EOF
评论
暂无评论
发表评论
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。
李超线段树是一种通过线段树维护某处线段（或说斜率）进而维护凸包的数据结构工具。可以做到查询 $\mathcal{O}(\log n)$ ，区间修改 $\mathcal{O}(\log^2n)$ 。
其过程具体地说，修改时，分治找区间内最大的线段与该线段的交点，修改即可。
思维难度不是很高。
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。