前置知识：线段树常规操作的复杂度证明
单点修改、查询
线段树高为 \(O(\log n)\)，因此单点操作复杂度单次 \(O(\log n)\)，总复杂度 \(O(q\log n)\)。
区间修改、查询
在懒标记的基础上，区间修改和查询操作本质是相同的，设当前操作的区间是 \([L,R]\)，线段树所在节点对应区间 \([l,r]\)，则有三种情况：
-
\([l,r]\) 与 \([L,R]\) 无交，退出函数
-
\([l,r]\) 为 \([L,R]\) 子区间，执行操作并退出函数
-
\([l,r]\) 与 \([L,R]\) 有交，向左右儿子节点继续执行操作
容易发现第一种情况和第二种情况都来自第三种情况，其数量不会超过第三种的 \(2\) 倍，因此我们只需要证明第三种情况的复杂度。
在每一深度的线段树中，至多有两个区间会与 \([L,R]\) 有交且不为子区间，因此每个深度之后有两个区间为第三种情况，树高 \(O(\log n)\)，因此总复杂度 \(O(q\log n)\)。
线段树合并
设初始线段树的叶子节点数量 \(m\)，线段树规模 \(n\)。
按照上面的思考方式，合并时的重复节点会产生对复杂度的影响。
考虑合并时重复节点个数是不超过较小一棵线段树的，因此每个节点的合并次数不超过 \(\log n\)，因此时间复杂度 \(O(m\log n)\)。
同时“可持久化”的线段树合并中，每次新建节点也是在出现重复节点时，因此空间复杂度 \(O(m\log n)\)。
区间最值操作
不含区间加减的情况
含有区间取 \(\min\)，区间求和和区间求 \(\max\) 三个操作。
实现方法
对线段树每个节点，维护和 \(sum\)，最大值 \(mx\)，最大值个数 \(cnt\)，严格最大值 \(sec\)，以及区间取 \(\min\) 的标记 \(tag\)。
区间修改与 \(k\) 取 \(\min\) 时，讨论不同情况：
-
若 \(mx\le k\)，则不会产生影响，直接退出
-
若 \(sec<k<mx\)，则只有 \(mx\) 会受到影响，直接修改并打上标记 \(tag\)
-
若 \(k\le sec\)，则继续向下操作
同时下传标记时，由于打上标记的充要条件时 \(sec<k<mx\),因此当前子区间的次大值一定是小于 \(k\) 的，所以下传时只需要讨论前两种，而单次复杂度 \(O(1)\)。
点击查看代码
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ls rt<<1
#define rs rt<<1|1
ll sum[maxn<<2];
int mx[maxn<<2],cnt[maxn<<2],sec[maxn<<2];
int tag[maxn<<2];
inline void push_up(int rt){
sum[rt]=(sum[ls]+sum[rs]);
if(mx[ls]==mx[rs]){
mx[rt]=mx[ls],cnt[rt]=cnt[ls]+cnt[rs];
sec[rt]=max(sec[ls],sec[rs]);
}
else if(mx[ls]>mx[rs]){
mx[rt]=mx[ls],cnt[rt]=cnt[ls];
sec[rt]=max(sec[ls],mx[rs]);
}
else{
mx[rt]=mx[rs],cnt[rt]=cnt[rs];
sec[rt]=max(sec[rs],mx[ls]);
}
}
inline void push_tag(int rt,int k){
if(mx[rt]<=k) return;
else{
sum[rt]-=1ll*cnt[rt]*(mx[rt]-k);
mx[rt]=k,tag[rt]=k;
}
}
inline void push_down(int rt){
if(tag[rt]!=-1){
push_tag(rt<<1,tag[rt]);
push_tag(rt<<1|1,tag[rt]);
tag[rt]=-1;
}
}
void build(int rt,int l,int r){
tag[rt]=-1;
if(l==r){
sum[rt]=a[l],mx[rt]=a[l],cnt[rt]=1,sec[rt]=-1;
return;
}
build(lson),build(rson);
push_up(rt);
}
void update(int rt,int l,int r,int pl,int pr,int k){
if(pl<=l&&r<=pr&&sec[rt]<k) return push_tag(rt,k),void();
push_down(rt);
if(pl<=mid) update(lson,pl,pr,k);
if(pr>mid) update(rson,pl,pr,k);
push_up(rt);
}
ll query_sum(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return sum[rt];
push_down(rt);
ll res=0;
if(pl<=mid) res+=query_sum(lson,pl,pr);
if(pr>mid) res+=query_sum(rson,pl,pr);
return res;
}
int query_max(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return mx[rt];
push_down(rt);
int res=-1;
if(pl<=mid) res=max(res,query_max(lson,pl,pr));
if(pr>mid) res=max(res,query_max(rson,pl,pr));
return res;
}
#undef mid
#undef lson
#undef rson
#undef ls
#undef rs
}S;
时间复杂度证明
吉老师的论文中的证明如下。
将最大值设为一种标记，并去掉所有与父亲节点标记相同的标记，这样标记只存在于 \(O(n)\) 个位置，且区间次大值等价于一个节点子树（不包括本身）中的最大标记。
定义一次取 \(\min\) 操作及其延迟下传产生的标记为一类标记。定义一类标记的权值为其存在的所有节点与根节点组成的虚树大小，设势能函数 \(\Phi(x)\) 为所有标记的总权值。
区间取 \(\min\) 操作直接影响到的节点数为 \(O(\log n)\)，也使每影响到一个节点便势能函数增加 \(O(1)\)。
下传标记的操作是伴随其他操作进行的，且每次下传使势能函数增加 \(O(1)\)。
最重要的部分是暴力向下走的情况，此时暴力向下走说明修改值 \(k\) 是小于次小值的，也就是说子树内一定有小于修改值 \(k\) 的标记，而每次到一个节点便会使这个标记减小，即使这一类标记权值减小 \(O(1)\)。
因此每种操作都会以 \(O(1)\) 的复杂度使势能函数产生 \(O(1)\) 的变化，而势能函数的增加量是 \(O(q\log n)\) 的，减少量也不会超过 \(O(q\log n)\)，于是复杂度就是 \(O(q\log n)\) 的。
参考资料
- 《2016国家集训队论文集：区间最值操作与历史最值问题》- 吉如一