《论线段树》
——线段树精细讲解第二篇 ——Yeasion_Nein出品
在上一节中，我们大概了解了线段树的运算机制以及基本的代码运行 ，在这一节，我们主要针对一个例题进行更深层次的讲解。
首先来看一道题。（题目原链接：线段树2
题目描述
如题，已知一个数列，你需要进行下面三种操作：
1.将某区间每一个数乘上x
2.将某区间每一个数加上x
3.求出某区间每一个数的和
输入输出格式
输入格式：第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k
操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k
操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果
输出格式：输出包含若干行整数，即为所有操作3的结果。
好了，首先我们来分析一下这个题目和《论线段树：一》中的例题有什么不一样的地方。
乍一看好像就是多了一个乘法机制嘛？ 没错，就是这么一个机制，把它从 普及+/提高 的难度拔到了 提高+/省选 的难度。。。
至于为什么呢.... 我们首先来考虑怎么做这道题，你就明白为什么了。
大家基本一看就知道：该题的难点就是Lazy Tag的下放。有了lazy tag，我们就可以直接更新节点的值（也就是询问3中的当前答案），然后其他的保存在lazy tag中，那么我们就可以达到近似于O(nlogn)的速度。
这一次，我们不在用struct来定义{left,right,sum}，因为这样会很繁琐。我们再次定义一个stuct里面包含三个元素。
1.此时的答案，也就是真实值。2.表示乘法意义上的lay tag。3.表示加法意义上的lazy tag。
struct point { ll value; //表示此时的答案 ll mul; //表示lazy tag的乘法意义 ll add; //表示lazy tag的加法意义 }edge[MAXN*4];
然后便是建树了，build和以前有一个不同点在开头有一个初始化mul和add的操作。由于我们要进行乘法和加法操作，于是我们将mul初始化为1，将add初始化为0.。（你想想要是mul被初始化为0了怎么乘.....）
void update(int now)//更新操作 { edge[now].value=(edge[leftson].value+edge[rightson].value)%p; //其实就是该节点的值等于他的左儿子的值和右儿子的值的和嘛 } //当然在这个build函数里面并没有使用update，看了就知道为啥了qwq... void build(int now,int left,int right) { edge[now].mul=1; //初始化乘法意义为1 edge[now].add=0; //初始化加法意义为0 if(left==right) edge[now].value=data[left]; else { int mid=(left+right)/2; //取中间节点 build(rightson,mid+1,right); //向右边建树 build(leftson,left,mid); //向左边建树 edge[now].value=edge[leftson].value+edge[rightson].value; //更新value的值 } edge[now].value%=p; return ; }
然后就是针对乘法的一个change函数，就且叫做One_change好了（怎么顺溜怎么起）。
在这里有一个问题：就是乘法和加法的优先顺序。换句话说就是：我们是先考虑乘法呢，还是先考虑加法呢？
我们先假设考虑加法优先会怎么样：其实也就是我们规定：
edge[leftson].value=((edge[leftson].value+edge[now].add)*edge[now].mul)%p;
edge[rightson].value=((edge[rightson].value+edge[now].add)*edge[mul])%p;
那么你会发现，更新操作就会变的很坑爹，只要稍微变一下add的值，mul就会跟着大大小小地变，精度损失很大。
然后我们考虑乘法优先：其实就是规定
edge[leftson].value=((edge[leftson].value*edge[now].muledge[now].add*(当前区间的长度))%p;
edge[rightson].value=((edge[rightson].value*edge[now].muledge[now].add*(当前区间的长度))%p;
然后我们就发现要改变add的数值的话只需改变add就可以了，改变mul的时候吧add也对应地乘一下就可以了，并不会损失精度。
所以我们就知道了：为了不损失精度，我们优先考虑乘法。
这里有一个和《论线段树：一》不一样的地方就是他的修改，这里我们要同时修改value,mul,add三个值，当然，最后不要忘记%p。
//One_change 表示乘法 void One_change(int now,int now_left,int now_right,int left,int right,int num) //now表示节点编号，now_left和now_right是当前遍历到的线段的左右端点。 //left和right是要操作的左右端点。num是要乘的数。 //注意：这里的端点是和《论线段树：一》相反的，不要看叉！（Yeasion手贱打错了qnq.... { if(now_left>right||now_right<left)//如果取不到交集 return ; if(left<=now_left&&right>=now_right)//如果当前遍历到的范围被要操作的范围完全包含 { edge[now].value=(edge[now].value*num)%p;//更新当前的答案值 edge[now].mul=(edge[now].mul*num)%p;//更新lazy tag的乘法值 edge[now].add=(edge[now].add*num)%p;//更新lazy tag的加法值 return ; } put(now,now_left,now_right);//下放标记 int mid=(now_left+now_right)/2;//取中 One_change(rightson,mid+1,now_right,left,right,num);//向右继续遍历 One_change(leftson,now_left,mid,left,right,num);//向左继续遍历 update(now); return ;//更新然后返回 }
然后就是加法，这里加法比乘法要少一个mul的更新，因为我们知道改变mul的时候add也要跟着乘，但是改变add的时候只改变其add自身就可以了。
//Two_change 表示加法 void Two_change(int now,int now_left,int now_right,int left,int right,int num) //now表示节点编号，now_left和now_right是当前遍历到的线段的左右端点。 //left和right是要操作的左右端点。num是要乘的数。 //注意：这里的端点是和《论线段树：一》相反的，不要看叉！（Yeasion手贱打错了qnq.... { if(now_left>right||now_right<left)//如果取不到交集 return ; if(left<=now_left)//如果完全包含 if(right>=now_right) { edge[now].value=(edge[now].value+num*(now_right-now_left+1))%p;//更新当前答案 edge[now].add=(edge[now].add+num)%p;//更新加法tag值 return ; } put(now,now_left,now_right);//下放一波标记 int mid=(now_left+now_right)/2;//取中间 Two_change(rightson,mid+1,now_right,left,right,num);//向右继续遍历 Two_change(leftson,now_left,mid,left,right,num);//向左继续遍历 update(now); return ;//更新now节点值 }
。。。好了下面就是比较繁琐的put：下放lazy tag函数了（蛤蛤）
由于我们是在加法和乘法之后都有put函数，因此我们的put函数要同时包含加法和乘法。
并且我们知道，按照我们规定的优先度，一个节点的值=其值*父节点的mul+父节点的add*（本区间的长度），最后再%p；
当然在最后我们还要想build函数开始时那样，初始化节点的mul和add值。
inline void put(int now,int left,int right) { int mid=(left+right)/2; edge[rightson].value=(edge[rightson].value*edge[now].mul+edge[now].add*(right-mid))%p; //我们知道一个节点的值=当前值*其父亲的乘法tag加上其父亲的加法tag然后一个%（注意：先乘再加） edge[leftson].value=(edge[leftson].value*edge[now].mul+edge[now].add*(mid-left+1))%p; //同理，rightson和leftson都是这个样子 edge[rightson].mul=(edge[rightson].mul*edge[now].mul)%p; edge[leftson].mul=(edge[leftson].mul*edge[now].mul)%p; edge[rightson].add=(edge[rightson].add*edge[now].mul+edge[now].add)%p; edge[leftson].add=(edge[leftson].add*edge[now].mul+edge[now].add)%p; edge[now].mul=1; edge[now].add=0; return ; }
最后的询问就很简单了，一个简单的递归完事。（注意递归的是其左儿子的值和其右儿子的值的和）。
int query(int now,int now_left,int now_right,int left,int right) { if(right<now_left||left>now_right)//如果娶不到交集 return 0; if(right>=now_right)//如果完全包含 if(left<=now_left) return edge[now].value;//返回当前节点的值 put(now,now_left,now_right);//下方标记 int mid=(now_right+now_left)/2;//取中 return (query(rightson,mid+1,now_right,left,right)+query(leftson,now_left,mid,left,right))%p; //递归 }
好的，那么整个的线段树二的代码就是这样，那么现在你应该明白它为什么是一个提高+/省选的题了吧。因为他需要考虑的地方和细节非常多，一不小心就会写错。大家写线段树二的时候一定要非常小心，有可能打错了一个代码整个代码就全盘崩溃了。
下面是全部代码：
//Yeasion_Nein出品 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define MAXN 100010 #define leftson now*2 #define rightson now*2+1 #define ll long long using namespace std; ll n,m,p,data[MAXN]; struct point { ll value; //表示此时的答案 ll mul; //表示lazy tag的乘法意义 ll add; //表示lazy tag的加法意义 }edge[MAXN*4]; void update(int now)//更新操作 { edge[now].value=(edge[leftson].value+edge[rightson].value)%p; //其实就是该节点的值等于他的左儿子的值和右儿子的值的和嘛 } inline void put(int now,int left,int right) { int mid=(left+right)/2; edge[rightson].value=(edge[rightson].value*edge[now].mul+edge[now].add*(right-mid))%p; //我们知道一个节点的值=当前值*其父亲的乘法tag加上其父亲的加法tag然后一个%（注意：先乘再加） edge[leftson].value=(edge[leftson].value*edge[now].mul+edge[now].add*(mid-left+1))%p; //同理，rightson和leftson都是这个样子 edge[rightson].mul=(edge[rightson].mul*edge[now].mul)%p; edge[leftson].mul=(edge[leftson].mul*edge[now].mul)%p; edge[rightson].add=(edge[rightson].add*edge[now].mul+edge[now].add)%p; edge[leftson].add=(edge[leftson].add*edge[now].mul+edge[now].add)%p; edge[now].mul=1; edge[now].add=0; return ; } void build(int now,int left,int right) { edge[now].mul=1; //初始化乘法意义为1 edge[now].add=0; //初始化加法意义为0 if(left==right) edge[now].value=data[left]; else { int mid=(left+right)/2; //取中间节点 build(rightson,mid+1,right); //向右边建树 build(leftson,left,mid); //向左边建树 edge[now].value=edge[leftson].value+edge[rightson].value; //更新value的值 } edge[now].value%=p; return ; } //One_change 表示乘法 void One_change(int now,int now_left,int now_right,int left,int right,int num) //now表示节点编号，now_left和now_right是当前遍历到的线段的左右端点。 //left和right是要操作的左右端点。num是要乘的数。 //注意：这里的端点是和《论线段树：一》相反的，不要看叉！（Yeasion手贱打错了qnq.... { if(now_left>right||now_right<left)//如果取不到交集 return ; if(left<=now_left&&right>=now_right)//如果当前遍历到的范围被要操作的范围完全包含 { edge[now].value=(edge[now].value*num)%p;//更新当前的答案值 edge[now].mul=(edge[now].mul*num)%p;//更新lazy tag的乘法值 edge[now].add=(edge[now].add*num)%p;//更新lazy tag的加法值 return ; } put(now,now_left,now_right);//下放标记 int mid=(now_left+now_right)/2;//取中 One_change(rightson,mid+1,now_right,left,right,num);//向右继续遍历 One_change(leftson,now_left,mid,left,right,num);//向左继续遍历 update(now); return ;//更新然后返回 } //Two_change 表示加法 void Two_change(int now,int now_left,int now_right,int left,int right,int num) //now表示节点编号，now_left和now_right是当前遍历到的线段的左右端点。 //left和right是要操作的左右端点。num是要乘的数。 //注意：这里的端点是和《论线段树：一》相反的，不要看叉！（Yeasion手贱打错了qnq.... { if(now_left>right||now_right<left)//如果取不到交集 return ; if(left<=now_left)//如果完全包含 if(right>=now_right) { edge[now].value=(edge[now].value+num*(now_right-now_left+1))%p;//更新当前答案 edge[now].add=(edge[now].add+num)%p;//更新加法tag值 return ; } put(now,now_left,now_right);//下放一波标记 int mid=(now_left+now_right)/2;//取中间 Two_change(rightson,mid+1,now_right,left,right,num);//向右继续遍历 Two_change(leftson,now_left,mid,left,right,num);//向左继续遍历 update(now); return ;//更新now节点值 } int query(int now,int now_left,int now_right,int left,int right) { if(right<now_left||left>now_right)//如果娶不到交集 return 0; if(right>=now_right)//如果完全包含 if(left<=now_left) return edge[now].value;//返回当前节点的值 put(now,now_left,now_right);//下方标记 int mid=(now_right+now_left)/2;//取中 return (query(rightson,mid+1,now_right,left,right)+query(leftson,now_left,mid,left,right))%p; //递归 } int main() { scanf("%lld%lld%lld",&n,&m,&p); for(int i=1;i<=n;i++) scanf("%lld",&data[i]); build(1,1,n); for(int i=1;i<=m;i++) { int opt; scanf("%d",&opt); if(opt==1) { ll x,y,k; scanf("%lld%lld%lld",&x,&y,&k); One_change(1,1,n,x,y,k); } else if(opt==2) { ll x,y,k; scanf("%lld%lld%lld",&x,&y,&k); Two_change(1,1,n,x,y,k); } else { ll x,y; scanf("%lld%lld",&x,&y); printf("%lld ",query(1,1,n,x,y)); } } return 0; }