March 16, 2025
感觉需要按照 这个顺序 重新复习一下线段树，掌握一下先进姿势！
首先我觉得最重要的就是仔细学习 atc 模板：
虽然线段树模板茫茫多，但是这个无疑依然是目前最有生命力的一个，它不仅适用范围广，速度快（里面居然是个 zkw 树），而后面的 lazysegtree 模板的原理现在大家所说的「双半群」模型。
领悟之后我们发现大部分线段树问题竟然都变成了无脑填空题囧！！
而另一个技术就是势能线段树！简单来说就是有些修改操作破坏半群性质修改的情况，我们找到区间后先暴力清空，或者放宽找区间的代码，递归下去。
这样看似暴力，但是因为有些时候修改操作可以势能分析，发现复杂度没变！
最经典的模型就是区间取模取根，区间染色，以及区间 CheckMin QueryMax！
Posted by
xiaodao
Category: 日常
Your name - Required
Your email - Required (will not be published)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。