线段树模板

2019-11-08 02:15:50

字体：大中小

来源：转载

供稿：网友

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int tree_maxsize = (1<<18) + 1;//代表最多的二叉树的节点const int maxn = 100000 + 10;//代表最多的元素typedef struct addtree{ //区间用[ql,qr],[l,r]表示 int t[tree_maxsize]; //向上更新区间和函数 //比如区间[1,8]我们要在5位置将原来的数加上2就需要传入(5,2,1,1,8) void update(int loc,int x,int k,int l,int r){ if(l==r) t[k]+=x; else{ int mid = l + (r-l)/2; if(loc<=mid) update(loc,x,k*2,l,mid); else update(loc,x,k*2+1,mid+1,r); t[k] = t[k*2] + t[k*2+1]; } } //查询区间和 //比如区间[1,8]我们要查询[3,6]区间的区间和就要传入(3,6,1,1,8) int query(int ql,int qr,int k,int l,int r){ if(ql<=l && r<=qr) return t[k]; int mid = l + (r-l)/2,ans=0; if(ql<=mid) ans+=query(ql,qr,k*2,l,mid); if(mid+1<=qr) ans+=query(ql,qr,k*2+1,mid+1,r); return ans; }}addtree;//单点加上一个值求区间和的线段树addtree at;typedef struct mtree{ //区间用[ql,qr],[l,r]表示 int maxt[maxn * 4]; int mint[maxn * 4]; //向上更新区间最值 //比如区间[1,8]我们要在5位置将原来的数改为2就需要传入(5,2,1,1,8) void update(int loc,int x,int k,int l,int r){ if(l==r) {maxt[k]=x;mint[k]=x;} else{ int mid = l + (r-l)/2; if(loc<=mid) update(loc,x,k*2,l,mid); else update(loc,x,k*2+1,mid+1,r); maxt[k] = max(maxt[k*2],maxt[k*2+1]); mint[k] = min(mint[k*2],mint[k*2+1]); } } //查询区间最大值 //比如区间[1,8]我们要查询[3,6]区间内的最大值就要传入(3,6,1,1,8) int querymax(int ql,int qr,int k,int l,int r){ if(ql<=l && r<=qr) return maxt[k]; int mid = l + (r-l)/2,ans=-1; if(ql<=mid) ans = max(ans,querymax(ql,qr,k*2,l,mid)); if(mid+1<=qr) ans = max(ans,querymax(ql,qr,k*2+1,mid+1,r)); return ans; } int querymin(int ql,int qr,int k,int l,int r){ if(ql<=l && r<=qr) return mint[k]; int mid = l + (r-l)/2,ans=INF; if(ql<=mid) ans = min(ans,querymin(ql,qr,k*2,l,mid)); if(mid+1<=qr) ans = min(ans,querymin(ql,qr,k*2+1,mid+1,r)); return ans; }}mtree;//单点更新值求区间最值的线段树mtree mt;typedef struct lazytree{ //区间用[ql,qr),[l,r)来表示 int ta[tree_maxsize],tb[tree_maxsize]; //[ql,qr)区间所有的元素加上一个值x //比如我们要在[1,8]这个总的区间的[1,5]区间都加上1,就需要传入(1,6,1,1,9); void add(int ql,int qr,int x,int k,int l,int r){ if(ql<=l && r<= qr) ta[k]+=x; else if(l<qr && ql<r){ tb[k] += (min(qr,r) - max(ql,l)) * x; add(ql,qr,x,k*2,l,l+(r-l)/2); add(ql,qr,x,k*2+1,l+(r-l)/2,r); } } //查询区间和 //比如我们在[1,8]查询[5,5]时要传入(5,6,1,1,9) int query(int ql,int qr,int k,int l,int r){ if(qr<=l || r<=ql) return 0; else if(ql<=l && r<=qr) return ta[k]*(r-l) + tb[k]; else{ int ans = (min(qr,r) - max(ql,l)) * ta[k]; ans += query(ql,qr,k*2,l,l+(r-l)/2); ans += query(ql,qr,k*2+1,l+(r-l)/2,r); return ans; } }}lazytree;//区间加值求区间和的线段树lazytree lt;int main(){ int n,m,op;//说明数据范围是从1~n scanf("%d%d",&n,&m); memset(lt.ta,0,sizeof(lt.ta)); memset(lt.tb,0,sizeof(lt.tb)); for(int i=0;i<m;i++){ scanf("%d",&op); if(op==1){//代表修改某一个结点或者是在某一个结点上添加某一个值 int ql,qr,x; scanf("%d%d%d",&ql,&qr,&x); lt.add(ql,qr+1,x,1,1,n+1);//单个叶子结点用[x,x+1)表示,这里和不是lazy的线段树单点用[x,x]表示不同, } else{ int ql,qr; scanf("%d%d",&ql,&qr); PRintf("%d/n",lt.query(ql,qr+1,1,1,n+1)); } } return 0;}

经过测试上面的代码都没有问题，但是由于lazy的线段树是最后一个写的，所以只给出最后一组测试数据。该代码还可以根据不同的题目进行必要的修改

上一篇：华为OJ：句子逆序

下一篇：hdu 1754 I Hate It 【线段树】