文章目錄

• 問題
• 解析
• • 單點修改
• 詢問
• 完整代碼
• 標記永久化
• • 代碼

所謂二維線段樹，就是有兩個維度的線段樹

(逃)

問題

給出一個矩形
要求支持以下操作：

1.詢問一個子矩形的最值
2.修改某一個單點的值

解析

使用線段樹套線段樹，來解決二維動態問題
注意這個東西只能支持單點修改，區間查詢
區間改直接死翹翹

對于x軸開一個線段樹
每個結點對應一個y方向[1,n]的長條
時空復雜度$qlog{n}^2$

在求和問題時不妨用map套樹狀樹組
就可以支持區間修改了
而且代碼號寫許多
但缺陷是時間復雜度由于套map變成了3log
跑得飛慢qwq

單點修改

由于這個矩形可能很大（比如長寬1e5級別）
我們可能無法把整棵線段樹存下來
所以使用x方向直接開，y方向動態開點
為什么x方向不動態開點？因為那實在是太不好寫了…
那如果長寬1e9級別怎么辦？你去死吧

注意x方向修改完往上遞歸的時候要遞歸到對應的y方向的葉子更新信息
具體實現的時候我開了一個map，$m{p}_{i,j}$記錄x方向編號為i的樹的y方向上j號葉子結點的編號（如果沒看明白看代碼就清楚了）
這樣時空復雜度還是對的
注意map賦值的位置，不然可能使你憑空變成三個log

map<int,int>mp[N<<2]; void change(int line,int &k,int l,int r,int p,int v,int flag=0){if(!k){k=New();if(l==r) mp[line][p]=k;}if(l==r){if(flag==0) tr[k].mx=tr[k].mn=v;else{int L=mp[line<<1][p],R=mp[line<<1|1][p];tr[k].mx=max(tr[L].mx,tr[R].mx);tr[k].mn=min(tr[L].mn,tr[R].mn);}return;}if(p<=mid) change(line,tr[k].ls,l,mid,p,v,flag);else change(line,tr[k].rs,mid+1,r,p,v,flag);pushup(k);return; } void Add(int k,int l,int r,int x,int y,int v){if(l==r){change(k,rt[k],1,n,y,v,0);return;}if(x<=mid) Add(k<<1,l,mid,x,y,v);else Add(k<<1|1,mid+1,r,x,y,v);change(k,rt[k],1,n,y,v,1);return; }

詢問

二維線段樹主要難寫的地方其實就是修改
詢問相比之下就比較常規了
直接遞歸到對應的樹上取答案即可
這里貼一個取max的

int askmx(int k,int l,int r,int x,int y){if(!k) return -2e9;if(x<=l&&r<=y){return tr[k].mx;}int res=-2e9;if(x<=mid) Max(res,askmx(tr[k].ls,l,mid,x,y));if(y>mid) Max(res,askmx(tr[k].rs,mid+1,r,x,y));return res; } int Querymx(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1<=l&&r<=x2){return askmx(rt[k],1,n,y1,y2);}int res=-2e9;if(x1<=mid) Max(res,Querymx(k<<1,l,mid,x1,y1,x2,y2));if(x2>mid) Max(res,Querymx(k<<1|1,mid+1,r,x1,y1,x2,y2));return res; }

完整代碼

板子題

#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline const int N=850; const int M=3e6+100; const int mod=998244353; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m;inline void Max(int &x,int y){x=max(x,y);} inline void Min(int &x,int y){x=min(x,y);} int rt[N<<2]; struct tree{int mx,mn,ls,rs; }tr[M]; int tot; #define mid ((l+r)>>1) inline int New(){++tot;tr[tot].mx=-2e9;tr[tot].mn=2e9;tr[tot].ls=tr[tot].rs=0;return tot; } inline void pushup(int x){tr[x].mx=max(tr[tr[x].ls].mx,tr[tr[x].rs].mx);tr[x].mn=min(tr[tr[x].ls].mn,tr[tr[x].rs].mn);return; } map<int,int>mp[N<<2]; void change(int line,int &k,int l,int r,int p,int v,int flag=0){if(!k){k=New();if(l==r) mp[line][p]=k;}if(l==r){if(flag==0) tr[k].mx=tr[k].mn=v;else{int L=mp[line<<1][p],R=mp[line<<1|1][p];tr[k].mx=max(tr[L].mx,tr[R].mx);tr[k].mn=min(tr[L].mn,tr[R].mn);}return;}if(p<=mid) change(line,tr[k].ls,l,mid,p,v,flag);else change(line,tr[k].rs,mid+1,r,p,v,flag);pushup(k);return; } void Add(int k,int l,int r,int x,int y,int v){if(l==r){change(k,rt[k],1,n,y,v,0);return;}if(x<=mid) Add(k<<1,l,mid,x,y,v);else Add(k<<1|1,mid+1,r,x,y,v);change(k,rt[k],1,n,y,v,1);return; } int askmn(int k,int l,int r,int x,int y){if(!k) return 2e9;if(x<=l&&r<=y){return tr[k].mn;}int res=2e9;if(x<=mid) Min(res,askmn(tr[k].ls,l,mid,x,y));if(y>mid) Min(res,askmn(tr[k].rs,mid+1,r,x,y));return res; } int askmx(int k,int l,int r,int x,int y){if(!k) return -2e9;if(x<=l&&r<=y){return tr[k].mx;}int res=-2e9;if(x<=mid) Max(res,askmx(tr[k].ls,l,mid,x,y));if(y>mid) Max(res,askmx(tr[k].rs,mid+1,r,x,y));return res; } int Querymx(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1<=l&&r<=x2){return askmx(rt[k],1,n,y1,y2);}int res=-2e9;if(x1<=mid) Max(res,Querymx(k<<1,l,mid,x1,y1,x2,y2));if(x2>mid) Max(res,Querymx(k<<1|1,mid+1,r,x1,y1,x2,y2));return res; } int Querymn(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1<=l&&r<=x2){return askmn(rt[k],1,n,y1,y2);}int res=2e9;if(x1<=mid) Min(res,Querymn(k<<1,l,mid,x1,y1,x2,y2));if(x2>mid) Min(res,Querymn(k<<1|1,mid+1,r,x1,y1,x2,y2));return res; } int main(){tr[0].mx=-2e9;tr[0].mn=2e9;scanf("%d",&n);//if(o==3) break;memset(rt,0,sizeof(rt));tot=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=read();Add(1,1,n,i,j,x);}}m=read();for(int i=1;i<=m;i++){char c;scanf(" %c",&c);if(c=='c'){int x=read(),y=read(),v=read();Add(1,1,n,x,y,v);}else{int x1=read(),y1=read(),x2=read(),y2=read();int mx=Querymx(1,1,n,x1,y1,x2,y2),mn=Querymn(1,1,n,x1,y1,x2,y2);printf("%d %d\n",mx,mn);}}return 0; } /* 3 1 3 1 33 2 1 1 2 3 1 3 */

