當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

ACM-线段树

發(fā)布時(shí)間：2025/4/14 编程问答 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 ACM-线段树小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

http://blog.csdn.net/libin56842/article/details/8530197

基礎(chǔ)可以看上面這篇文章

風(fēng)格：

maxn是題目給的最大區(qū)間，而節(jié)點(diǎn)數(shù)要開(kāi)4倍，確切的說(shuō)……

lson和rson辨別表示結(jié)點(diǎn)的左孩子和右孩子。

PushUp(int rt)是把當(dāng)前結(jié)點(diǎn)的信息更新到父節(jié)點(diǎn)

PushDown（int rt)是把當(dāng)前結(jié)點(diǎn)的信息更新給孩子結(jié)點(diǎn)。

rt表示當(dāng)前子樹(shù)的根（root），也就是當(dāng)前所在的結(jié)點(diǎn)。

思想：

對(duì)于每個(gè)非葉節(jié)點(diǎn)所標(biāo)示的結(jié)點(diǎn) [a,b]，其做孩子表示的區(qū)間是[a,(a+b)/2]，其右孩子表示[(a+b)/2,b].

構(gòu)造：

離散化和線段樹(shù)：

題目：x軸上有若干個(gè)線段，求線段覆蓋的總長(zhǎng)度。

普通解法：設(shè)置坐標(biāo)范圍[min,max],初始化為0，然后每一段分別染色為1，最后統(tǒng)計(jì)1的個(gè)數(shù)，適用于線段數(shù)目少，區(qū)間范圍小。

離散化的解法：離散化就是一一映射的關(guān)系，即將一個(gè)大坐標(biāo)和小坐標(biāo)進(jìn)行一一映射，適用于線段數(shù)目少，區(qū)間范圍大。

例如：[10000,22000],[30300,55000],[44000,60000],[55000,60000].

第一步：排序 10000 22000 30300 44000 55000 60000

第二部：編號(hào) 1 ? ? ? ?2 ? ? ? ?3 ? ? ? ? 4 ? ? ? 5 ? ? ? ? 6

第三部：用編號(hào)來(lái)代替原數(shù)，即小數(shù)代大數(shù) 。

[10000,22000]~[1,2]

[30300,55000]~[3,5]

[44000,60000]~[4,6]

[55000,60000]~[5,6]

然后再用小數(shù)進(jìn)行普通解法的步驟，最后代換回去。

線段樹(shù)的解法：線段樹(shù)通過(guò)建立線段，將原來(lái)染色O(n)的復(fù)雜度減小到 log（n），適用于線段數(shù)目多，區(qū)間范圍小的情況。

離散化的線段樹(shù)：適用于線段數(shù)目多，區(qū)間范圍大的情況。

構(gòu)造：

動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)：

struct node{

?node* left;

?node* right;

……

}

靜態(tài)全局?jǐn)?shù)組模擬（完全二叉樹(shù)）：

struct node{

? int left;

? int right;

……

}Tree[MAXN]

http://www.xuebuyuan.com/1470670.html

線段樹(shù)主要用四種用法

單點(diǎn)更新：

模板：

單點(diǎn)增減，查詢(xún)線段和

struct node {int l,r,c; }T[MAXN*4];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c; }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 0;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1); }void update(int val,int l,int x) {if(T[x].l == T[x].r && T[x].l == l){T[x].c += val;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){update(val,l,(x<<1) + 1);}else{update(val,l,x<<1);}PushUp(x); }int n,m,ans;void query(int l,int r,int x) {if(T[x].l == l && T[x].r == r){ans += T[x].c;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){query(l,r,(x<<1)+1);}else if(r<=mid){query(l,r,(x<<1));}else{query(l,mid,(x<<1));query(mid+1,r,(x<<1)+1);} }

HDU 1166

