1、【完全版】線段樹很早前寫的那篇線段樹專輯至今一直是本博客閱讀點擊量最大的一片文章,當時覺得挺自豪的,還去pku打廣告,但是現在我自己都不太好意思去看那篇文章了,覺得當時的代碼風格實在是太丑了,很多線段樹的初學者可能就是看著這篇文章來練習的,如果不小心被我培養出了這么糟糕的風格,實在是過意不去,正好過幾天又要給集訓隊講解線段樹,所以決定把這些題目重新寫一遍,順便把近年我接觸到的一些新題更新上去;并且學習了splay等更高級的數據結構后對線段樹的體會有更深了一層,線段樹的寫法也就比以前飄逸,簡潔且方便多了.在代碼前先介紹一些我的線段樹風格:· maxn是題目給的最大區間,而節點數要開4倍

2、,確切的來說節點數要開大于maxn的最小2x的兩倍· lson和rson分辨表示結點的左兒子和右兒子,由于每次傳參數的時候都固定是這幾個變量,所以可以用預定于比較方便的表示· 以前的寫法是另外開兩個個數組記錄每個結點所表示的區間,其實這個區間不必保存,一邊算一邊傳下去就行,只需要寫函數的時候多兩個參數,結合lson和rson的預定義可以很方便· PushUP(int rt)是把當前結點的信息更新到父結點· PushDown(int rt)是把當前結點的信息更新給兒子結點· rt表示當前子樹的根(root),也就是當前所在的結點整理這些題目后我覺

3、得線段樹的題目整體上可以分成以下四個部分:· 單點更新:最最基礎的線段樹,只更新葉子節點,然后把信息用PushUP(int r)這個函數更新上來o hdu1166 敵兵布陣題意:O(-1)思路:O(-1)線段樹功能:update:單點增減 query:區間求和?View Code CPP12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <cstdio> #define ls

4、on l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 55555;int summaxn<<2;void PushUP(int rt) sumrt = sumrt<<1 + sumrt<<1|1;void build(int l,int r,int rt) if (l = r) scanf("%d",&sumrt);return ;int m = (l + r) >> 1;build(lson);build(

5、rson);PushUP(rt);void update(int p,int add,int l,int r,int rt) if (l = r) sumrt += add;return ;int m = (l + r) >> 1;if (p <= m) update(p , add , lson);else update(p , add , rson);PushUP(rt);int query(int L,int R,int l,int r,int rt) if (L <= l && r <= R) return sumrt;int m = (l

6、 + r) >> 1;int ret = 0;if (L <= m) ret += query(L , R , lson);if (R > m) ret += query(L , R , rson);return ret;int main() int T , n;scanf("%d",&T);for (int cas = 1 ; cas <= T ; cas +) printf("Case %d:n",cas);scanf("%d",&n);build(1 , n , 1);char op