標記永久化

盡管二維線段樹無法實現區間賦值
但是在一些特殊的情況下可以通過騷操作使其具有區間賦值的功能
那就是這個！標記永久化
大概的思路就是x和y方向上都建兩棵樹，一棵是區間的最大值mx，一棵存該區間整體賦過的最大值tag
修改的時候沿途對所有的mx更新，并對最終子區間的tag更新
詢問的時候，如果是子區間，直接返回mx，否則先把res賦值成tag，再遞歸嘗試更新這個res
確實是挺妙的
但這個東西是有局限性的
就像它的名字一樣，這個標記無法撤銷
比如維護最大值的時候，如果可以把值改小，就炸了
更具體的細節看代碼吧

代碼

板子

#include<bits/stdc++.h> using namespace std; #define ll long long #define debug(a,b) fprintf(stderr,a,b) const int N=1030; const int mod=1e9+7; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m,k; struct node{int mx,tag,ls,rs; }tr[N*N*15]; int mx[N<<2],tag[N<<2],tot; #define mid ((l+r)>>1) int ask(int k,int l,int r,int x,int y){if(!k) return 0;if(x<=l&&r<=y){//printf("ask:k=%d (%d %d) (%d %d) mx=%d\n",k,l,r,x,y,tr[k].mx);return tr[k].mx;}int res=tr[k].tag;//printf("ask:k=%d (%d %d) (%d %d) tag=%d\n",k,l,r,x,y,tr[k].tag);if(x<=mid) res=max(res,ask(tr[k].ls,l,mid,x,y));if(y>mid) res=max(res,ask(tr[k].rs,mid+1,r,x,y));return res; } int Query(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1<=l&&r<=x2){int o=ask(mx[k],1,m,y1,y2);//printf("Query:k=%d (%d %d) [(%d %d),(%d %d)] mx=%d\n",k,l,r,x1,y1,x2,y2,o);return o;}int res=ask(tag[k],1,m,y1,y2);//printf("Query:k=%d (%d %d) [(%d %d),(%d %d)] tag=%d\n",k,l,r,x1,y1,x2,y2,res);if(x1<=mid) res=max(res,Query(k<<1,l,mid,x1,y1,x2,y2));if(x2>mid) res=max(res,Query(k<<1|1,mid+1,r,x1,y1,x2,y2));return res; } void change(int &k,int l,int r,int x,int y,int v){if(!k) k=++tot;tr[k].mx=max(tr[k].mx,v);if(x<=l&&r<=y){//printf("change:k=%d (%d %d) (%d %d) tag:v=%d\n",k,l,r,x,y,v);tr[k].tag=max(tr[k].tag,v);return;}if(x<=mid) change(tr[k].ls,l,mid,x,y,v);if(y>mid) change(tr[k].rs,mid+1,r,x,y,v);return; } void Add(int k,int l,int r,int x1,int y1,int x2,int y2,int v){change(mx[k],1,m,y1,y2,v);if(x1<=l&&r<=x2){change(tag[k],1,m,y1,y2,v);return;}if(x1<=mid) Add(k<<1,l,mid,x1,y1,x2,y2,v);if(x2>mid) Add(k<<1|1,mid+1,r,x1,y1,x2,y2,v);return; } int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endif//printf("%d\n",sizeof(tr)/1024/1024);n=read();m=read();k=read();++n;++m;for(int i=1;i<=k;i++){int l=read(),w=read(),h=read(),x=read(),y=read();x++;y++;int x1=x,y1=y,x2=x+l-1,y2=y+w-1;int mx=Query(1,1,n,x1,y1,x2,y2);Add(1,1,n,x1,y1,x2,y2,mx+h);//printf("(%d %d) (%d %d) mx=%d -> %d\n",x1,y1,x2,y2,mx,mx+h);}printf("%d\n",Query(1,1,n,1,1,n,m));return 0; }

總結

以上是生活随笔為你收集整理的模板：二维线段树（线段树套线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。