线段树有两个操作，pushup跟pushdown
这节课用到pushup和build和modify和query四个操作，分别是用子节点算父节点的信息，用堆的形式建一维数组的线段树，修改单点操作，查询某段区间的信息
build操作
query操作
modify操作
直接递归到子节点x在pushup就行，因为是递归每个父区间都会pushup到，也即更新到
1.最大数
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
先建好线段树
第一个操作就是在n+1的位置修改成x，第二个操作就是查询[n-l+1,n]的最大值
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,p,m; struct Node { int l,r; int v; }tr[4*N];//建线段树要开4倍空间 void pushup(int u)//用子节点信息更新父节点信息 { tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v); } void build(int u,int l,int r)//建一颗线段树 { tr[u]={l,r}; if(l==r) return; int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r);//建左右子区间 } int query(int u,int l,int r)//询问从某个父节点开始，问l,r的区间最大值 { if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;//假如这个父节点在区间中直接返回这个父节点的最大值 int mid=tr[u].l+tr[u].r>>1; int v=0; if(l<=mid) v=query(u<<1,l,r);//假如左边覆盖到了，取左区间的值 if(r>mid) v=max(v,query(u<<1|1,l,r));//假如右边覆盖到了，取右区间的值，并且更新一下最大值 return v;//返回最大值 } void modify(int u,int x,int v)//修改某个位置的值 { if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;//假如找到了这个位置，直接修改这个位置的值 else { int mid=tr[u].l+tr[u].r>>1; if(x<=mid) modify(u<<1,x,v);//假如这个值在左区间，则递归左区间进行查找这个值进行修改 else modify(u<<1|1,x,v);//反之在右区间，则递归右区间进行查找这个值进行修改 pushup(u);//修改了之后这个父节点的值也要更新一下 } } int main() { scanf("%d%d",&m,&p); build(1,1,m); char op[2]; int l,last=0; while(m--) { scanf("%s%d",op,&l); if(*op=='Q') { last=query(1,n-l+1,n);//假如是询问则直接输出后l个数的最大值 printf("%d\n",last); } else { ++n; modify(1,n,(l+last)%p);//假如是添加一个数，则直接就在n+1的后面修改成这个数 } } return 0; }
2.你能回答这些问题吗
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; int n,m; int w[N]; struct Node { int l,r; int tmux,lmax,rmax,sum; }tr[4*N];//建线段树要开4倍空间 void pushup(Node& u,Node& l,Node& r)//用子节点信息更新父节点信息 { u.sum=l.sum+r.sum;//和等于两个子段和 u.lmax=max(l.lmax,l.sum+r.lmax);//左边最长字段和 = 左子树的左边最长子段和 与 左子段的和+右边的左边最大子段和 取最大值 u.rmax=max(r.rmax,l.rmax+r.sum);//右边最长字段和 = 右子树的右边最长子段和 与 左子段的最大右子段和+右边子段和 取最大值 u.tmux=max(max(l.tmux,r.tmux),l.rmax+r.lmax);//最长连续子段和 = 左边最长子段和 与 右边最长子段和 与 左边的后面+左边的前面 取最大 } void pushup(int u)//用子节点信息更新父节点信息 { pushup(tr[u],tr[u<<1],tr[u<<1|1]); } void build(int u,int l,int r)//建一颗线段树 { if(l==r) tr[u]={l,r,w[r],w[r],w[r],w[r]}; else { tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r);//建左右子区间 pushup(u);//更新一遍这个节点 } } Node query(int u,int l,int r)//询问从某个父节点开始，问l,r的区间最大连续子段和 { if(tr[u].l>=l&&tr[u].r<=r) return tr[u];//假如这个父节点在区间中直接返回这个父节点的最大连续区间子段和 int mid=tr[u].l+tr[u].r>>1; if(r<=mid) return query(u<<1,l,r);//假如整个区间在左边 if(l>mid) return query(u<<1|1,l,r);//假如整个区间在右边 auto left=query(u<<1,l,r),right=query(u<<1|1,l,r);//反之左右都有 Node ans; pushup(ans,left,right);//则求一边左右区间的最大值 return ans;//返回答案 } void modify(int u,int x,int v)//修改某个位置的值 { if(tr[u].l==x&&tr[u].r==x) tr[u]={x,x,v,v,v,v};//假如找到了这个位置，直接修改这个位置的值 else { int mid=tr[u].l+tr[u].r>>1; if(x<=mid) modify(u<<1,x,v);//假如这个值在左区间，则递归左区间进行查找这个值进行修改 else modify(u<<1|1,x,v);//反之在右区间，则递归右区间进行查找这个值进行修改 pushup(u);//修改了之后这个父节点的值也要更新一下 } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); build(1,1,n); int k,x,y; while(m--) { scanf("%d%d%d",&k,&x,&y); if(k&1) { if(x>y) swap(x,y); printf("%d\n",query(1,x,y).tmux);//输出查找后的答案 } else modify(1,x,y);//把x的位置的值改位y，递归处理 } return 0; }
3.区间最大公约数
246. 区间最大公约数 - AcWing题库
这里的线段树维护的是一个差分，假如添加则a[l]+=d,a[r+1]-=d
假如查询则gcd(a[l],gcd(b[l+1]~b[r])),也即a[l]这个元素与[l+1,r]这个区间的最大公约数取最大公约数
区间l,r的最大公约数等于差分后的数的最大公约数
1. #in#include<bits/stdc++.h> using namespace std; const int N=5e5+10; typedef long long ll; int n,m; ll w[N]; struct Node { int l,r; ll sum,d; }tr[4*N]; ll gcd(ll a,ll b)//求最大公约数 { return b?gcd(b,a%b):a; } void pushup(Node& u,Node& l,Node& r)//用子节点信息更新父节点信息 { u.sum=l.sum+r.sum;//父节点的和等于子节点的两个和的和 u.d=gcd(l.d,r.d);//父节点最小公倍数等于两个子节点的最小公倍数 } void pushup(int u)//用来更新父节点信息 { pushup(tr[u],tr[u<<1],tr[u<<1|1]); } void built(int u,int l,int r)//建立线段树 { if(l==r) { ll b=w[l]-w[l-1];//换成差分数组 tr[u]={l,r,b,b}; } else { tr[u]={l,r}; int mid=l+r>>1; built(u<<1,l,mid),built(u<<1|1,mid+1,r);//建左右子树 pushup(u);//更新一遍节点信息 } } void modify(int u,int x,ll v)//用来更改信息 { if(tr[u].l==x&&tr[u].r==x)//假如找到了这个点 { ll sum=tr[u].sum+v;//这个点加上这个数 tr[u]={x,x,sum,sum};//更新 } else { int mid=tr[u].l+tr[u].r>>1; if(x<=mid) modify(u<<1,x,v);//假如这个点在左边 else modify(u<<1|1,x,v);//假如这个点在右边 pushup(u);//更新一下节点信息 } } Node query(int u,int l,int r)//查找某个区间 { if(tr[u].l>=l&&tr[u].r<=r) return tr[u];//假如这个区间在查找区间内，则返回 int mid=tr[u].l+tr[u].r>>1; if(r<=mid) return query(u<<1,l,r);//假如在左边，则查找左边 if(l>mid) return query(u<<1|1,l,r);//假如在右边，则查找右边 auto left=query(u<<1,l,r),right=query(u<<1|1,l,r);//反之在左右区间内 Node res; pushup(res,left,right);//用左右区间更新一下答案 return res;//返回答案 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); built(1,1,n); char op[2]; int l,r; ll d; while(m--) { scanf("%s",op); if(*op=='Q') { scanf("%d%d",&l,&r); auto id1=query(1,1,l);//先查找a[l]，也即id1.sum if(l+1<=n)//假如右边有数 { auto id2=query(1,l+1,r);//则查找一遍右边的最大公约数 printf("%lld\n",abs(gcd(id1.sum,id2.d)));//求两个最大公约数 } else printf("%lld\n",abs(id1.sum));//反之没有右边的数，直接输出 } else { scanf("%d%d%lld",&l,&r,&d); modify(1,l,d);//b[l]+=d if(r+1<=n) modify(1,r+1,-d);//b[r+1]-=d } } return 0; }
