数据结构专题——线段树

线段树

转载请注明出处，谢谢！http://blog.csdn.net/metalseed/article/details/8039326 by MetalSeed

持续更新中

1：概述

线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!

性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍

2：基本操作（demo用的是查询区间最小值）

线段树的主要操作有：

(1)：线段树的构造 void build(int node, int begin, int end);

主要思想是递归构造，如果当前节点记录的区间只有一个值，则直接赋值，否则递归构造左右子树，最后回溯的时候给当前节点赋值

(2)：区间查询int query(int node, int begin, int end, int left, int right);
（其中node为当前查询节点，begin,end为当前节点存储的区间，left,right为此次query所要查询的区间）
主要思想是把所要查询的区间[a,b]划分为线段树上的节点，然后将这些节点代表的区间合并起来得到所需信息
比如前面一个图中所示的树，如果询问区间是[0,2]，或者询问的区间是[3,3]，不难直接找到对应的节点回答这一问题。但并不是所有的提问都这么容易回答，比如[0,3]，就没有哪一个节点记录了这个区间的最小值。当然，解决方法也不难找到：把[0,2]和[3,3]两个区间（它们在整数意义上是相连的两个区间）的最小值“合并”起来，也就是求这两个最小值的最小值，就能求出[0,3]范围的最小值。同理，对于其他询问的区间，也都可以找到若干个相连的区间，合并后可以得到询问的区间。
#include <cstdio>#include <algorithm>using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 222222;int h , w , n;int MAX[maxn<<2];void PushUP(int rt) {MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);}void build(int l,int r,int rt) {MAX[rt] = 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) {MAX[rt] -= x;return l;}int m = (l + r) >> 1;int ret = (MAX[rt<<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 (MAX[1] < x) puts("-1");else printf("%d\n",query(x , 1 , h , 1));}}return 0;}

成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候hdu1698 Just a Hook
题意:O(-1)
思路:O(-1)
线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息)
#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 add[maxn<<2];LL sum[maxn<<2];void PushUp(int rt) {sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void PushDown(int rt,int m) {if (add[rt]) {add[rt<<1] += add[rt];add[rt<<1|1] += add[rt];sum[rt<<1] += add[rt] * (m - (m >> 1));sum[rt<<1|1] += add[rt] * (m >> 1);add[rt] = 0;}}void build(int l,int r,int rt) {add[rt] = 0;if (l == r) {scanf("%lld",&sum[rt]);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) {add[rt] += c;sum[rt] += (LL)c * (r - l + 1);return ;}PushDown(rt , r - l + 1);int m = (l + r) >> 1;if (L <= 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 sum[rt];}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 += query(L , R , rson);return ret;}int main() {int N , Q;scanf("%d%d",&N,&Q);build(1 , N , 1);while (Q --) {char op[2];int a , b , c;scanf("%s",op);if (op[0] == 'Q') {scanf("%d%d",&a,&b);printf("%lld\n",query(a , b , 1 , N , 1));} else {scanf("%d%d%d",&a,&b,&c);update(a , b , c , 1 , N , 1);}}return 0;}

poj2528 Mayor’s posters
题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了[1,4][1,2][3,4]
线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
线段树功能:update:成段替换 query:简单hash
#include <cstdio>#include <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 = 22222;struct Seg{int l , r , h , s;Seg() {}Seg(int a,int b,int c,int d):l(a) , r(b) , h(c) , s(d) {}bool operator < (const Seg &cmp) const {if (h == cmp.h) return s > cmp.s;return h < cmp.h;}}ss[maxn];bool lbd[maxn<<2] , rbd[maxn<<2];int numseg[maxn<<2];int cnt[maxn<<2];int len[maxn<<2];void PushUP(int rt,int l,int r) {if (cnt[rt]) {lbd[rt] = rbd[rt] = 1;len[rt] = r - l + 1;numseg[rt] = 2;} else if (l == r) {len[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;} else {lbd[rt] = lbd[rt<<1];rbd[rt] = rbd[rt<<1|1];len[rt] = len[rt<<1] + len[rt<<1|1];numseg[rt] = numseg[rt<<1] + numseg[rt<<1|1];if (lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;//两条线重合}}void update(int L,int R,int c,int l,int r,int rt) {if (L <= l && r <= R) {cnt[rt] += c;PushUP(rt , l , r);return ;}int m = (l + r) >> 1;if (L <= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson);PushUP(rt , l , r);}int main() {int n;while (~scanf("%d",&n)) {int m = 0;int lbd = 10000, rbd = -10000;for (int i = 0 ; i < n ; i ++) {int a , b , c , d;scanf("%d%d%d%d",&a,&b,&c,&d);lbd = min(lbd , a);rbd = max(rbd , c);ss[m++] = Seg(a , c , b , 1);ss[m++] = Seg(a , c , d , -1);}sort(ss , ss + m);int ret = 0 , last = 0;for (int i = 0 ; i < m ; i ++) {if (ss[i].l < ss[i].r) update(ss[i].l , ss[i].r - 1 , ss[i].s , lbd , rbd - 1 , 1);ret += numseg[1] * (ss[i+1].h - ss[i].h);ret += abs(len[1] - last);last = len[1];}printf("%d\n",ret);}return 0;}

练习
hdu3265 Posters
hdu3642 Get The Treasury
poj2482 Stars in Your Window
poj2464 Brownie Points II
hdu3255 Farming 
ural1707 Hypnotoad’s Secret
uva11983 Weird Advertisement

占坑,有空来写N颗更新到底的线段树 2012/7/10
线段树与其他结合练习(欢迎大家补充):
hdu3954 Level up
hdu4027 Can you answer these queries?
hdu3333 Turing Tree
hdu3874 Necklace
hdu3016 Man Down
hdu3340 Rain in ACStar
zju3511 Cake Robbery
UESTC1558 Charitable Exchange
CF85-D Sum of Medians
spojGSS2 Can you answer these queries II