[C++知识库]C++线段树区间乘法&区间加法&区间查询代码详解（可能是最详细的了）

当我刚刚接触线段树区间乘法时，因为一直没想懂乘法和加法的懒标记怎么一起下推，上百度和CSDN搜索程序讲解，但搜到的绝大多数都是一些没有讲解，直挂代码的博文，很难让人看懂代码意思，往往会花费大量时间在理解变量的作用和操作的原理，因此为了方便初学者学习（也为了方便我以后复习），就写了这篇博文，希望对你有所帮助！

题目：

代码解释：

代码虽然长，但原理简单

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll a[100001],tree[400001],mark[400001],mark_[400001],n,m,M; //a用来存原数组的值，tree用来维护线段树，mark用来记录加法的懒标记
                                                            //mark_用来记录乘法的懒标记，M是需要取模的数值
inline void read(ll &a) {  //快读
	ll x(0),y(1);char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+(c^48);c=getchar();
	}
	a=x*y;return;
}
inline void write(ll x) {  //快输
	if(x<0) {
		putchar('-');x=-x;write(x);
	} else {
		if(x>9)
			write(x/10);
		putchar(x%10+'0');
	}
}

push_dawn函数：

push_dawn函数是程序的核心，主要作用是把加法和乘法标记下推，并维护左右子树的值，下面会对此函数进行详细解释

第一个部分：左右子树数值维护

首先，因为子树同时有乘法的标记和加法的标记，我们需要一起处理

先说乘法：

因为乘法是把从 $l$ 到 $r$ 的所有数乘以 $k$ 所以可以得到如下公式：

$$a_l+a_{l+1}+...+a_r=a_l\times k+a_{l+1}\times k+...+a_r\times k$$

提取公因式：

$$a_l\times k+a_{l+1}\times k+...+a_r\times k=k\times (a_l+a_{l+1}+...+a_r)$$

又因为 $tree$ 数组·刚好就是维护区间和的，所以可以得到：

$$k\times (a_l+a_{l+1}+...+a_r)=k\times tre{e}_{l～r}$$

所以我们想要知道 $tree$ 数组在处理完乘法标记后的数值时，就可以直接用标记乘以 $tree$

再说加法：

因为加法是把从 $l$ 到 $r$ 的所有数加上 $k$ 所以可以得到如下公式：

$$a_l+a_{l+1}+...+a_r=a_l+k+a_{l+1}+k+...+a_r+k$$

提取公因式：

$$a_l+k+a_{l+1}+k+...+a_r+k=(r?l+1)\times k+(a_l+a_{l+1}+...+a_r)$$

又因为 $tree$ 数组·刚好就是维护区间和的，所以可以得到：

$$(r?l+1)\times k+(a_l+a_{l+1}+...+a_r)=(r?l+1)\times k+tre{e}_{l～r}$$

所以我们想要知道 $tree$ 数组在处理完加法标记后的数值时，就可以直接用标记乘以区间内数字个数在加上 $tree$

最后合并

知道了乘法和加法分别怎么处理，最后就很简单了，因为只要把乘法的修改和加法的修改加在一起，就是最后的答案。

也就是
$$tre{e}_{p\times 2}=(mark{\_}_p?tre{e}_{p\times 2}+(len?len÷2)\times mar{k}_p)\%M$$
和
$$tre{e}_{p\times 2+1}=(mark{\_}_p?tre{e}_{p\times 2+1}+(len?len÷2)\times mar{k}_p)\%M$$

