线段树基础模板 发表于 2019-03-15 | 更新于 2019-08-09 | 分类于 线段树 | | 阅读次数: ℃ 字数统计: 799 | 阅读时长 ≈ 4 三个基本的线段树操作模板。 线段树单点更新+查询区间最大值HDU1754 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=1000000;int dat[maxn],n;int m,a,b;char op;void init(int x){ n=1; while(n<x) n*=2; for(int i=0;i<n*2-1;i++){ dat[i]=0; }}void update(int k,int a){ k+=n-1; dat[k]=a; while(k>0){ k=(k-1)/2; dat[k]=max(dat[k*2+1],dat[k*2+2]); }}int query(int a,int b,int k,int l,int r){ if(r<a || b<l) return 0; if(a<=l && r<=b) return dat[k]; else{ int vl=query(a,b,k*2+1,l,(l+r)/2); int vr=query(a,b,k*2+2,(l+r)/2+1,r); return max(vl,vr); }}int main(){ int n_; while(~scanf("%d %d",&n,&m)){ n_=n; init(n); for(int i=0;i<n_;i++){ scanf("%d",&dat[i+n-1]); update(i,dat[i+n-1]); } getchar(); while(m--){ scanf("%c %d %d",&op,&a,&b); getchar(); if(op=='Q') printf("%d\n",query(a-1,b-1,0,0,n-1)); else if(op=='U') update(a-1,b); } } return 0;} 线段树区间更新FZU1608 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=1000000;int n,m,dat[maxn];void init(int x){ n=1; while(n<x) n*=2; for(int i=0;i<n*2-1;i++){ dat[i]=0; }}void update(int a,int b,int x,int k,int l,int r){ if(b<l || r<a) return ; if(a<=l && r<=b) dat[k]=max(x,dat[k]); else{ update(a,b,x,k*2+1,l,(l+r)/2); update(a,b,x,k*2+2,(l+r)/2+1,r); }}int query(int l,int r,int k,int mmax){ if(l==r) return max(mmax,dat[k]); dat[k]=max(mmax,dat[k]); int vl=query(l,(l+r)/2,k*2+1,dat[k]); int vr=query((l+r)/2+1,r,k*2+2,dat[k]); return vl+vr;}int main(){ int a,b,x; while(~scanf("%d %d",&n,&m)){ init(n); for(int i=0;i<m;i++){ scanf("%d %d %d",&a,&b,&x); update(a,b-1,x,0,0,n-1); } printf("%d\n",query(0,n-1,0,0)); } return 0;} 线段树区间更新+区间求和POJ3468 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<stdio.h>#include<algorithm>using namespace std;#define ll long longconst ll maxn=1000000;ll dat[maxn],sum[maxn],n,m;void update(ll a,ll b,ll x,ll k,ll l,ll r){ if(a<=l && r<=b){ dat[k]+=x; } else if(l<=b && a<=r){ sum[k]+=(min(b,r)-max(a,l)+1)*x; update(a,b,x,k*2+1,l,(l+r)/2); update(a,b,x,k*2+2,(l+r)/2+1,r); }}ll query(ll a,ll b,ll k,ll l,ll r){ if(b<l || r<a) return 0; else if(a<=l && r<=b) return dat[k]*(r-l+1)+sum[k]; else{ ll res=(min(b,r)-max(a,l)+1)*dat[k]; res+=query(a,b,k*2+1,l,(l+r)/2); res+=query(a,b,k*2+2,(l+r)/2+1,r); return res; }}int main(){ ll a,b,x; char op; scanf("%lld %lld",&n,&m); for(int i=0;i<n;i++){ scanf("%lld",&x); update(i,i,x,0,0,n-1); } getchar(); while(m--){ scanf("%c",&op); if(op=='Q'){ scanf("%lld %lld",&a,&b); printf("%lld\n",query(a-1,b-1,0,0,n-1)); } else{ scanf("%lld %lld %lld",&a,&b,&x); update(a-1,b-1,x,0,0,n-1); } getchar(); } return 0;} 感谢您的支持 打赏 微信支付 支付宝 本文作者: Boctorio 本文链接: https://boctorio.github.io/2019/03/15/线段树基础模板/ 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处! -------------本文结束感谢您的阅读-------------