線段樹模板

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); 經過測試上面的代碼都沒有問題，但是由于lazy的線段樹是最后一個寫的，所以只給出最后一組測試數據。該代碼還可以根據不同的題目進行必要的修改