void push_down(ll p,ll len) {
	tree[p*2]=(mark_[p]*tree[p*2]+(len-len/2)*mark[p])%M;  //此部分原理见上
	tree[p*2+1]=(mark_[p]*tree[p*2+1]+(len/2)*mark[p])%M;
	//----------分开理解----------
	mark_[p*2]=mark_[p*2]*mark_[p]%M;  //子节点的乘法标记和父节点的相乘，原因可以按照上面的思想推一下，很容易发现，就不过多解释
	mark_[p*2+1]=mark_[p*2+1]*mark_[p]%M;  //同上
	mark[p*2]=(mark[p*2]*mark_[p]+mark[p])%M;  //子节点的加法标记稍稍难理解，但原理差不多，因为这个区间内的数已经有了一个加法标记，所以我们分解因式，把加法标记和tree分开乘，最后再把父节点的加法标记给他推下去，就可以了（先乘载加顺序很重要！）
	mark[p*2+1]=(mark[p*2+1]*mark_[p]+mark[p])%M;  //同上
	//----------分开理解----------
	mark[p]=0;  //父节点的标记已经下推，所以父节点标记清空
	mark_[p]=1;  //乘法标记不能是0，原因显然
}
void build(ll l,ll r,ll p) {  //建树操作
	mark_[p]=1;  //乘法标记初始化
	if(l==r) {   //如果是子节点
		tree[p]=a[l];  //当前节点的数值为原数组数值
		return;
	}
	ll mid=(l+r)>>1;  //记录中间值
	build(l,mid,p*2);  //建左子树
	build(mid+1,r,p*2+1);  //建右子树
	tree[p]=tree[p*2]+tree[p*2+1];  //当前节点数值等于左右子树数值之和
	return;
}
void update(ll l,ll r,ll k,ll p,ll cl,ll cr) {  //线段树加法数值更新，表示把从l到r的数值加d，p是当前树序号，cl,cr是当前区间范围
	if(cl>r||cr<l) { //如果需要更新的区间和当前区间无交集
		return;
	} else {
		if(l<=cl&&r>=cr) { //如果当前区间被完全包含在需要更新的区间内
			tree[p]+=k*(cr-cl+1);   //数值更新
			if(cl<cr) { //如果没有到叶子节点
				mark[p]+=k;  //打标记
			}
		} else { //如果部分包含
			ll mid=(cl+cr)/2; //记录中间值
			push_down(p,cr-cl+1);  //标记下推
			update(l,r,k,p*2,cl,mid); //更新左子树
			update(l,r,k,p*2+1,mid+1,cr); //更新右子树
			tree[p]=tree[p*2]+tree[p*2+1];   //更新当前结点数值
		}
	}
}
void update_(ll l,ll r,ll k,ll p,ll cl,ll cr) { //线段树乘法数值更新，表示把从l到r的数值加d，p是当前树序号，cl,cr是当前区间范围
	if(cl>r||cr<l) { //如果需要更新的区间和当前区间无交集
		return;
	} else {
		if(l<=cl&&r>=cr) { //如果当前区间被完全包含在需要更新的区间内
			tree[p]=tree[p]*k%M;  //乘法更新，原理与push_down相同
			if(cl<cr) {  //如果没有到叶子节点
				mark[p]=mark[p]*k%M;  //乘法标记对加法标记有影响，毕竟要分开成，所以这里就先把加法标记乘了
				mark_[p]=mark_[p]*k%M;  //乘法标记更新
			}
		} else {
			ll mid=(cl+cr)/2;  //记录中间值
			push_down(p,cr-cl+1); //标记下推
			update_(l,r,k,p*2,cl,mid); //更新左子树
			update_(l,r,k,p*2+1,mid+1,cr);//更新右子树
			tree[p]=tree[p*2]+tree[p*2+1];  //更新当前结点数值
		}
	}
}
ll query(ll l,ll r,ll p,ll cl,ll cr) {   //区间查询
	if(cl>r||cr<l) {  //如果与当前区间无交集
		return 0;
	} else {
		if(cl>=l&&cr<=r) {  //如果被完全包含在需要查询的区间内
			return  tree[p];  //返回当前节点数值
		} else {    //部分包含
			ll mid=(cl+cr)/2;  //记录中间值
			push_down(p,cr-cl+1); //标记下推
			return query(l,r,p*2,cl,mid)+query(l,r,p*2+1,mid+1,cr);  //返回当前区间与需要查询的区间的交集值
		}
	}
}

int main() {
//	freopen("3372_1.in","r",stdin);
	int i;
	read(n);read(m);read(M);
	for(i=1; i<=n; ++i) {read(a[i]);}
	build(1,n,1);
	ll q,x,y,k;
	for(i=1; i<=m; ++i) {
		read(q);read(x);read(y);
		if(q==2) {
			read(k);
			update(x,y,k,1,1,n);  //加法更新
		} else {
			if(q==3) {
				write(query(x,y,1,1,n)%M);  //输出
				putchar('\n');
			} else {
				read(k);
				update_(x,y,k,1,1,n);  //乘法更新
			}
		}
	}
}

如果有帮助就点个赞吧，谢谢啦~·