线段树题单记录
线段树的题都很板的，模板敲上去再改改就行
有的题你用的线段树可能都可以删除一部分并正常使用
TODO
什么你问为什么有的题是两重确认？啊那是因为我还没写（
P3372 【模板】线段树 1
题目
Link
为什么模板是绿题，还有下面那道
思路
首先我们要明确它为什么叫线段树：
OI Wiki 上的这张图很好理解：
从这张图也可以看出来，线段树的每个节点管辖的一个又一个的线段（区间），所以我们通俗地叫它线段树。
废话
这里只讲最简朴的线段树，关于什么 ZKW线段树、动态开点线段树 请自行了解。
普通线段树学完了好像那些奇奇怪怪的线段树优化更好理解
线段树的功能很简朴，就是对区间进行维护。
维护包括但不限于 和、积和极值。
那还要珂朵莉树干什么
好吧它们各有优劣。
固然珂朵莉树快
线段树的复杂度有一个 \(4\) 的常数，所以能不用线段树尽量不用线段树。
\(st\) 表和树状数组的题线段树都能做，但是可能会被出题人卡常
代码
- #include <bits/stdc++.h>
- using namespace std;
- const int N=1e5+5;
- #define int long long
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
- while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
- return x*f;
- }
- struct node{
- int l,r;
- int s;
- int lt;
- }t[N*4];
- int n,m;
- int a[N];
- void pushup(int p){t[p].s=t[p*2].s+t[p*2+1].s;}
- void pushdown(int p){
- if(t[p].lt==0)
- return;
- t[p*2].s+=t[p].lt*(t[p*2].r-t[p*2].l+1);
- t[p*2+1].s+=t[p].lt*(t[p*2+1].r-t[p*2+1].l+1);
- t[p*2].lt+=t[p].lt;
- t[p*2+1].lt+=t[p].lt;
- t[p].lt=0;
- }
- void build(int p,int l,int r){
- t[p].l=l;
- t[p].r=r;
- if(l==r){t[p].s=a[l];return;}
- int mid=(l+r)>>1;
- build(p*2,l,mid);
- build(p*2+1,mid+1,r);
- pushup(p);
- }
- void update(int p,int l,int r,int c){
- if(t[p].l>=l&&t[p].r<=r){
- t[p].lt+=c;
- t[p].s+=c*(t[p].r-t[p].l+1);
- return;
- }
- pushdown(p);
- int mid=(t[p].l+t[p].r)>>1;
- if(l<=mid)
- update(p*2,l,r,c);
- if(r>mid)
- update(p*2+1,l,r,c);
- pushup(p);
- }
- int query(int p,int l,int r){
- if(t[p].l>=l&&t[p].r<=r)
- return t[p].s;
- int reu=0;
- int mid=(t[p].l+t[p].r)>>1;
- pushdown(p);
- if(l<=mid)
- reu+=query(p*2,l,r);
- if(r>mid)
- reu+=query(p*2+1,l,r);
- return reu;
- }
- signed main(){
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- cin>>a[i];
- build(1,1,n);
- int ty;
- int x,y,k;
- for(int i=1;i<=m;i++){
- cin>>ty;
- if(ty==1){
- cin>>x>>y>>k;
- update(1,x,y,k);
- }
- else{
- cin>>x>>y;
- cout<<query(1,x,y)<<endl;
- }
- }
- return 0;
- }
pushdown
声明：void pushdown (int p)
这个函数是用来进行儿子节点更新的，传入要进行 pushdown 操作的节点编号 \(p\)，然后进行修改，就像如许：- if(l==r){t[p].s=a[l];return;}
- int mid=(l+r)>>1;
- build(p*2,l,mid);
- build(p*2+1,mid+1,r);
- pushup(p);
这里也是题目设难点的一个重灾区，某些题目要思量的情况很多，一不注意就 \(WA\) 了
现在我们来看查询 query。
query
声明：int query (int p,int l,int r)
传入三个参数：
当前节点编号 \(p\)、当前修改的左端点 \(l\)、当前修改的右端点 \(r\)。
和 update 差不多，query 的判断逻辑也是如果说当前节点的左右端点已经被查询区间完全包含了，那么就 return 当前节点的查询值：- if(t[p].l>=l&&t[p].r<=r){
- t[p].lt+=c;
- t[p].s+=c*(t[p].r-t[p].l+1);
- return;
- }
可能有的人会比较好奇，pushdown 和 pushup 是个什么用的，为什么要在那些位置放他们 是的没错就是我朋友的问题。
关于 pushup 和 pushdown
为什么会有它俩：
用 OI Wiki 上的图画的
如果说我们某次修改了区间 [1,3]（图中红色区间）。
现在我们要查询区间 [2,2] 其实就一个点（图中蓝色的点）。
然后你会发现它并没有被修改，所以在 query 中出现了 pushdown，用来确保它的儿子节点是最新的。
那么它为什么没有 pushup 呢？
有也可以，但是由于它的儿子节点没有 被修改，所以我们用不到 pushup。
那么这个 “被修改” 是什么意思呢？
显然，这里在它的儿子节点修改之前它已经修改过了，所以它不用修改。
那么 update 中为什么会同时有 pushup 和 pushdown 呢？
照旧这张图。
如果说我们现在蓝色标记不是查询而是修改，即
我们某次修改了区间 [1,3]（图中红色区间）。
现在我们要修改区间 [2,2]（图中蓝色的点）。
然后我们会发现，它的值不是最新的，我们要把 [1,3] 区间的懒标记进行 pushdown 操作已包管修改前它的值是最新的。
那为什么还要有 pushup 操作呢？
和刚刚的 update 相对，这里它的子节点一定被修改了，而且这次修改没有在它本身身上体现，所以我们须要用 pushup 进行修改以确保它是最新的。
P3373 【模板】线段树 2
Link
题目思路
这个不就是多个 \(lt\)，原有 \(lt\) 功能不变，新的 \(lt\) 用来保存乘积吗，pushdown 的时候先 pushdown 乘积再 pushdown 和就行了。
这题还行，某 \(AT\) \(ABC\) 的题 MD 少 \(mod\) 了两下连 \(unsigned long long\) 都给我爆了（
关于为什么先 pushdown 乘积再 pushdown 和 显然 让我们来证一下：
首先，设其中三次修改分别为 乘、加、乘，三次修改值分别为 \(x\)、\(y\)、\(z\)。原数列为 \(A\)，其中元素为 \(a\)，长度为 \(N\)（简写 \(n\)）。
那么修改后的和 \(NewSum\) 为：
我懒
\(NewSum\)
\(\xlongequal {} (a_1 \times x+y) \times z + \dots + (a_n \times x+y) \times z\)
\(\xlongequal {} a_1 \times x \times z + y \times z \dots + a_n \times x \times z+ y \times z\)
\(\xlongequal {} OldSum \times x \times z + n \times y \times z\)
所以我们要先更新乘法的懒标记再更新加法的懒标记。
应该没有人会把乘法的懒标记重置为 \(0\) 吧
代码
- pushdown(p);
- int mid=(t[p].l+t[p].r)>>1;
- if(l<=mid)
- update(p*2,l,r,c);
- if(r>mid)
- update(p*2+1,l,r,c);
- pushup(p);
Link
思路
这里可以体现出线段树不只能维护区间某些数学值，也可以维护一些 奇奇怪怪 的值。
这道题的节点中须要维护的东西有 亿 点多，不过字符因为只有两种，为了方便，可以用 \(bool\) 范例来存。
就拿样例 \(1\) 来说明吧。- {
- if(t[p].lt==0)
- return;
- t[p*2].s+=t[p].lt*(t[p*2].r-t[p*2].l+1);
- t[p*2+1].s+=t[p].lt*(t[p*2+1].r-t[p*2+1].l+1);
- t[p*2].lt+=t[p].lt;
- t[p*2+1].lt+=t[p].lt;
- t[p].lt=0;
- }
https://imgse.com/i/pkOP0L4
用颜色来区分 \(L\) 和 \(R\)，其中黑色为 \(L\)，红色为 \(R\)。
现在来想一下更新区间 \(1\) ~ \(3\) 的最大值时可能出现的情况：
1. 左右两段区间不能衔接
如图：
https://imgse.com/i/pkOP0L4
其实就是上面那张图
它的最值为它左右儿子的最值。
2. 左右两段区间可以相接
如图：
https://imgse.com/i/pkOP6F1
这种情况下，要额外思量左右区间相接的情况对于区间最值潜伏的影响。
综上，我们可以得出：
节点中须要保存的信息有：
- 左右端点 这个不用说了吧
- 区间最值
- 区间左侧字母
- 区间右侧字母
- 区间从左侧开始最值
- 区间从右侧开始最值
更新时，须要额外思量左右区间能否相接以更新最值。
Code
[code]#include using namespace std;const int N=2e5+5;struct node{ int l,r; int len; int s; int ls,rs; bool cl,cr;}t[N*4];int n,q;void pushup(int p){ t[p].s=max(t[p*2].s,t[p*2+1].s); if(t[p*2].cr!=t[p*2+1].cl) t[p].s=max(t[p].s,t[p*2].rs+t[p*2+1].ls); t[p].cl=t[p*2].cl; t[p].cr=t[p*2+1].cr; if(t[p*2].ls==t[p*2].len&&t[p*2].cr!=t[p*2+1].cl) t[p].ls=t[p*2].ls+t[p*2+1].ls; else t[p].ls=t[p*2].ls; if(t[p*2+1].rs==t[p*2+1].len&&t[p*2].cr!=t[p*2+1].cl) t[p].rs=t[p*2+1].rs+t[p*2].rs; else t[p].rs=t[p*2+1].rs;}void build(int p,int l,int r){ t[p].l=l,t[p].r=r; t[p].len=t[p].r-t[p].l+1; t[p].cl=0,t[p].cr=0; if(l==r){ t[p].s=1; t[p].ls=1; t[p].rs=1; return; } int mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); pushup(p);}void update(int p,int l,int r){ if(t[p].l>=l&&t[p].r>1; if(lmid) update(p*2+1,l,r); pushup(p);}int query(int p,int l,int r){ if(t[p].l>=l&&t[p].r>1; int ql=query(p*2,l,r); int qr=query(p*2+1,l,r); if(lmid)) reu=ql; if(r>mid&&!(l>n>>q; int x; build(1,1,n); for(int i=1;i>x,update(1,x,x),cout1; pushdown(p); if(lmid) reu+=query(p*2+1,l,r); return reu; } void update(int p,int l,int r,int c){ if(t[p].l>=l&&t[p].r>1; if(lmid) update(p*2+1,l,r,c); pushup(p); }}lt,rt;int n,m;signed main(){ cin>>n>>m; lt.n=n; rt.n=n; lt.build(1,1,n); rt.build(1,1,n); int q,l,r,k=0; for(int i=1;i>q>>l>>r; if(q==1) lt.update(1,l,l,1),rt.update(1,r,r,1),k++; else{ int cost=0; if(l-1 >= 1) cost+=rt.query(1,1,l-1); if(r+1 |
