线段树（2）——其实是总题解
借这道挺难的模板题浅谈线段树入门必须的几种技巧
1.基础的建树
理解：sum数组用来存这棵树，前边分段的操作可以看作搭建树的建构，把树对应的每个坐标的格子空下用来装值。挡拆到单点时将需要进行树状处理的数组填进去，然后按照自己的需要上推所需要的值，线段树就构造完成了
代码大致如下(十分简单)：
void build(int x,int l,int r)
{
if(l==r)
{
sum[x]=a[l];//找到单点
return;//记得return!!!!!!!!!!!!!要不然会毒瘤
}
int mid=(l+r)/2;
build(x*2,l,mid);//拆分
build(x*2+1,mid+1,r);
push_up(x);//往上推回溯
}2.基础的查询
先去做I HATE IT和模板1，涉及简单的查询
理解：
（1）单点查找【替换】
最简单的理解是： 二分查找！
与建树的过程大致相同：二分在左右儿子中找需要的找到需要的单点时对其进行操作即可
代码
void max_updata(int x,int l,int r,int a,int b)//把a的成绩改为b,b是个数字
{
if(l==r)//找到单点a
{
sum[x]=max(sum[x], b);//替换
return;
}
int mid=(l+r)/2;//标准且经典的二分查找
if(a<=mid) max_updata(x*2,l,mid,a,b);
else max_updata(x*2+1,mid+1,r,a,b);
push_up(x);//别忘了在改动最下边的值之后pushup回溯改变上边的值
}（2）最大最小值查询
这个代码就更弟弟了，二分查找左右儿子中最大/最小的那个
特别说明：1. 求最大最小值时，因为选择方法的改变，上推条件变成了比大小，push_up函数需要修改；2. 求最小值时，不在界内最好返回一个极大的值，不要随手返回0（本人在这个点上卡了一个半小时）
代码
int min_update(int x,int l,int r,int lx,int ly)
{
if(l>ly||r<lx) return 0x7f7f7f7f;///又见毒瘤
// printf("%d %d %d %d %d %d\n",x,l,r,lx,ly,sum[x]);
if(l>=lx&&r<=ly) return sum[x];
int mid=(l+r)/2;
int t= min(min_update(x*2,l,mid,lx,ly),min_update(x*2+1,mid+1,r,lx,ly));/////////
// printf(" %d\n",t);
return t;
}（3）区间查找求和
这里要引进一个个人一直用的（暴力的）讨论方式：三段分类讨论
1.当前区间完全不在要求的区间中，当前区间的SUM值完全与要求的没有关系，返回0； 2.当前区间完全在要求的区间之内，即使还没求完也不用当前的区间管了，之间返回当前sum值就好。 3.如果当前区间超出了要求的区间，那么就二分拆分它直到拆到在界内为止【期间必定就舍去了界外的部分】
代码
int query(int x,int l,int r,int lx,int ly)//////////
{
if(l>ly||r<lx) return 0;
if(lx<=l&&r<=ly) return sum[x];
int mid=(l+r)/2;
//push_down_multiply(x,l,r);//没区间替换不用下移lazy_tag
//push_down_add(x,l,r);
int summ=query(x*2,l,mid,lx,ly)+query(x*2+1,mid+1,r,lx,ly);
return summ;
}3.基础的区间修改
这里涉及一个lazy_tag的概念，其他dalao已经讲的很清楚了，只简单提一下：
lazy_tag与之前的push_up正好相反，修改区间时还修改儿子，那为啥还要用线段树？！跑得比暴力还慢。。。于是我们修改爸爸，利用爸爸前溯修改儿子，就可以大大减少操作次数。
那么lazy_tag到底是啥呢？就是对爸爸（其实就包括了儿子）的操作标记，每次下移一层（！！）就像传家宝一样，一代一代往下传，越攒越多（别忘了儿子自己也有tag）,传到最后一代就完成了修改。
代码（注意事项在其中）
void push_down(int x,int l,int r)
{
if(add[x])
{
int leftson=x*2,rightson=x*2+1;
int mid=(l+r)/2;
add[leftson]+=add[x];//注意这里的+=
add[rightson]+=add[x];
sum[leftson]+=add[x]*(mid-l+1);//同时修改总值，标记*长度即可
sum[rightson]+=add[x]*(r-(mid+1)+1);
add[x]=0;//归零要不然回溯的时候会多加一遍
return;
}
}最后讲讲这道题需要注意的地方：
难点在于：1.多了一个乘法标记，这种修改是牵一发而动全身的，在下移乘法标记的时候要先更新加法标记 2.须知乘法结合律，
（a+b）c!=ac+b;所以做区间乘法时要先下移乘法标记，再下移加法标记； 3.这道题数字会非常大，所以在计算中千万记得要把该取模的都取上，要不然也会毒瘤 4.multiply标记是 乘法！！在下以后要归为1！！！在初始时也要先赋成1！！不然也会毒瘤！！
AC代码附上：
///ORZ ZWH
#include<bits/stdc++.h>
#define int long long
#define MAXN 100010
using namespace std;
int n,m,p;
int a[MAXN],tree[MAXN*4],sum[MAXN*4],add[MAXN*4],multiply[MAXN*4];
void push_up(int x)//////////
{
sum[x]=sum[x*2]+sum[x*2+1];
}
void push_down_add(int x,int l,int r)/////////
{
if(add[x])
{
int leftson=x*2,rightson=x*2+1;
int mid=(l+r)/2;
add[leftson]=(add[leftson]%p+add[x]%p)%p;
add[rightson]=(add[rightson]%p+add[x]%p)%p;
sum[leftson]=(sum[leftson]%p+add[x]%p*(mid-l+1)%p)%p;
sum[rightson]=(sum[rightson]%p+add[x]%p*(r-(mid+1)+1)%p)%p;
add[x]=0;
return;
}
}
void push_down_multiply(int x,int l,int r)
{
if(multiply[x]!=1)
{
int leftson=x*2,rightson=x*2+1;
multiply[leftson]=(multiply[leftson]*multiply[x])%p;
multiply[rightson]=(multiply[rightson]*multiply[x])%p;
add[leftson]=(add[leftson]*multiply[x])%p;
add[rightson]=(add[rightson]*multiply[x])%p;
sum[leftson]=(sum[leftson]*multiply[x])%p;
sum[rightson]=(sum[rightson]*multiply[x])%p;
multiply[x]=1;
return;
}
}
void build(int x,int l,int r)/////////////
{
if(l==r)
{
sum[x]=a[l];
return;//记得return!!!!!!!!!!!!!要不然会毒瘤
}
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
push_up(x);
}
void add_update(int x,int l,int r,int lx,int ly,int k)
{
if(l>ly||r<lx) return;
if(l>=lx&&r<=ly)
{
sum[x]+=k*(r-l+1)%p;
add[x]+=k;
return;
}
push_down_multiply(x,l,r);
push_down_add(x,l,r);
int mid=(l+r)/2;
add_update(x*2,l,mid,lx,ly,k);
add_update(x*2+1,mid+1,r,lx,ly,k);
push_up(x);
return;
}
void multiply_update(int x,int l,int r,int lx,int ly,int k)
{
if(l>ly||r<lx) return;
if(l>=lx&&r<=ly)
{
sum[x]=(sum[x]*k)%p;
add[x]=(add[x]*k)%p;
multiply[x]=(multiply[x]*k)%p;
return;
}
push_down_multiply(x,l,r);
push_down_add(x,l,r);
int mid=(l+r)/2;
multiply_update(x*2,l,mid,lx,ly,k);
multiply_update(x*2+1,mid+1,r,lx,ly,k);
push_up(x);
return;
}
int query(int x,int l,int r,int lx,int ly)
{
if(l>ly||r<lx) return 0;
if(lx<=l&&r<=ly) return sum[x];
int mid=(l+r)/2;
push_down_multiply(x,l,r);//没区间替换不用下移lazy_tag
push_down_add(x,l,r);
int summ=query(x*2,l,mid,lx,ly)+query(x*2+1,mid+1,r,lx,ly);
return summ;
}
signed main()
{
fill(multiply,multiply+MAXN*4,1);//
cin>>n>>p;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
cin>>m;
while(m--)
{
int z,x,y,k;
cin>>z;
if(z==1)
{
cin>>x>>y>>k;
multiply_update(1,1,n,x,y,k);
}
if(z==2)
{
cin>>x>>y>>k;
add_update(1,1,n,x,y,k);
}
if(z==3)
{
cin>>x>>y;
cout<<query(1,1,n,x,y)%p<<endl;
}
}
return 0;
} 结语
这是一道其实很毒瘤的题，但其实只要避过了那些易错的bug点，这道题就也只是模板一多了个tag而已。线段树的基本操作大概也就这么多，仅为个人理解，一定与书上不同，不喜勿喷
最后祝大家debug愉快【手动滑稽】