LGP3372 [LG TPLT] 线段树·一 学习笔记
\(\texttt{Luogu Link}\)
题意简述
给你一个序列。
做法解析一
线段树。
维护若干个区间的信息，满足可以用 \(O(\log n)\) 个区间的信息拼起来整个区间的信息。所以它非常巧妙。还有巧妙的传 tag 机制。对，应该是。
我也不知道这里有必要写什么。先空着吧。
来都来了，测一下自己敲最基础的线段树的耗时。
代码实现一
好吧，我居然忘了区间加线段树在 maketag 的时候，sum[u]+=tag[u]*clen[u] 这个地方是有个 clen[u] 的系数的！见鬼。
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
int N,M,Opt,X,Y;lolo A[MaxN],Z;
struct SegTree{int cl[MaxN<<2],cr[MaxN<<2],cmid[MaxN<<2];lolo sum[MaxN<<2],tag[MaxN<<2];int ls(int u){return u<<1;}int rs(int u){return (u<<1)|1;}void pushup(int u){sum[u]=sum[ls(u)]+sum[rs(u)];}void build(int u,int l,int r){cl[u]=l,cr[u]=r;if(l==r){sum[u]=A[l];return;}int mid=(l+r)>>1;cmid[u]=mid;build(ls(u),l,mid),build(rs(u),mid+1,r),pushup(u);}void maketag(int u,lolo x){sum[u]+=(cr[u]-cl[u]+1)*x,tag[u]+=x;}void pushdown(int u){if(tag[u])maketag(ls(u),tag[u]),maketag(rs(u),tag[u]),tag[u]=0;}void modify(int u,int dl,int dr,lolo x){if(dl<=cl[u]&&cr[u]<=dr){maketag(u,x);return;}pushdown(u);if(dl<=cmid[u])modify(ls(u),dl,dr,x);if(dr>cmid[u])modify(rs(u),dl,dr,x);pushup(u);}lolo getsum(int u,int dl,int dr){if(dl<=cl[u]&&cr[u]<=dr)return sum[u];pushdown(u);lolo res=0;if(dl<=cmid[u])res+=getsum(ls(u),dl,dr);if(dr>cmid[u])res+=getsum(rs(u),dl,dr);return res;}
}SgT;
int main(){readis(N,M);for(int i=1;i<=N;i++)readi(A[i]);SgT.build(1,1,N);for(int i=1;i<=M;i++){readis(Opt,X,Y);if(Opt==1)readi(Z),SgT.modify(1,X,Y,Z);if(Opt==2)writil(SgT.getsum(1,X,Y));}return 0;
}
做法解析二
区间加区间修树状数组。
首先，修改或查询 \([l,r]\) 都差分成 \([1,r]\) 和 \([1,l)\) 解决。
考虑求出原数组的差分数组 \(B\)。区间修改在差分数组上表现为两个单点改；对于区间查询显然有：\(\sum_{i=1}^p a_i=\sum_{i=1}^p (p+1-i)\times b_i=(p+1) \sum_{i=1}^p b_i-\sum_{i=1}^p i\times b_i\)。所以我们维护 \(\sum_{i=1}^p b_i\) 和 \(\sum_{i=1}^p i\times b_i\)。
代码实现二
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
int N,M,Opt;lolo X,Y,Z;
struct BinidTree{int n;lolo ta[MaxN],ts[MaxN];void init(int x){n=x;fill(ta,ta+n+1,0),fill(ts,ts+n+1,0);}int lowbit(int x){return x&(-x);}void add(int p,lolo x){for(int q=p;q&&q<=n;q+=lowbit(q))ta[q]+=x,ts[q]+=p*x;}void adds(int l,int r,lolo x){add(l,x),add(r+1,-x);}lolo gts(int p){lolo res=0;for(int q=p;q;res+=(p+1)*ta[q]-ts[q],q-=lowbit(q));return res;}lolo getsum(int l,int r){return gts(r)-gts(l-1);}
}BiT;
int main(){readis(N,M);BiT.init(N);for(int i=1;i<=N;i++)readi(X),BiT.adds(i,i,X);for(int i=1;i<=M;i++){readis(Opt,X,Y);if(Opt==1)readi(Z),BiT.adds(X,Y,Z);if(Opt==2)writil(BiT.getsum(X,Y));}return 0;
}
反思总结
\(\sum_{i=1}^p (p+1-i)\times b_i=(p+1)\sum_{i=1}^p i-\sum_{i=1}^p b_i\times b_i\)。记好。