【高阶数据结构】线段树加乘（维护序列）详细解释乘与加懒标记

1.题目

题目来源:https://www.luogu.com.cn/problem/P2023

[AHOI2009] 维护序列

题目背景

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

题目描述

有一个长为 $n$ 的数列 { a n } \{a_n\} {an​}，有如下三种操作形式：

1. 格式 1 t g c，表示把所有满足 $t\le i\le g$ 的 $a_i$ 改为 $a_i\times c$ ;
2. 格式 2 t g c 表示把所有满足 $t\le i\le g$ 的 $a_i$ 改为 $a_i+c$ ;
3. 格式 3 t g 询问所有满足 $t\le i\le g$ 的 $a_i$ 的和，由于答案可能很大，你只需输出这个数模 $p$ 的值。

输入格式

第一行两个整数 $n$ 和 $p$。

第二行含有 $n$ 个非负整数，表示数列 { a i } \{a_i\} {ai​} 。

第三行有一个整数 $m$，表示操作总数。

从第四行开始每行描述一个操作，同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式

对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

---

2.懒标记处理

先加后乘的形式

假设我们要在一个区间上做更新操作，区间内的某个数的值用 $x$ 表示，add 和 mul 分别代表加法因子和乘法因子。

1. 先加后乘的操作

先加后乘的更新过程是：
我们想在区间上的每个元素先加一个数 $a$，再乘以一个数 $m$，这个操作可以表示为：

$$(x+\text{add})\ast \text{mul}$$

• 乘法更新
  假设当前要在区间上乘以 $a$，则操作变成：
  $$(x+\text{add})\ast \text{mul}\ast a$$
  新的乘法标记将变为 $\text{mul}\ast a$，这是可以接受的。

• 加法更新
  假设现在要在区间上加上 $a$，则变成：
  $$(x+\text{add})\ast \text{mul}+a$$
  这个表达式不容易简化成一种标准形式。我们可以尝试将其转换为：
  $$(x+\text{add}+\frac{a}{\text{mul}})\ast \text{mul}$$

  然而，这样得到的 add 标记变成了 $\text{add}+\frac{a}{\text{mul}}$，这个值可能是一个小数，很难表示或处理。因此，先加后乘的形式并不理想。

先乘后加的形式

2. 先乘后加的操作

另一种常见的更新方式是先乘后加，即首先进行乘法操作，然后再进行加法操作。我们可以表示为：

$$x\ast \text{mul}+\text{add}$$

乘法操作

如果我们在这个数上乘以 $m$，则更新如下：

$$(x\ast \text{mul}+\text{add})\ast m=x\ast \text{mul}\ast m+\text{add}\ast m$$

因此：

• 新的乘法标记变成了 $\text{mul}\ast m$。
• 新的加法标记变成了 $\text{add}\ast m$。

加法操作

如果我们在这个数上加上 $a$，则更新如下：

$$x\ast \text{mul}+\text{add}+a$$

这里：

• 新的加法标记变为 $\text{add}+a$。
• 乘法标记保持不变。

懒标记的下传

考虑区间树的情况，假设父节点有乘法标记 $m$ 和加法标记 $a$，其更新表达式为：

$$(x\ast \text{mul}+\text{add})\ast m+a=x\ast \text{mul}\ast m+\text{add}\ast m+a$$

• 左右孩子节点的 sum 更新为：
  $$\text{root.sum}\ast m+(\text{root.r}-\text{root.l}+1)\ast a$$
  这是一个标准的加法和乘法更新，可以继续进行懒标记下传。

• 乘法标记（mul）下传时，更新为：
  $$\text{mul}\ast m$$

• 加法标记（add）下传时，更新为：
  $$\text{add}\ast m+a$$

---

3.代码

//为什么先加后乘的形式不可以
//我们要变成(x+add)*mul的形式
//假设现在要在这个区间上乘 a
//那么这个数就变成了 (x+add)*mul*a
//新的mul标记就变成了 mul*a 这个是可以的
//假设现在要在这个区间上加 a
//那么这个数就变成了 (x+add)*mul + a
//化成上面的形式 (x+add + a/mul)*mul
//显然新的add标记(add+ a/mul)可能是个小数，不好表示，故而这种方式不合适

//先乘后加形式
// x*mul +add的形式
// 在这个数上乘m
// (x*mul+add)*m
// x*mul*m + add*m
// 新的mul标记就变成了 mul*m
// 新的add标记就变成了 add*m
// 在这个数上加a
// x*mul + add + a
// mul标记不变
// 新的add标记就变成了 add + a
// pushdown的时候为什么l和r的懒标记怎么改
// 显然父亲结点的mul和add就是以先乘后加的形式下传
// 假设父亲结点为m和a
// (x*mul+add)*m+ a
// x*mul*m +add*m+a
// 左右孩子的 sum = (root.sum*m+(root.r-root.l+1)*add)
// mul : mul*m
// add : add*m+a

#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
typedef long long ll;
using LL =long long;
const int N = 1e5 + 10;
int n, p, m;
int w[N];
struct Node{
    int l, r, sum, add, mul; 
} tr[4 * N];

void pushup(int u)
{
    tr[u].sum = (tr[u<<1].sum+tr[u<<1|1].sum)%p;
}

void cale(Node &root, int a, int m) 
{
    root.sum = (ll)((ll)(root.sum)*m +(ll)(root.r-root.l + 1)*a)%p;
    root.add = (ll)(root.add*m+a)%p;
    root.mul = (ll)root.mul*m%p;
}

void pushdown(int u)
{
    Node & root = tr[u],& left =tr[u<<1], &right =tr[u<<1|1];
    cale(left,root.add,root.mul);
    cale(right,root.add,root.mul);
    tr[u].add=0;
    tr[u].mul=1;
}

void build(int u, int l, int r)
{
    if(l==r){
        tr[u]={l,r,w[l],0,1};
    }
    else{
        tr[u]={l,r,0,0,1};
        int mid = l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add, int mul)
{
    if(tr[u].l>=l&&tr[u].r<=r){
        cale(tr[u],add,mul);
    }
    else{
        pushdown(u);
        int mid =tr[u].l+tr[u].r>>1;
        if(l<=mid)modify(u<<1,l,r,add,mul);
        if(r >mid)modify(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if(tr[u].l>=l &&tr[u].r<=r)return tr[u].sum;
    else{
        pushdown(u);
        int mid =tr[u].l+tr[u].r>>1;
        ll res =0;
        if(l<=mid)res += query(u<<1,l,r)%p;
        if(r >mid)res = (res+query(u<<1|1,l,r))%p;
        return res;
    }
}

signed main()
{
    cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>w[i];
    build(1,1,n);
    cin>>m;
    while ( m -- )
    {
        int t, l, r, d;
        cin>>t>>l>>r;
        if ( t == 1 ) 
        {
            cin>>d;
            modify(1, l, r, 0, d);
        }
        else if ( t == 2 )
        {
            cin>>d;
            modify(1, l, r, d, 1);
        }
        else cout<<query(1, l, r)<<'\n';
    }
    return 0;
}

原文地址：https://blog.csdn.net/surtr1/article/details/145137149

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！