线段树技巧
Part 1： 简单的常数优化
1.非递归线段树
你可以不用zkw，只用每次单点操作时直接像打二分样写下去就好了
以单点求和为例
int Que(int p,int l,int r,int x){
if(l==r) return Sum[p];
int mid=(l+r)>>1;
Down(p);
if(x<=mid) return Que(p<<1,l,mid,x);
else return Que(p<<1|1,mid+1,r,x);
}//递归
int Que(int x){
int p=1,l=1,r=n,mid;
while(l!=r) {
mid=(l+r)>>1;
if(x<=mid) r=mid,p=p<<1|1;
else l=mid+1,p=p<<1;
}
return Sum[p];
}//非递归
当然你可以花一些时间之间去学zkw
2.标记永久化
当操作只有区间修改和单点查询时，可以用（事实上这是一种很有通用的技巧）
查询时直接将遇到的点的Sum值累和过来
void Upd(int p,int l,int r,int ql,int qr,int x){
if(l==ql&&r==qr) {
Sum[p]+=(r-l+1)*x;
tag[p]+=x;
return;
}
Down(p);
int mid=(l+r)>>1;
if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x);
else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x);
Sum[p]=Sum[p<<1]+Sum[p<<1|1];
}
int Que(int p,int l,int r,int x){
if(l==r) return Sum[p];
int mid=(l+r)>>1;
Down(p);
if(x<=mid) return Que(p<<1,l,mid,x);
else return Que(p<<1|1,mid+1,r,x);
}
//普通标记法
void Upd(int p,int l,int r,int ql,int qr,int x){
if(l==ql&&r==qr) {
Sum[p]+=(r-l+1)*x;
return;
}
Down(p);
int mid=(l+r)>>1;
if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x);
else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x);
}
void Que(int p,int l,int r,int x,int &res){
res+=Sum[p];
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) Que(p<<1,l,mid,x,res);
else Que(p<<1|1,mid+1,r,x,res);
}
//标记永久化
//注意不要Up
\[\
\]
\[\
\]
\[\
\]
Part 2：神奇的用法
(当你做了一道序列上的dp题,发现自己只会打暴力怎么办？线段树不就是了!)
1.区间取模操作
将一个区间\([L,R]\)的数对\(x\)取模
发现性质当\(a[i]>=x\)时, \(a[i] \mod x \leq \frac {a[i]}2\)
因为当\(a[i] < x*2\)时，\(a[i] \mod x= a[i]-x < a[i]/2\)
当\(a[i] \geq x*2\)时，\(a[i] \mod x<=x<=\frac{a[i]}2\)
所以直接存一下最大值，大于等于x时就递归下去，复杂度\(log^2 n\)
void Upd(int p,int l,int r,int ql,int qr,int x) {
if(l==r) {
ma[p]%=x;
s[p]=is[ma[p]];
return;
}
int mid=(l+r)>>1;
if(ql==l&&qr==r) {
if(ma[p<<1]>=x) Upd(p<<1,l,mid,ql,mid,x);
if(ma[p<<1|1]>=x) Upd(p<<1|1,mid+1,r,mid+1,qr,x);
} else {
if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x);
else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x);
}
ma[p]=max(ma[p<<1],ma[p<<1|1]);
s[p]=s[p<<1]+s[p<<1|1];
}
2.内外标记结合
当你的标记在线段树上不好处理时，可以选择在整个序列上操作，把标记存在外面
如\(Set(a[1..n])=x-a[1..n]\)
可以在整个序列外面记录，将整个序列符号取反，再加x
3.整体偏移大法
当你遇到这样一个dp
\[dp[i][j]=dp[i-1][j-x]
\]
如何搞？直接在序列外面记录偏移量\(d\)，保留线段树中原来节点的权值
其实这时一个映射的思想
初始情况下$i \rightarrow i $
偏移后\(i \rightarrow i+x\)
但是偏移后值域改变？
不，你只用在刚开始时整体值域弄大一点就好了
真的不行我们还有动点线段树啊
事实上这只是一种简单的偏移，它还可以完成更多操作
如\(dp[i][j]=dp[i-1][x-j]\)
只用在偏移上乘上一个系数就好了
注意偏移后，查询\(L,R\)时，要带入系数算出原来的位置,解个方程就好了
是不是很\(easy\)!
这题我就是暴力搞过去的
const int N=3e3+10,K=230,P=1e9+7;
const ll L=-1e11,R=1e11;
int n;
ll c[N];
int cnt;
int s[N*K],t1[N*K],t2[N*K];
int ls[N*K],rs[N*K];
void Down(int p,ll l,ll r){
ll mid=(l+r)>>1;
if(~t1[p]) {
t1[rs[p]]=t1[p];
t1[ls[p]]=t1[p];
t2[ls[p]]=t2[rs[p]]=0;
s[ls[p]]=1ll*t1[p]*((mid-l+1)%P)%P;
s[rs[p]]=1ll*t1[p]*((r-mid)%P)%P;
t1[p]=-1;
}
if(t2[p]) {
(t2[rs[p]]+=t2[p])%=P;
(t2[ls[p]]+=t2[p])%=P;
(s[ls[p]]+=1ll*t2[p]*((mid-l+1)%P)%P)%=P;
(s[rs[p]]+=1ll*t2[p]*((r-mid)%P)%P)%=P;
t2[p]=0;
}
}
void Set(int p,ll l,ll r,ll ql,ll qr,int x){
x%=P;
if(ql>qr) return;
if(l==ql&&r==qr){
s[p]=1ll*(r-l+1)%P*x%P;
t1[p]=x;
t2[p]=0;
return;
}
if(!ls[p]) ls[p]=++cnt;
if(!rs[p]) rs[p]=++cnt;
Down(p,l,r);
ll mid=(l+r)>>1;
if(qr<=mid) Set(ls[p],l,mid,ql,qr,x);
else if(ql>mid) Set(rs[p],mid+1,r,ql,qr,x);
else Set(ls[p],l,mid,ql,mid,x),Set(rs[p],mid+1,r,mid+1,qr,x);
s[p]=(s[ls[p]]+s[rs[p]])%P;
}
void Upd(int p,ll l,ll r,ll ql,ll qr,int x){
if(ql>qr) return;
if(l==ql&&r==qr){
(s[p]+=(r-l+1)%P*x%P)%=P;
(t2[p]+=x)%=P;
return;
}
if(!ls[p]) ls[p]=++cnt;
if(!rs[p]) rs[p]=++cnt;
Down(p,l,r);
ll mid=(l+r)>>1;
if(qr<=mid) Upd(ls[p],l,mid,ql,qr,x);
else if(ql>mid) Upd(rs[p],mid+1,r,ql,qr,x);
else Upd(ls[p],l,mid,ql,mid,x),Upd(rs[p],mid+1,r,mid+1,qr,x);
s[p]=(s[ls[p]]+s[rs[p]])%P;
}
ll Que(int p,ll l,ll r,ll ql,ll qr) {
if(ql>qr) return 0;
if(l==ql&&r==qr) return s[p]%=P;
if(!ls[p]) ls[p]=++cnt;
if(!rs[p]) rs[p]=++cnt;
Down(p,l,r);
ll mid=(l+r)>>1;
if(qr<=mid) return Que(ls[p],l,mid,ql,qr);
else if(ql>mid) return Que(rs[p],mid+1,r,ql,qr);
else return (Que(ls[p],l,mid,ql,mid)+Que(rs[p],mid+1,r,mid+1,qr))%P;
}
int main(){
rep(kase,1,rd()) {
cnt=1;
memset(ls,0,sizeof ls);
memset(rs,0,sizeof rs);
memset(t2,0,sizeof t2);
memset(t1,-1,sizeof t1);
memset(s,0,sizeof s);
n=rd();
rep(i,2,n) c[i]=rd();
Upd(1,L,R,1,R,1);
ll fl=1,d=0;
rep(i,2,n) {
ll t1,t2;
t1=(1-d)*fl,t2=(c[i]-d)*fl;
ll sum;
if(fl==1) sum=Que(1,L,R,t1,t2);
else sum=Que(1,L,R,t2,t1);
ll t=Que(1,L,R,t2,t2);
ll tmp=-d/fl;
Set(1,L,R,tmp,tmp,sum);
t2=(c[i]-1-d)*fl;
if(fl==1) {
Set(1,L,R,L,tmp-1,0);
Set(1,L,R,t2+1,R,0);
} else {
Set(1,L,R,L,t2-1,0);
Set(1,L,R,tmp+1,R,0);
}
if(fl==1) {
Upd(1,L,R,t1,t2,t);
} else Upd(1,L,R,t2,t1,t);
fl=-fl;
d=c[i]-d;
if(d>=R||d<=L) while(1);
}
ll ans=Que(1,L,R,L,R)%P;
ans=(ans%P+P)%P;
printf("%lld\n",ans);
}
}
\[\
\]
4.区间取\(min\),单点查询
用一个标记记录即可，可以和其他多种标记(如：加法，赋值)
问题都出在标记的合并问题上，这个只能根据具体情况来模拟了
5.区间对于\(a\)取\(min\)，区间查询
每个区间记录两个值\((x,y,c)\)表示最大值,严格次大值,最大值出现的次数
考虑多种更新情况
i. \(x\leq a\)跳过
ii.\(y<a<x\)只有最大值会被影响到，直接按照个数更新即可
tip:必须是\(y<a\)才能更新，因更新之后新的\(x=a\)，如果\(y=a\)，那么最大值的个数无法直接求出
iii.\(a\leq y\) 此时需要递归到子树取更新
可以证明这样递归的次数是远达不到\(O(m\log^2n)\)
如果不包含其他修改，可以被证明是\(O(m\log n)\)的
这样的做法对于取\(min\)，甚至是同时取\(min\),取\(max\)都可以写
下面是标准的板子题
const int N=1e6+10;
const int INF=(1ll<<31)-1;
int n,m;
int a[N];
struct Node{
ll sum;
int x,y,c;
Node operator + (const Node __) const {
Node res;
res.sum=sum+__.sum;
res.x=max(x,__.x);
res.c=0;
if(x==res.x) res.c+=c;
if(__.x==res.x) res.c+=__.c;
res.y=-1;
if(x<res.x) cmax(res.y,x);
if(y<res.x) cmax(res.y,y);
if(__.x<res.x) cmax(res.y,__.x);
if(__.y<res.x) cmax(res.y,__.y);
return res;
}
}s[N<<2];
int t[N<<2];
void Build(int p,int l,int r) {
t[p]=INF;
if(l==r) {
s[p]=(Node){a[l],a[l],-1,1};
return;
}
int mid=(l+r)>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
s[p]=s[p<<1]+s[p<<1|1];
}
void Down(int p) {
if(t[p]==INF) return;
rep(i,p<<1,p<<1|1) if(s[i].x>t[p]) {
s[i].sum-=1ll*(s[i].x-t[p])*s[i].c,s[i].x=t[p];
cmin(t[i],t[p]); // 注意只有x>a 时，才能够下传标记，否则会挂(当然如果特判了就另当别论)
}
t[p]=INF;
}
void Upd(int p,int l,int r,int ql,int qr,int x) {
if(ql<=l && r<=qr) {
if(s[p].x<=x) return;
if(s[p].y<x && x<s[p].x) { // 这种情况需要更新
cmin(t[p],x);
s[p].sum-=1ll*(s[p].x-x)*s[p].c;
s[p].x=x;
return;
}
}
int mid=(l+r)>>1;
Down(p);
if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
s[p]=s[p<<1]+s[p<<1|1];
}
Node Que(int p,int l,int r,int ql,int qr) {
if(ql==l && r==qr) return s[p];
Down(p);
int mid=(l+r)>>1;
if(qr<=mid) return Que(p<<1,l,mid,ql,qr);
else if(ql>mid) return Que(p<<1|1,mid+1,r,ql,qr);
else return Que(p<<1,l,mid,ql,mid)+Que(p<<1|1,mid+1,r,mid+1,qr);
}
int main(){
rep(kase,1,rd()) {
n=rd(),m=rd();
rep(i,1,n) a[i]=rd();
Build(1,1,n);
rep(i,1,m) {
int opt=rd(),l=rd(),r=rd();
if(opt==0) Upd(1,1,n,l,r,rd());
else {
Node res=Que(1,1,n,l,r);
if(opt==1) printf("%d\n",res.x);
else printf("%lld\n",res.sum);
}
}
}
}
\[\
\]
6.\(gcd\)和区间更新
例子：
1.求\(gcd(a[l],a[l+1],..a[r])\)
2.对于区间\(l,r\),增加\(x\)
\[\
\]
利用\(gcd(a,b)=gcd(a,b-a)\)，序列差分之后，这个问题可以转化为单点修改问题
这个思想适用于这一类区间求\(gcd\)的问题
\[\
\]
7.历史版本最大值
即考虑之前 (之前每次操作过后这段区间的\(max\)) 的\(max\)
考虑对于每一种标记记录一个\(max\)，表示 这个标记在历史版本的最大值，更新时就可以同步更新了
这里有一个复杂的多标记结合+历史版本最大值的题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
int rd(){
int s=0,f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=1e5+10;
const ll INF=1e18;
int n,m;
char opt[2];
ll a[N],s1[N<<2],s2[N<<2],t1[N<<2],t2[N<<2],g1[N<<2],g2[N<<2];
void Up(int p) { s1[p]=max(s1[p<<1],s1[p<<1|1]),s2[p]=max(s2[p<<1],s2[p<<1|1]); }
void Build(int p,int l,int r) {
if(l==r) return void(s1[p]=s2[p]=a[l]);
t1[p]=t2[p]=g1[p]=g2[p]=-INF;
int mid=(l+r)>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r),Up(p);
}
void Mark(int p,ll x,int k) {
if(k==1) {
s1[p]+=x,cmax(s2[p],s1[p]);
if(t2[p]!=-INF) t2[p]+=x,cmax(g2[p],t2[p]);
else t1[p]=(t1[p]==-INF)?x:t1[p]+x,cmax(g1[p],t1[p]);
} else {
t1[p]=-INF,t2[p]=x,cmax(g2[p],t2[p]);
s1[p]=x,cmax(s2[p],s1[p]);
}
}
void Down(int p) {
if(t1[p]==-INF && t2[p]==-INF) return;
rep(i,p<<1,p<<1|1) {
if(t1[i]!=-INF) cmax(g1[i],g1[p]+t1[i]);
else if(t2[i]!=-INF) cmax(g2[i],g1[p]+t2[i]);
else cmax(g1[i],g1[p]);
cmax(s2[i],s1[i]+g1[p]),cmax(g2[i],g2[p]),cmax(s2[i],g2[p]);
}
if(t2[p]!=-INF) Mark(p<<1,t2[p],2),Mark(p<<1|1,t2[p],2);
else Mark(p<<1,t1[p],1),Mark(p<<1|1,t1[p],1);
t1[p]=t2[p]=g1[p]=g2[p]=-INF;
}
void Upd(int p,int l,int r,int ql,int qr,int x,int k) {
if(ql<=l && r<=qr) return Mark(p,x,k);
Down(p);
int mid=(l+r)>>1;
if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x,k);
if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x,k);
Up(p);
}
ll Que(int p,int l,int r,int ql,int qr,int k) {
if(ql<=l && r<=qr) return k==1?s1[p]:s2[p];
Down(p);
int mid=(l+r)>>1;
ll res=-INF;
if(ql<=mid) cmax(res,Que(p<<1,l,mid,ql,qr,k));
if(qr>mid) cmax(res,Que(p<<1|1,mid+1,r,ql,qr,k));
return res;
}
int main(){
n=rd();
rep(i,1,n) a[i]=rd();
m=rd();
Build(1,1,n);
rep(i,1,m) {
scanf("%s",opt);
int l=rd(),r=rd();
if(opt[0]=='Q') printf("%lld\n",Que(1,1,n,l,r,1));
else if(opt[0]=='A') printf("%lld\n",Que(1,1,n,l,r,2));
else Upd(1,1,n,l,r,rd(),opt[0]=='P'?1:2);
}
}
\[\
\]