#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std;#define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 55555 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3fstruct node {int l,r,c; }T[MAXN*4];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c; }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 0;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1); }void update(int val,int l,int x) {if(T[x].l == T[x].r && T[x].l == l){T[x].c += val;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){update(val,l,(x<<1) + 1);}else{update(val,l,x<<1);}PushUp(x); }int n,m,ans;void query(int l,int r,int x) {if(T[x].l == l && T[x].r == r){ans += T[x].c;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){query(l,r,(x<<1)+1);}else if(r<=mid){query(l,r,(x<<1));}else{query(l,mid,(x<<1));query(mid+1,r,(x<<1)+1);} }int main() {int t,i,kase=1;char d[10];sf("%d",&t);while(t--){mem(T,0);pf("Case %d:\n",kase++);sf("%d",&n);build(1,n,1);for(i=1;i<=n;i++){int tmp;sf("%d",&tmp);update(tmp,i,1);}while (sf("%s",d) != EOF){if (d[0] == 'E') break;int x, y;sf("%d%d", &x, &y);if (d[0] == 'Q'){ans = 0;query(x,y,1);pf("%d\n",ans);}if (d[0] == 'S') update(-y,x,1);if (d[0] == 'A') update(y,x,1);}}return 0; }

單點(diǎn)替換，查詢(xún)線段最高

模板：

struct node {int l,r,c; }T[MAXN*4];void PushUp(int rt) {T[rt].c = max(T[rt<<1].c,T[(rt<<1)+1].c); }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 0;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1); }void update(int val,int l,int x) {if(T[x].l == T[x].r && T[x].l == l){T[x].c = val;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){update(val,l,(x<<1) + 1);}else{update(val,l,x<<1);}PushUp(x); }int n,m,ans;void query(int l,int r,int x) {if(T[x].l == l && T[x].r == r){ans = max(ans,T[x].c);return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){query(l,r,(x<<1)+1);}else if(r<=mid){query(l,r,(x<<1));}else{query(l,mid,(x<<1));query(mid+1,r,(x<<1)+1);} }

hdu 1754

這邊要注意，輸入字符不要用%c，會(huì)導(dǎo)致一些難以預(yù)料的問(wèn)題

#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std;#define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 200005 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3fstruct node {int l,r,c; }T[MAXN*4];void PushUp(int rt) {T[rt].c = max(T[rt<<1].c,T[(rt<<1)+1].c); }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 0;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1); }void update(int val,int l,int x) {if(T[x].l == T[x].r && T[x].l == l){T[x].c = val;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){update(val,l,(x<<1) + 1);}else{update(val,l,x<<1);}PushUp(x); }int n,m,ans;void query(int l,int r,int x) {if(T[x].l == l && T[x].r == r){ans = max(ans,T[x].c);return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){query(l,r,(x<<1)+1);}else if(r<=mid){query(l,r,(x<<1));}else{query(l,mid,(x<<1));query(mid+1,r,(x<<1)+1);} }int main() {int t,i,kase=1;while(sf("%d%d",&n,&m)==2){build(1,n,1);for(i=1;i<=n;i++){int tmp;sf("%d",&tmp);update(tmp,i,1);}while (m--){int x,y;char d[2];sf("%s %d %d",d,&x, &y);//pf("%s %d %d\n",d,x,y);if (d[0] == 'Q'){ans = 0;query(x,y,1);pf("%d\n",ans);}if (d[0] == 'U') update(y,x,1);}}return 0; }

成段更新

(通常這對(duì)初學(xué)者來(lái)說(shuō)是一道坎),需要用到延遲標(biāo)記(或者說(shuō)懶惰標(biāo)記),簡(jiǎn)單來(lái)說(shuō)就是每次更新的時(shí)候不要更新到底,用延遲標(biāo)記使得更新延遲到下次需要更新or詢(xún)問(wèn)到的時(shí)候

http://blog.sina.com.cn/s/blog_a2dce6b30101l8bi.html

區(qū)間替換，求總和

數(shù)組要開(kāi)4倍才夠

第一種思路，標(biāo)記

模板：