7、10;while (scanf("%s",op) if (op0 = 'E') break;int a , b;scanf("%d%d",&a,&b);if (op0 = 'Q') printf("%dn",query(a , b , 1 , n , 1);else if (op0 = 'S') update(a , -b , 1 , n , 1);else update(a , b , 1 , n , 1);return 0;o hdu1754 I Hate It題意:

8、O(-1)思路:O(-1)線段樹功能:update:單點替換 query:區間最值?View Code CPP12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <cstdio>#include <algorithm>using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt &l

9、t;< 1 | 1const int maxn = 222222;int MAXmaxn<<2;void PushUP(int rt) MAXrt = max(MAXrt<<1 , MAXrt<<1|1);void build(int l,int r,int rt) if (l = r) scanf("%d",&MAXrt);return ;int m = (l + r) >> 1;build(lson);build(rson);PushUP(rt);void update(int p,int sc,int l,

10、int r,int rt) if (l = r) MAXrt = sc;return ;int m = (l + r) >> 1;if (p <= m) update(p , sc , lson);else update(p , sc , rson);PushUP(rt);int query(int L,int R,int l,int r,int rt) if (L <= l && r <= R) return MAXrt;int m = (l + r) >> 1;int ret = 0;if (L <= m) ret = max

11、(ret , query(L , R , lson);if (R > m) ret = max(ret , query(L , R , rson);return ret;int main() int n , m;while (scanf("%d%d",&n,&m) build(1 , n , 1);while (m -) char op2;int a , b;scanf("%s%d%d",op,&a,&b);if (op0 = 'Q') printf("%dn",query(a ,

12、 b , 1 , n , 1);else update(a , b , 1 , n , 1);return 0;o hdu1394 Minimum Inversion Number題意:求Inversion后的最小逆序數思路:用O(nlogn)復雜度求出最初逆序數后,就可以用O(1)的復雜度分別遞推出其他解線段樹功能:update:單點增減 query:區間求和?View Code CPP123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

13、55565758#include <cstdio>#include <algorithm>using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 5555;int summaxn<<2;void PushUP(int rt) sumrt = sumrt<<1 + sumrt<<1|1;void build(int l,int r,int rt) sumrt

14、 = 0;if (l = r) return ;int m = (l + r) >> 1;build(lson);build(rson);void update(int p,int l,int r,int rt) if (l = r) sumrt +;return ;int m = (l + r) >> 1;if (p <= m) update(p , lson);else update(p , rson);PushUP(rt);int query(int L,int R,int l,int r,int rt) if (L <= l && r

15、 <= R) return sumrt;int m = (l + r) >> 1;int ret = 0;if (L <= m) ret += query(L , R , lson);if (R > m) ret += query(L , R , rson);return ret;int xmaxn;int main() int n;while (scanf("%d",&n) build(0 , n - 1 , 1);int sum = 0;for (int i = 0 ; i < n ; i +) scanf("%d&

16、quot;,&xi);sum += query(xi , n - 1 , 0 , n - 1 , 1);update(xi , 0 , n - 1 , 1);int ret = sum;for (int i = 0 ; i < n ; i +) sum += n - xi - xi - 1;ret = min(ret , sum);printf("%dn",ret);return 0;o hdu2795 Billboard題意:h*w的木板,放進一些1*L的物品,求每次放空間能容納且最上邊的位子思路:每次找到最大值的位子,然后減去L線段樹功能:query:區間

17、求最大值的位子(直接把update的操作在query里做了)?View Code CPP123456789101112131415161718192021222324252627282930313233343536373839404142#include <cstdio>#include <algorithm>using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 222222;i

18、nt h , w , n;int MAXmaxn<<2;void PushUP(int rt) MAXrt = max(MAXrt<<1 , MAXrt<<1|1);void build(int l,int r,int rt) MAXrt = w;if (l = r) return ;int m = (l + r) >> 1;build(lson);build(rson);int query(int x,int l,int r,int rt) if (l = r) MAXrt -= x;return l;int m = (l + r) >&

19、gt; 1;int ret = (MAXrt<<1 >= x) ? query(x , lson) : query(x , rson);PushUP(rt);return ret;int main() while (scanf("%d%d%d",&h,&w,&n) if (h > n) h = n;build(1 , h , 1);while (n -) int x;scanf("%d",&x);if (MAX1 < x) puts("-1");else printf(&q

20、uot;%dn",query(x , 1 , h , 1);return 0;· 練習:o poj2828 Buy Ticketso poj2886 Who Gets the Most Candies?· 成段更新(通常這對初學者來說是一道坎),需要用到延遲標記(或者說懶惰標記),簡單來說就是每次更新的時候不要更新到底,用延遲標記使得更新延遲到下次需要更新or詢問到的時候o hdu1698 Just a Hook題意:O(-1)思路:O(-1)線段樹功能:update:成段替換 (由于只query一次總區間,所以可以直接輸出1結點的信息)?View Code

21、60;CPP123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <cstdio>#include <algorithm>using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 111111;int h , w , n;

22、int colmaxn<<2;int summaxn<<2;void PushUp(int rt) sumrt = sumrt<<1 + sumrt<<1|1;void PushDown(int rt,int m) if (colrt) colrt<<1 = colrt<<1|1 = colrt;sumrt<<1 = (m - (m >> 1) * colrt;sumrt<<1|1 = (m >> 1) * colrt;colrt = 0;void build(int l,i

23、nt r,int rt) colrt = 0;sumrt = 1;if (l = r) return ;int m = (l + r) >> 1;build(lson);build(rson);PushUp(rt);void update(int L,int R,int c,int l,int r,int rt) if (L <= l && r <= R) colrt = c;sumrt = c * (r - l + 1);return ;PushDown(rt , r - l + 1);int m = (l + r) >> 1;if (L

24、<= m) update(L , R , c , lson);if (R > m) update(L , R , c , rson);PushUp(rt);int main() int T , n , m;scanf("%d",&T);for (int cas = 1 ; cas <= T ; cas +) scanf("%d%d",&n,&m);build(1 , n , 1);while (m -) int a , b , c;scanf("%d%d%d",&a,&b,&a

25、mp;c);update(a , b , c , 1 , n , 1);printf("Case %d: The total value of the hook is %d.n",cas , sum1);return 0;o poj3468 A Simple Problem with Integers題意:O(-1)思路:O(-1)線段樹功能:update:成段增減 query:區間求和?View Code CPP1234567891011121314151617181920212223242526272829303132333435363738394041424

26、344454647484950515253545556575859606162636465666768697071727374#include <cstdio>#include <algorithm>using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1#define LL long longconst int maxn = 111111;LL addmaxn<<2;LL summaxn<<2;vo

27、id PushUp(int rt) sumrt = sumrt<<1 + sumrt<<1|1;void PushDown(int rt,int m) if (addrt) addrt<<1 += addrt;addrt<<1|1 += addrt;sumrt<<1 += addrt * (m - (m >> 1);sumrt<<1|1 += addrt * (m >> 1);addrt = 0;void build(int l,int r,int rt) addrt = 0;if (l = r)

28、scanf("%lld",&sumrt);return ;int m = (l + r) >> 1;build(lson);build(rson);PushUp(rt);void update(int L,int R,int c,int l,int r,int rt) if (L <= l && r <= R) addrt += c;sumrt += (LL)c * (r - l + 1);return ;PushDown(rt , r - l + 1);int m = (l + r) >> 1;if (L <

29、;= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson);PushUp(rt);LL query(int L,int R,int l,int r,int rt) if (L <= l && r <= R) return sumrt;PushDown(rt , r - l + 1);int m = (l + r) >> 1;LL ret = 0;if (L <= m) ret += query(L , R , lson);if (m < R) ret += que

30、ry(L , R , rson);return ret;int main() int N , Q;scanf("%d%d",&N,&Q);build(1 , N , 1);while (Q -) char op2;int a , b , c;scanf("%s",op);if (op0 = 'Q') scanf("%d%d",&a,&b);printf("%lldn",query(a , b , 1 , N , 1); else scanf("%d%d%d&

31、quot;,&a,&b,&c);update(a , b , c , 1 , N , 1);return 0;o poj2528 Mayors posters題意:在墻上貼海報,海報可以互相覆蓋,問最后可以看見幾張海報思路:這題數據范圍很大,直接搞超時+超內存,需要離散化:離散化簡單的來說就是只取我們需要的值來用,比如說區間1000,2000,1990,2012 我們用不到-,9991001,19891991,19992001,20112013,+這些值,所以我只需要1000,1990,2000,2012就夠了,將其分別映射到0,1,2,3,在于復雜度就大大的降下來了所

32、以離散化要保存所有需要用到的值,排序后,分別映射到1n,這樣復雜度就會小很多很多而這題的難點在于每個數字其實表示的是一個單位長度(并且一個點),這樣普通的離散化會造成許多錯誤(包括我以前的代碼,poj這題數據奇弱)給出下面兩個簡單的例子應該能體現普通離散化的缺陷:1-10 1-4 5-101-10 1-4 6-10為了解決這種缺陷,我們可以在排序后的數組上加些處理,比如說1,2,6,10如果相鄰數字間距大于1的話,在其中加上任意一個數字,比如加成1,2,3,6,7,10,然后再做線段樹就好了.線段樹功能:update:成段替換 query:簡單hash?View Code CPP12

33、3456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define lson l , m , rt << 1#define rson m +

34、 1 , r , rt << 1 | 1 const int maxn = 11111;bool hashmaxn;int limaxn , rimaxn;int Xmaxn*3;int colmaxn<<4;int cnt; void PushDown(int rt) if (colrt != -1) colrt<<1 = colrt<<1|1 = colrt;colrt = -1;void update(int L,int R,int c,int l,int r,int rt) if (L <= l &&am

35、p; r <= R) colrt = c;return ;PushDown(rt);int m = (l + r) >> 1;if (L <= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson);void query(int l,int r,int rt) if (colrt != -1) if (!hashcolrt) cnt +;hash colrt = true;return ;if (l = r) return ;int m = (l + r) >> 1;query(l

36、son);query(rson);int Bin(int key,int n,int X) int l = 0 , r = n - 1;while (l <= r) int m = (l + r) >> 1;if (Xm = key) return m;if (Xm < key) l = m + 1;else r = m - 1;return -1;int main() int T , n;scanf("%d",&T);while (T -) scanf("%d",&n);int nn = 0;for (int i

37、 = 0 ; i < n ; i +) scanf("%d%d",&lii , &rii);Xnn+ = lii;Xnn+ = rii;sort(X , X + nn);int m = 1;for (int i = 1 ; i < nn; i +) if (Xi != Xi-1) Xm + = Xi;for (int i = m - 1 ; i > 0 ; i -) if (Xi != Xi-1 + 1) Xm + = Xi-1 + 1;sort(X , X + m);memset(col , -1 , sizeof(col);for (i

38、nt i = 0 ; i < n ; i +) int l = Bin(lii , m , X);int r = Bin(rii , m , X);update(l , r , i , 0 , m , 1);cnt = 0;memset(hash , false , sizeof(hash);query(0 , m , 1);printf("%dn",cnt);return 0;o poj3225 Help with Intervals題意:區間操作,交,并,補等思路:我們一個一個操作來分析:(用0和1表示是否包含區間,-1表示該區間內既有包含又有不包含)U:把區間l

39、,r覆蓋成1I:把-,l)(r,覆蓋成0D:把區間l,r覆蓋成0C:把-,l)(r,覆蓋成0 , 且l,r區間0/1互換S:l,r區間0/1互換成段覆蓋的操作很簡單,比較特殊的就是區間0/1互換這個操作,我們可以稱之為異或操作很明顯我們可以知道這個性質:當一個區間被覆蓋后,不管之前有沒有異或標記都沒有意義了所以當一個節點得到覆蓋標記時把異或標記清空而當一個節點得到異或標記的時候,先判斷覆蓋標記,如果是0或1,直接改變一下覆蓋標記,不然的話改變異或標記開區間閉區間只要數字乘以2就可以處理(偶數表示端點,奇數表示兩端點間的區間)線段樹功能:update:成段替換,區間異或 query:簡單hash

40、?View Code CPP123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include <cstdio>#include <cstring>#include <cctype>#include <algorithm

41、>using namespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1 const int maxn = 131072;bool hashmaxn;int covermaxn<<2;int XORmaxn<<2;void FXOR(int rt) if (coverrt != -1) coverrt = 1;else XORrt = 1;void PushDown(int rt) if (coverrt != -1) coverrt

42、<<1 = coverrt<<1|1 = coverrt;XORrt<<1 = XORrt<<1|1 = 0;coverrt = -1;if (XORrt) FXOR(rt<<1);FXOR(rt<<1|1);XORrt = 0;void update(char op,int L,int R,int l,int r,int rt) if (L <= l && r <= R) if (op = 'U') coverrt = 1;XORrt = 0; else if (op = &#

43、39;D') coverrt = 0;XORrt = 0; else if (op = 'C' | op = 'S') FXOR(rt);return ;PushDown(rt);int m = (l + r) >> 1;if (L <= m) update(op , L , R , lson);else if (op = 'I' | op = 'C') XORrt<<1 = coverrt<<1 = 0;if (m < R) update(op , L , R , rson

44、);else if (op = 'I' | op = 'C') XORrt<<1|1 = coverrt<<1|1 = 0;void query(int l,int r,int rt) if (coverrt = 1) for (int it = l ; it <= r ; it +) hashit = true;return ; else if (coverrt = 0) return ;if (l = r) return ;PushDown(rt);int m = (l + r) >> 1;query(lson);q

45、uery(rson);int main() cover1 = XOR1 = 0;char op , l , r;int a , b;while ( scanf("%c %c%d,%d%cn",&op , &l , &a , &b , &r) ) a <<= 1 , b <<= 1;if (l = '(') a +;if (r = ')') b -;if (a > b) if (op = 'C' | op = 'I') cover1 = XOR

46、1 = 0; else update(op , a , b , 0 , maxn , 1);query(0 , maxn , 1);bool flag = false;int s = -1 , e;for (int i = 0 ; i <= maxn ; i +) if (hashi) if (s = -1) s = i;e = i; else if (s != -1) if (flag) printf(" ");flag = true;printf("%c%d,%d%c",s&1?'(':'' , s>

47、;>1 , (e+1)>>1 , e&1?')':'');s = -1;if (!flag) printf("empty set");puts("");return 0;· 練習:o poj1436 Horizontally Visible Segmentso poj2991 Craneo Another LCISo Bracket Sequence· 區間合并這類題目會詢問區間中滿足條件的連續最長區間,所以PushUp的時候需要對左右兒子的區間進行合并o poj3667 Ho

48、tel題意:1 a:詢問是不是有連續長度為a的空房間,有的話住進最左邊2 a b:將a,a+b-1的房間清空思路:記錄區間中最長的空房間線段樹操作:update:區間替換 query:詢問滿足條件的最左斷點?View Code CPP1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <cstdio>#include &

49、lt;cstring>#include <cctype>#include <algorithm>using namespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1 const int maxn = 55555;int lsummaxn<<2 , rsummaxn<<2 , msummaxn<<2;int covermaxn<<2; void PushDown(int rt,

50、int m) if (coverrt != -1) coverrt<<1 = coverrt<<1|1 = coverrt;msumrt<<1 = lsumrt<<1 = rsumrt<<1 = coverrt ? 0 : m - (m >> 1);msumrt<<1|1 = lsumrt<<1|1 = rsumrt<<1|1 = coverrt ? 0 : (m >> 1);coverrt = -1;void PushUp(int rt,int m) lsumrt = ls

51、umrt<<1;rsumrt = rsumrt<<1|1;if (lsumrt = m - (m >> 1) lsumrt += lsumrt<<1|1;if (rsumrt = (m >> 1) rsumrt += rsumrt<<1;msumrt = max(lsumrt<<1|1 + rsumrt<<1 , max(msumrt<<1 , msumrt<<1|1);void build(int l,int r,int rt) msumrt = lsumrt = rsum

52、rt = r - l + 1;coverrt = -1;if (l = r) return ;int m = (l + r) >> 1;build(lson);build(rson);void update(int L,int R,int c,int l,int r,int rt) if (L <= l && r <= R) msumrt = lsumrt = rsumrt = c ? 0 : r - l + 1;coverrt = c;return ;PushDown(rt , r - l + 1);int m = (l + r) >> 1

53、;if (L <= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson);PushUp(rt , r - l + 1);int query(int w,int l,int r,int rt) if (l = r) return l;PushDown(rt , r - l + 1);int m = (l + r) >> 1;if (msumrt<<1 >= w) return query(w , lson);else if (rsumrt<<1 + lsumrt<<1|1 >= w) return m - rsumrt<<1 + 1;return query(w , rson);int main() int n , m;scanf("%d%d",&n,&m);bui