小清新线段树
定义
结合时间复杂度分析（势能分析）以及懒标记应用的非传统线段树
可以理解为带剪枝的线段树
复杂度证明
以 The Child and Sequence 为例，先看操作 1,2，对于一个数 \(x\) 进行取模，要么这个数保持不变。若模数 \(M>\frac{x}{2}\)，则剩余部分小于 \(\frac{x}{2}\)；若模数 \(M<\frac{x}{2}\)，则剩余部分小于 \(M\)。综上x至少折半，那么这个数最多被取模 \(\log V\) 次。
在具体实现时，维护区间最大值，若最大值小于模数，则跳过此区间。
对于操作3，只会增加一个数的值，最多增加 \(O(\log V)\) 的复杂度
对一个点修改 \(O(\log n)\)，由于多次修改会同时进行，LCA会多算，实际复杂度更小
综上时间复杂度 \(O((n+m)\log n\log V)\) ，空间复杂度（动态开点）： \(O(n)\)
实现
维护区间值，进行剪枝
// Problem: The Child and Sequence
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF438D
// Memory Limit: 250 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define EPS 1e-8
#define ll long long
#define ld long double
#define PII pair<int,int>
#define PDD pair<int,int>
#define max3(a,b,c) max(max(a,b),c)
#define max4(a,b,c,d) max(max3(a,b,c),d)
#define lowbit(x) ((x)&-(x))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Yes printf("Yes")
#define No printf("No")
#define chmax(a,b) (a=max(a,b))
#define chmin(a,b) (a=min(a,b))
using namespace std;
const int N=1e5+10;
int a[N],n,m;
struct SEG{
struct SEG_Node{
int ls,rs;
long long sum;
int maxv;
#define lc t[p].ls
#define rc t[p].rs
#define mid (L+R>>1)
}t[N<<1];
int tot,rt;
int mknode(){
++tot;
t[tot].ls = t[tot].rs = 0;
t[tot].sum = t[tot].maxv = 0;
return tot;
}
void pushup(int p){
t[p].sum = t[lc].sum + t[rc].sum;
t[p].maxv = max(t[lc].maxv,t[rc].maxv);
}
void build(int &p,int L,int R){
if(!p)p=mknode();
if(L==R){
t[p].sum = t[p].maxv = a[L];
return;
}
build(lc,L,mid);
build(rc,mid+1,R);
pushup(p);
}
void modify(int p,int L,int R,int l,int r,int x){
if(L==R){
t[p].sum = t[p].maxv = t[p].sum%x;
return;
}
if(l<=mid&&t[lc].maxv>=x)modify(lc,L,mid,l,r,x);
if(r>mid&&t[rc].maxv>=x)modify(rc,mid+1,R,l,r,x);
pushup(p);
}
long long query(int p,int L,int R,int l,int r){
if(l<=L&&R<=r){
return t[p].sum;
}
long long res=0;
if(l<=mid)res+=query(lc,L,mid,l,r);
if(r>mid)res+=query(rc,mid+1,R,l,r);
return res;
}
void change(int p,int L,int R,int k,int x){
if(L==R){
t[p].sum = t[p].maxv = x;
return;
}
if(k<=mid)change(lc,L,mid,k,x);
else change(rc,mid+1,R,k,x);
pushup(p);
}
}seg;
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
seg.build(seg.rt,1,n);
for(int i=1;i<=m;++i){
int op,l,r,x,k;cin>>op;
if(op==1){
cin>>l>>r;
cout<<seg.query(seg.rt,1,n,l,r)<<'\n';
}
else if(op==2){
cin>>l>>r>>x;
seg.modify(seg.rt,1,n,l,r,x);
}
else{
cin>>k>>x;
seg.change(seg.rt,1,n,k,x);
}
}
return 0;
}
思想总结
这里用到势能分析和均摊的思想。线段树灵活的区间处理优势被运用得淋漓尽致。这里没有用到懒标记，因为取模操作无法区间进行。小清新线段树的关键技术在于二进制划分区间后，能够通过整块的标记，进行类似剪枝的操作，减少时间的浪费。
线段树的算法，永无止境。当我第一次学小清新线段树的时候，就为之一振。原来，未来的时代永远充满创造力，充满活力。