关于线段树的一些算法的模板的汇总。
Luogu P3372
普通的线段树，区间加法，区间查询。
#includeusing namespace std;const int maxn = 100005;int n,m,x,y,flag;int l[4*maxn],r[4*maxn];long long lazy[8*maxn],sum[4*maxn];void build(int L,int R,int now) { lazy[now] = 0; l[now] = L; r[now] = R; if(L == R) { scanf("%lld",&sum[now]); return; } int mid = (L+R)/2; build(L,mid,now*2); build(mid+1,R,now*2+1); sum[now] = sum[now*2] + sum[now*2+1];}long long query(int L,int R,int now) { sum[now] += lazy[now] * (r[now] - l[now] + 1); lazy[now*2] += lazy[now]; lazy[now*2+1] += lazy[now]; lazy[now] = 0; if(l[now] == L && r[now] == R)return sum[now]; int mid = (l[now]+r[now])/2; if(R <= mid) return query(L,R,now*2); else if(L >= mid+1) return query(L,R,now*2+1); else return query(L,mid,now*2)+query(mid+1,R,now*2+1);}void modify(int L,int R,long long d,int now) { if(l[now] == L && r[now] == R) { lazy[now] += d; return; } sum[now] += (long long)d*(R-L+1); int mid = (l[now]+r[now])/2; if(R <= mid) modify(L,R,d,now*2); else if(L >= mid+1) modify(L,R,d,now*2+1); else { modify(L,mid,d,now*2); modify(mid+1,R,d,now*2+1); }}int main() { scanf("%d%d",&n,&m); build(1,n,1); while(m) { m--; scanf("%d",&flag); if(flag == 1) { long long k; scanf("%d%d%lld",&x,&y,&k); modify(x,y,k,1); } if(flag == 2) { scanf("%d%d",&x,&y); printf("%lld\n",query(x,y,1)); } } return 0;}
Luogu P3373
区间加法，区间乘法，区间查询。
注意：乘法标记优先于加法标记，打标记后直接（在原数的基础上）修改。
#include#include #include #include #define MogeKo qwqusing namespace std;#define ls (now<<1)#define rs (now<<1|1)const int maxn = 1e6+10;int n,q,p,op,x,y;long long k;int l[maxn<<2],r[maxn<<2];long long sum[maxn<<2],a[maxn<<3],m[maxn<<3];void build(int L,int R,int now) { l[now] = L; r[now] = R; m[now] = 1; a[now] = 0; if(L == R) { scanf("%lld",&k); sum[now] = k%p; return; } int mid = (l[now] + r[now])>>1; build(L,mid,ls); build(mid+1,R,rs); sum[now] = (sum[ls] + sum[rs])%p;}void pushdown(int now) { if(m[now]==1 && a[now]==0) return; m[ls] = (m[ls]*m[now])%p; m[rs] = (m[rs]*m[now])%p; a[ls] = (a[ls]*m[now] + a[now])%p; a[rs] = (a[rs]*m[now] + a[now])%p; sum[ls] = (sum[ls]*m[now] + a[now]*(long long)(r[ls]-l[ls]+1))%p; sum[rs] = (sum[rs]*m[now] + a[now]*(long long)(r[rs]-l[rs]+1))%p; m[now] = 1; a[now] = 0;}void modify(int L,int R,int now,long long A,long long M) { pushdown(now); if(l[now] == L && r[now] == R) { m[now] = (m[now]*M)%p; a[now] = (a[now]*M + A)%p; sum[now] = (sum[now]*M + A*(long long)(r[now]-l[now]+1))%p; return; } int mid = (l[now] + r[now])>>1; if(R <= mid) modify(L,R,ls,A,M); else if(L >= mid+1) modify(L,R,rs,A,M); else { modify(L,mid,ls,A,M); modify(mid+1,R,rs,A,M); } sum[now] = (sum[ls] + sum[rs])%p;}long long query(int L,int R,int now) { if(l[now] == L && r[now] == R) { return sum[now]%p; } pushdown(now); int mid = (l[now] + r[now])>>1; if(R <= mid) return query(L,R,ls)%p; else if(L >= mid+1) return query(L,R,rs)%p; else return (query(L,mid,ls) + query(mid+1,R,rs))%p;}int main() { scanf("%d%d%d",&n,&q,&p); build(1,n,1); while(q--) { scanf("%d%d%d",&op,&x,&y); if(op == 3) printf("%lld\n",query(x,y,1)); else { scanf("%lld",&k); if(op == 1) modify(x,y,1,0,k); if(op == 2) modify(x,y,1,k,1); } } return 0;}
Luogu P3834
这道模板题是求静态区间第$k$大的值。
对于每个前缀，建立一棵权值线段树，记录每个数字在当前的区间中出现了多少次，以及当前的区间中共有几个数字。
建树时，判断新加的数在左区间还是右区间，把当前的树不需要修改的儿子连向前一个状态，给另一个需要修改的儿子建立一个新节点，重复上一步。
查询时，用前缀和的方式求解。求出左区间共有多少个数（$sum[ls(v)]-sum[ls(u-1)]$），设为$lengthL$，然后与$k$的大小比较，
若$lengthL≥k$则在左儿子，否则在右儿子。注意，找右儿子时要把$k$减去左儿子已经找过的，即改为$k-lengthL$。
优化：给出的序列中可能不是每个数都出现的，一一对应效率较低，可以排序并去重。
（例如：给出1 2 5 5 8，可以直接建成(1)1,(2)2,(3)5,(4)8，而不是(1)1,(2)2,(3)3,(4)4,(5)5,(6)6,(7)7,(8)8 ）
#include#include #include #include #define MogeKo qwqusing namespace std;const int maxn = 200005;int a[maxn],b[maxn],T[maxn];int L[maxn<<5],R[maxn<<5],sum[maxn<<5];int cnt,n,q,m,t,u,v,k;int build(int l,int r){ int rt = ++cnt; int mid = (l+r)>>1; if(l < r){ L[rt] = build(l,mid); R[rt] = build(mid+1,r); } return rt;} int update(int pre,int l,int r,int x){ int rt = ++cnt; L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1; if(l < r){ int mid = (l+r)>>1; if(x <= mid) L[rt] = update(L[pre],l,mid,x); else R[rt] = update(R[pre],mid+1,r,x); } return rt;}int query(int u,int v,int l,int r,int k){ if(l == r)return l; int lenL = sum[L[v]] - sum[L[u]]; int mid = (l+r)>>1; if(k <= lenL) return query(L[u],L[v],l,mid,k); else return query(R[u],R[v],mid+1,r,k-lenL);} int main(){ scanf("%d%d",&n,&q); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); b[i] = a[i]; } sort(b+1,b+n+1); m = unique(b+1,b+n+1)-(b+1); T[0] = build(1,m); for(int i = 1;i <= n;i++){ t = lower_bound(b+1,b+m+1,a[i])-b; T[i] = update(T[i-1],1,m,t); } for(int i = 1;i <= q;i++){ scanf("%d%d%d",&u,&v,&k); printf("%d\n",b[query(T[u-1],T[v],1,m,k)]); } return 0;}