转载

线段树模板(持续更新)

线段树题目(持续更新)

\(1.\) \(GSS3\) \(-\) \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(III\)

\(2.\) 小白逛公园

\(3.\) \(GSS1\) \(-\) \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(I\)

\(4.\) \(GSS4\) \(-\) \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(IV\)

线段树单点修改、区间查询最大值

细节:所有操作都是从根节点( \(1\) 号点)开始遍历的;建树时从下往上传递信息;修改和查询的 \(mid\) 为该节点的左子节点的右端点。

\(View\) \(Code\)

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,q,a[500005],op,x,val,l,r,ans; struct SegmentTree { int l; int r; int val; }t[2000005]; void build(int pos,int l,int r) { t[pos].l=l; t[pos].r=r; if(l==r) { t[pos].val=a[l]; return; } int mid=(l+r)/2; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); t[pos].val=max(t[pos<<1].val,t[pos<<1|1].val); } void modify(int pos,int x,int val) { if(t[pos].l==t[pos].r) { t[pos].val=val; return; } int mid=(t[pos].l+t[pos].r)/2; if(x<=mid) modify(pos<<1,x,val); else modify(pos<<1|1,x,val); t[pos].val=max(t[pos<<1].val,t[pos<<1|1].val); } int query(int pos,int l,int r) { if(l<=t[pos].l&&t[pos].r<=r) return t[pos].val; int mid=(t[pos].l+t[pos].r)/2,val=-(1<<30); if(l<=mid) val=max(val,query(pos<<1,l,r)); if(mid<r) val=max(val,query(pos<<1|1,l,r)); return val; } int main() { n=read(); q=read(); for(register int i=1;i<=n;i++) a[i]=read(); build(1,1,n); while(q--) { op=read(); if(op==1) { x=read(); val=read(); modify(1,x,val); } else { l=read(); r=read(); ans=query(1,l,r); printf("%d\n",ans); } } return 0; }

线段树区间暴力修改、区间查询最大值

细节:区间修改和区间查询时均要遍历整个询问区间。(划重点!!!)

\(View\) \(Code\)

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } inline long long readl() { long long ret=0; int f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int tmp,n,q,op,l,r; long long a[100005]; struct SegmentTree { int l,r; long long sum,maxn; }t[400005]; void build(int pos,int l,int r) { t[pos].l=l; t[pos].r=r; if(l==r) { t[pos].sum=a[l]; t[pos].maxn=a[l]; return; } int mid=(l+r)/2; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum; t[pos].maxn=max(t[pos<<1].maxn,t[pos<<1|1].maxn); } void modify(int pos,int l,int r) { if(t[pos].l==t[pos].r) { t[pos].sum=(long long)sqrt(t[pos].sum); t[pos].maxn=(long long)sqrt(t[pos].maxn); return; } int mid=(t[pos].l+t[pos].r)/2; if(l<=mid&&1<t[pos<<1].maxn) modify(pos<<1,l,r); if(mid<r&&1<t[pos<<1|1].maxn) modify(pos<<1|1,l,r); t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum; t[pos].maxn=max(t[pos<<1].maxn,t[pos<<1|1].maxn); } long long query(int pos,int l,int r) { if(l<=t[pos].l&&t[pos].r<=r) return t[pos].sum; long long val=0; int mid=(t[pos].l+t[pos].r)/2; if(l<=mid) val+=query(pos<<1,l,r); if(mid<r) val+=query(pos<<1|1,l,r); return val; } int main() { n=read(); for(register int i=1;i<=n;i++) a[i]=readl(); build(1,1,n); q=read(); while(q--) { op=read(); l=read(); r=read(); if(r<l) { tmp=l; l=r; r=tmp; } if(!op) modify(1,l,r); else printf("%lld\n",query(1,l,r)); } return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11329986.html

正文到此结束
本文目录