题解：P3373 【模板】线段树 2

_droplet_ · 2025-03-30 08:40:21 · 题解

本题解使用 动态开点线段树。

方法

暴力时间复杂度 O(n^2)，肯定挂，考虑线段树。

复习线段树

线段树，将每一个区间分成个两个长度为 \frac{len}{2} 的区间，下图是一棵长度 n 为 4 的线段树，每个点维护一个值 val。

建树

对于每个线段 x，先建自己的子树，到最后一层时初始化 val，接下来更新上方的 val。

修改

考虑对每个区间修改，发现时间复杂度 O(n\log{n})，比暴力还差。

考虑当这个修改覆盖这一整个区间时，使用懒标记 tag 记录，当下次修改或查询时将懒标记下传给左右子数，别忘了更新上方的 val。

查询

几乎与修改一样，这个查询覆盖这一整个区间时，直接返回 val，当下次修改或查询时将懒标记下传给左右子数。

本题题解

考虑将 tag 分成两个，加法标记 add 和乘法标记 mul。其余同上。

注意事项

在下放 add 标记时受 mul 标记影响，更新 val 时先乘后加。