[数据结构入门]线段树plus - 区间乘法

2024-02-13 18:54:46

#0.0 前置知识
#1.0 区间乘法...？
更新日志及说明
- 更新
- 个人主页

#0.0 前置知识

本文为线段树^plus，在阅读本文前，请确保你已经学会了线段树区间加法与区间查询，否则建议继续学习：

[数据结构入门]线段树
发表于 2019-11-28 20:39 Dfkuaid
摘要：线段树的基本（建树、区间查询、单点修改）及进阶操作（区间修改单点查询、区间修改区间查询（标记下传、标记永久化））

阅读全文
>>

#1.0 区间乘法...？

对于区间乘法的处理本身并不麻烦，就如同处理区间加法时一样，给他一个懒标记，用的时候下传便是了，但是，问题肯定不止这么简单（~~不然我怎么水完这篇博客~~），重要的是在有其他区间操作时（比如还有区间加法）如何处理懒标记下传的顺序。所以这一节的标题应该是：

#1.1 ...是下传顺序！

思考，我们为什么要注意懒标记下传的顺序？

很简单，因为下传的顺序会影响维护的结果。

我们看下面这个修改过程：

假如我们有一个区间加法，又有一个区间乘法，那么我们也应该有两个懒标记，一个是 lazy_add，维护加法的懒标记，另一个则是lazy_mul，用于维护乘法的懒标记。
假如，结点 \(P\) 上同时有着加法懒标记 \(a\) 和乘法懒标记 \(b(a,b > 1)\)，我们第一次操作，对区间 \([x_1,y_1]\) 进行了一次区间加法，结点 \(P\) 表示的范围 \([l,r]\) 完全包含在要修改的范围里，显然我们会直接对 \(P\) 的 lazy_add 加上要加的数 \(k\) 变为 \(a+k\)，
假如我们要对区间 \([x,y]\) 再进行一次区间加法，但结点 \(P\) 表示的范围 \([l,r]\) 一部分在修改的范围里，而 \(P\) 上又同时有着加法懒标记和乘法懒标记，根据我们已有的知识，我们显然要先下放 \(P\) 上的懒标记
那么，假如（~~假如真^TM多~~）
- 我们先下放了 lazy_add，那么左儿子的 lazy_add，变为了 \(a_{lson} +a+k\)
- 再下放 lazy_mul，那么，根据整体的计算，我们不仅应当对左儿子的 sum 进行更改，还应该更改它的 lazy_add和lazy_mul，修改 lazy_add 时，问题出现了，现在这个 lazy_add 的值是 \(a_{lson}+a+k\)，这个 \(k\) 似乎不应当乘上这个懒标记诶，这个区间加上 \(k\) 应当在区间乘上这个懒标记之后操作才对，所以，先下放 lazy_add ，再下放lazy_mul的方法就这么挂了QwQ

由上面这个~~^{足足有400个字，“假如”多到我不想打的}~~例子可以很明显地看出，我们应当先下放lazy_mul，再下放 lazy_add 。

同样的，直接对一个区间进行懒标记上的修改也应遵循这样的顺序

#1.2 部分代码实现

大部分代码与单纯区间加法与区间查询区别不大，处理好下传标记即可

#1.2.1 打——标——记——

inline ll len(int k){
    return p[k].r - p[k].l + 1;
}

inline void update(int k,int mul,int add){
    p[k].lazy_mul = (p[k].lazy_mul * mul) % mod;
    p[k].lazy_add = (p[k].lazy_add * mul) % mod;
    p[k].lazy_add = (p[k].lazy_add + add) % mod;
    p[k].sum = (p[k].sum * mul + add * len(k)) % mod;
}

#1.2.2 下——放——标——记——

inline void pushdown(int k){
    int ls = p[k].ls,rs = p[k].rs;
    update(ls,p[k].lazy_mul,p[k].lazy_add);
    update(rs,p[k].lazy_mul,p[k].lazy_add);
    p[k].lazy_add = 0;
    p[k].lazy_mul = 1; //注意乘法懒标记清空是变成 1 而不是 0.
}

#1.2.2 区——间——更——改——

下面给出区间乘法的代码，区间加法不再多说

inline void multip(int k,int l,int r,int x){
    if (l <= p[k].l && p[k].r <= r){
        update(k,x,0);
        return;
    }
    pushdown(k);
    int mid = (p[k].l + p[k].r) >> 1;
    if (l <= mid)
      multip(p[k].ls,l,r,x);
    if (mid < r)
      multip(p[k].rs,l,r,x);
    pushup(k);
}

#1.2.3 其他

其他部分的代码与单纯区间加法区间查询没有什么两样，不再赘述

#1.3 启发

显然，这道题最重要的不是学会区间乘法，而是要学会考虑每一个过程是否会对答案造成错误的影响，要多考虑每一步步骤的合理性。而且，这样的结论及思考方式可以扩展出去，假如有三种运算怎么办？四种呢？一样分析即可。

好短啊。。。(╬￣皿￣)但是我真的水不出来什么了QwQ。。。找时间补充几张图吧。。。

其实最初还想讲讲动态开点的。。。码到一半才发现自己其实根本不会。。。一直用的是假的动态开点。。。

更新日志及说明

更新

初次完成编辑 - \(2021.2.2\)

个人主页

欢迎到以下地址支持作者！
Github：戳这里
Bilibili：戳这里
Luogu：戳这里

码农公寓