struct node {int l,r,c,f; }T[MAXN<<2];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c;//pf("%d %d\n",rt,T[rt].c); }void PushDown(int rt,int m) {if(T[rt].f){T[rt<<1].f = T[(rt<<1) + 1].f = T[rt].f;T[rt<<1].c = T[rt].f * (m-(m>>1));T[(rt<<1)+1].c = T[rt].f * (m>>1);T[rt].f = 0;} }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 1;T[x].f = 0;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1);PushUp(x); }void update(int val,int L,int R,int l,int r,int x) {if(L <= l && r <= R){T[x].f = val;T[x].c = val*(r-l+1);//pf("%d %d %d\n",T[x].c,l,r);return;}PushDown(x,r-l+1);//pf("%d %d %d %d %d %d\n",val,L,R,l,r,x);int mid = (l + r)>>1;if (L <= mid){update(val,L,R,l,mid,x<<1);}if(R > mid){update(val,L,R,mid+1,r,x<<1|1);}PushUp(x); }

第二種思路，雜色

struct node {int l,r,c; }T[MAXN<<2];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c; }void PushDown(int rt) {if(T[rt].c != -1)//如果該區(qū)間只有一種顏色 {T[rt<<1].c = T[rt<<1|1].c = T[rt].c;//由于后面必定對(duì)子樹(shù)操作，所以更新子樹(shù)的值等于父親的值T[rt].c = -1;//由于該區(qū)域顏色與修改不同，而且不是給定區(qū)域，所以該區(qū)域必定為雜色 } }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 1;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1); }void update(int val,int L,int R,int x) {if(T[x].c == val) return;//相同則不用修改了if(T[x].l == L && T[x].r == R)//找到了區(qū)間，直接更新 {T[x].c = val;return;}PushDown(x);//父區(qū)間為雜色時(shí)對(duì)所有子節(jié)點(diǎn)進(jìn)行操作int mid = (T[x].l + T[x].r)>>1;if(L>mid)update(val,L,R,x<<1|1);else if(R<=mid)update(val,L,R,x<<1);else{update(val,L,mid,x<<1);update(val,mid+1,R,x<<1|1);} }

hdu 1698

http://www.tuicool.com/articles/j6N3eaz

這里鏈接的其實(shí)不對(duì)，要求總和，所以每個(gè)點(diǎn)不能初始化為1

#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std;#define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 100000 + 5 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3fstruct node {int l,r,c,f; }T[MAXN<<2];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c;//pf("%d %d\n",rt,T[rt].c); }void PushDown(int rt,int m) {if(T[rt].f){T[rt<<1].f = T[(rt<<1) + 1].f = T[rt].f;T[rt<<1].c = T[rt].f * (m-(m>>1));T[(rt<<1)+1].c = T[rt].f * (m>>1);T[rt].f = 0;} }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].c = 1;T[x].f = 0;if (l == r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1);PushUp(x); }void update(int val,int L,int R,int l,int r,int x) {if(L <= l && r <= R){T[x].f = val;T[x].c = val*(r-l+1);//pf("%d %d %d\n",T[x].c,l,r);return;}PushDown(x,r-l+1);//pf("%d %d %d %d %d %d\n",val,L,R,l,r,x);int mid = (l + r)>>1;if (L <= mid){update(val,L,R,l,mid,x<<1);}if(R > mid){update(val,L,R,mid+1,r,x<<1|1);}PushUp(x); }int n,m,ans;void query(int l,int r,int x) {if(T[x].l == l && T[x].r == r){ans += T[x].c;return;}int mid = (T[x].l + T[x].r)>>1;if (l > mid){query(l,r,(x<<1)+1);}else if(r<=mid){query(l,r,(x<<1));}else{query(l,mid,(x<<1));query(mid+1,r,(x<<1)+1);} }int a[MAXN];int main() {int t,i,kase=1;sf("%d",&t);while(t--){sf("%d",&n);build(1,n,1);sf("%d",&m);for(i=1;i<=m;i++){int x,y,z;sf("%d%d%d",&x,&y,&z);update(z,x,y,1,n,1);}pf("Case %d: The total value of the hook is %d.\n",kase++,T[1].c);}return 0; }

區(qū)間增減，區(qū)間求和

模板：

struct node {LL l,r,c,f; }T[MAXN<<2];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c;//pf("%d %d\n",rt,T[rt].c); }void PushDown(int rt,int m) {if(T[rt].f){T[rt<<1].f += T[rt].f;T[(rt<<1) + 1].f += T[rt].f;T[rt<<1].c += T[rt].f * (m-(m>>1));T[(rt<<1)+1].c += T[rt].f * (m>>1);T[rt].f = 0;} }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].f = 0;T[x].c = 0;if(l==r) return;int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1); }void update(int val,int L,int R,int l,int r,int x) {if(L <= l && r <= R){T[x].f += val;T[x].c += val*(r-l+1);//pf("%d %d %d\n",T[x].c,l,r);return;}PushDown(x,r-l+1);//pf("%d %d %d %d %d %d\n",val,L,R,l,r,x);int mid = (l + r)>>1;if (L <= mid){update(val,L,R,l,mid,x<<1);}if(R > mid){update(val,L,R,mid+1,r,x<<1|1);}PushUp(x); }LL ans;int n,m;void query(int L,int R,int l,int r,int x) {if(L <= l && r <= R){ans += T[x].c;return;}PushDown(x,r-l+1);int mid = (l + r)>>1;if(L <= mid) query(L,R,l,mid,x<<1);if(R > mid) query(L,R,mid+1,r,x<<1|1);PushUp(x); }

poj 3468

#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std;#define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 111111 + 5 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3fstruct node {LL l,r,c,f; }T[MAXN<<2];void PushUp(int rt) {T[rt].c = T[rt<<1].c + T[(rt<<1)+1].c;//pf("%d %d\n",rt,T[rt].c); }void PushDown(int rt,int m) {if(T[rt].f){T[rt<<1].f += T[rt].f;T[(rt<<1) + 1].f += T[rt].f;T[rt<<1].c += T[rt].f * (m-(m>>1));T[(rt<<1)+1].c += T[rt].f * (m>>1);T[rt].f = 0;} }void build(int l,int r,int x) {T[x].l = l;T[x].r = r;T[x].f = 0;if(l==r){scanf("%I64d",&T[x].c);return;}int mid = (l+r)>>1;build(l,mid,x<<1);build(mid+1,r,(x<<1) + 1);PushUp(x); }void update(int val,int L,int R,int l,int r,int x) {if(L <= l && r <= R){T[x].f += val;T[x].c += val*(r-l+1);//pf("%d %d %d\n",T[x].c,l,r);return;}PushDown(x,r-l+1);//pf("%d %d %d %d %d %d\n",val,L,R,l,r,x);int mid = (l + r)>>1;if (L <= mid){update(val,L,R,l,mid,x<<1);}if(R > mid){update(val,L,R,mid+1,r,x<<1|1);}PushUp(x); }LL ans;int n,m;void query(int L,int R,int l,int r,int x) {if(L <= l && r <= R){ans += T[x].c;return;}PushDown(x,r-l+1);int mid = (l + r)>>1;if(L <= mid) query(L,R,l,mid,x<<1);if(R > mid) query(L,R,mid+1,r,x<<1|1); }int main() {int t,i,kase=1;while(~sf("%d%d",&n,&m)){build(1,n,1);/*for(i=1;i<=n;i++){int tmp;sf("%d",&tmp);update(tmp,i,i,1,n,1);}*/for(i=1;i<=m;i++){int x,y,z;char s[2];sf("%s",s);if(s[0]=='Q'){ans = 0;sf("%d%d",&x,&y);query(x,y,1,n,1);pf("%I64d\n",ans);}else{sf("%d%d%d",&x,&y,&z);update(z,x,y,1,n,1);}}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/qlky/p/5690265.html

總結(jié)

以上是生活随笔為你收集整理的ACM-线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

ACM
线段

上一篇：初识--AVSpeechSynthesi
下一篇：基础拾遗------委托详解