赤裸裸的线段树
#include<iostream> #include<cstdio> #include<algorithm> #define Max(a,b) (a>b)?a:b using namespace std; const int MAX_N=100005*4;//至少要开2*n-1个空间 typedef long long LL; struct node{ int l,r,max; LL sum; }; node a[MAX_N]; void build(int n,int l,int r) { a[n].l=l; a[n].r=r; a[n].max=-1; a[n].sum=0; if(l==r) { return ; } build(2*n,l,(l+r)/2); build(2*n+1,(l+r)/2+1,r); } void insert(int n, int pos,int val) { a[n].sum+=val; a[n].max=max(a[n].max,val); if(a[n].l==pos&&a[n].r==pos) { return ; } int mid=(a[n].l+a[n].r)/2; if(pos<=mid) insert(2*n,pos,val); else insert(2*n+1,pos,val); } void change(int n,int pos,int val) { if(a[n].l==pos&&a[n].r==pos) { a[n].max=val; a[n].sum=val; return ; } int mid=(a[n].l+a[n].r)/2; if(pos<=mid) change(2*n,pos,val); else change(2*n+1,pos,val); a[n].max=max(a[2*n].max,a[2*n+1].max); a[n].sum=a[2*n].sum+a[2*n+1].sum; } int Qmax(int n,int l,int r) { if(a[n].l==l&&a[n].r==r) { return a[n].max; } int mid=(a[n].l+a[n].r)/2; if(r<=mid) { return Qmax(2*n,l,r); } else if(mid<l) { return Qmax(2*n+1,l,r); } else { return Max(Qmax(2*n,l,mid),Qmax(2*n+1,mid+1,r)); } } LL Qsum(int n,int l, int r) { if(a[n].l==l&&a[n].r==r) { return a[n].sum; } int mid=(a[n].l+a[n].r)/2; if(r<=mid) { return Qsum(2*n,l,r); } else if(l>mid) { return Qsum(2*n+1,l,r); } return Qsum(2*n,l,mid)+Qsum(2*n+1,mid+1,r); } int main() { int n,m; scanf("%d %d",&n,&m); build(1,1,n); for(int i=1;i<=n;i++) { int v; scanf("%d",&v); insert(1,i,v); } while(m--) { int op,x,y; scanf("%d %d %d",&op,&x,&y); switch(op) { case 1:{ change(1,x,y); break; } case 2:{ printf("%lld ",Qsum(1,x,y)); break; } case 3:{ printf("%d ",Qmax(1,x,y)); break; } } } return 0; }
下面代码简介但时间慢
#include<cstdio> #include<algorithm> #define lson n<<1,l,mid #define rson n<<1|1,mid+1,r #define ENmax a[n].max=max(a[n<<1].max,a[n<<1|1].max) #define ENsum a[n].sum=a[n<<1].sum+a[n<<1|1].sum using namespace std; const int MAX_N=100005; typedef long long LL; struct node{ int l,r,max; LL sum; }; node a[MAX_N<<2]; void Build(int n,int l,int r) { a[n].l=l; a[n].r=r; if(l==r) { scanf("%d",&a[n].sum); a[n].max=a[n].sum; return ; } int mid=(l+r)>>1; Build(lson); Build(rson); ENmax; ENsum; } void Update(int n,int pos,int val) { if(a[n].l==pos&&a[n].r==pos) { a[n].max=a[n].sum=val; return ; } int mid=(a[n].l+a[n].r)>>1; if(pos<=mid) Update(n<<1,pos,val); else Update(n<<1|1,pos,val); ENsum; ENmax; } LL Qsum(int n,int l,int r) { if(a[n].l==l&&a[n].r==r) { return a[n].sum; } int mid=(a[n].l+a[n].r)>>1; if(r<=mid) return Qsum(n<<1,l,r); else if(mid<l) return Qsum(n<<1|1,l,r); else return Qsum(lson)+Qsum(rson); } int Qmax(int n,int l,int r) { if(a[n].l==l&&a[n].r==r) { return a[n].max; } int mid=(a[n].l+a[n].r)>>1; if(r<=mid) return Qmax(n<<1,l,r); else if(mid<l) return Qmax(n<<1|1,l,r); else return max(Qmax(lson),Qmax(rson)); } int main() { int n,m; scanf("%d%d",&n,&m); Build(1,1,n); while(m--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1) Update(1,x,y); else if(op==2) printf("%d ",Qsum(1,x,y)); else printf("%d ",Qmax(1,x,y)); } return 0; }