读书笔记摘抄新闻资讯
线段树
线段树是一种二叉搜寻树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间複杂度为O(logN)。而未最佳化的空间複杂度为2N，实际套用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
基本介绍
- 中文名：线段树
- 外文名：Segment Tree
- 功能：单点、区间的修改、查询
- 时间複杂度：log（n）（建树为O(n)）
- 学科：数据结构
- 领域：数据结构
定义
线段树是一种二叉搜寻树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间複杂度为O(logN）。而未最佳化的空间複杂度为2N，因此有时需要离散化让空间压缩。
基本结构
线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b]。长度为1的线段称为元线段。非元线段都有两个子结点，左结点代表的线段为[a,(a + b) / 2]，右结点代表的线段为[((a + b) / 2）+1,b]。
下图就是两棵长度範围为[1,5][1,10]的线段树。
长度範围为[1,L] 的一棵线段树的深度为log (L) + 1。这个显然，而且存储一棵线段树的空间複杂度为O(L）。
线段树支持最基本的操作为插入和删除一条线段。下面以插入为例，详细叙述，删除类似。
将一条线段[a,b] 插入到代表线段[l,r]的结点p中，如果p不是元线段，那幺令mid=（l+r）/2。如果b<mid，那幺将线段[a,b] 也插入到p的左儿子结点中，如果a>mid，那幺将线段[a,b] 也插入到p的右儿子结点中。
插入（删除）操作的时间複杂度为O（logn）。
实际套用
上面的都是些基本的线段树结构，但只有这些并不能做什幺，就好比一个程式有输入没输出，根本没有任何用处。
最简单的套用就是记录线段是否被覆盖，随时查询当前被覆盖线段的总长度。那幺此时可以在结点结构中加入一个变数int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。
另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。
实际上，通过在结点上记录不同的数据，线段树还可以完成很多不同的任务。例如，如果每次插入操作是在一条线段上每个位置均加k，而查询操作是计算一条线段上的总和，那幺在结点上需要记录的值为sum。
这里会遇到一个问题：为了使所有sum值都保持正确，每一次插入操作可能要更新O(N）个sum值，从而使时间複杂度退化为O(N）。
解决方案是Lazy思想：对整个结点进行的操作，先在结点上做标记，而并非真正执行，直到根据查询操作的需要分成两部分。
根据Lazy思想，我们可以在不代表原线段的结点上增加一个值toadd，即为对这个结点，留待以后执行的插入操作k值的总和。对整个结点插入时，只更新sum和toadd值而不向下进行，这样时间複杂度可证明为O(logN）。
对一个toadd值为0的结点整个进行查询时，直接返回存储在其中的sum值；而若对toadd不为0的一部分进行查询，则要更新其左右子结点的sum值，然后把toadd值传递下去，再对这个查询本身，左右子结点分别递归下去。时间複杂度也是O(nlogN）。
基本代码
C++
支持以下操作
1 x 若x不存在,插入x
2 x 若x存在,删除x
3 输出当前最小值,若不存在输出-1
4 输出当前最大值,若不存在输出-1
5 x 输出x的前驱,若不存在输出-1
6 x 输出x的后继,若不存在输出-1
7 x 若x存在,输出1,否则输出-1
//by hzwer#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<map>#include<set>#include<vector>#include<queue>#define inf 1000000000using namespace std;int n,m;struct seg{int l,r,v;}t[3000005];void build(int k,int l,int r) //建树 k：当前节点下标 线段左为l，线段右为r{ t[k].l=l;t[k].r=r; //线段左端，线段右端 if(l==r)return; //线段长度为零，结束 int mid=(l+r)>>1; //取线段中点 build(k<<1,l,mid); //k<<1:下标为k节点的左儿子下标，线段左为l，线段右为mid k<<1==k*2 build(k<<1|1,mid+1,r); //k<<1|1:下标为k节点的右儿子下标，线段左为mid+1，线段右为r k<<1|1==k*2+1}int mn(int k){ if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; if(t[k<<1].v)return mn(k<<1); else return mn(k<<1|1);}int mx(int k){ if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; if(t[k<<1|1].v)return mx(k<<1|1); else return mx(k<<1);}void insert(int k,int val){ int l=t[k].l,r=t[k].r; if(l==r){t[k].v=1;return;} int mid=(l+r)>>1; if(val<=mid)insert(k<<1,val); else insert(k<<1|1,val); t[k].v=t[k<<1].v+t[k<<1|1].v;}int find(int k,int val){ int l=t[k].l,r=t[k].r; if(l==r) { if(t[k].v)return 1; return -1; } int mid=(l+r)>>1; if(val<=mid)return find(k<<1,val); else return find(k<<1|1,val);}void del(int k,int val){ int l=t[k].l,r=t[k].r; if(l==r){t[k].v=0;return;} int mid=(l+r)>>1; if(val<=mid)del(k<<1,val); else del(k<<1|1,val); t[k].v=t[k<<1].v+t[k<<1|1].v;}int findpr(int k,int val){ if(val<0)return -1; if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; int mid=(l+r)>>1; if(val<=mid)return findpr(k<<1,val); else { int t=findpr(k<<1|1,val); if(t==-1)return mx(k<<1); else return t; }}int findsu(int k,int val){ if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; int mid=(l+r)>>1; if(val>mid)return findsu(k<<1|1,val); else { int t=findsu(k<<1,val); if(t==-1)return mn(k<<1|1); else return t; }}int main(){ scanf("%d %d",&n,&m); build(1,0,n); int opt,x; for(int i=1;i<=m;i++) { scanf("%d",&opt); switch(opt) { case 1:scanf("%d",&x);if(find(1,x)==-1)insert(1,x);break; case 2:scanf("%d",&x);if(find(1,x)==1)del(1,x);break; case 3:printf("%d\n",mn(1));break; case 4:printf("%d\n",mx(1));break; case 5:scanf("%d",&x);printf("%d\n",findpr(1,x-1));break; case 6:scanf("%d",&x);printf("%d\n",findsu(1,x+1));break; case 7:scanf("%d",&x);printf("%d\n",find(1,x));break; } } return 0;}Pascal
基本操作
program intervaltree;const maxn = 10000; inf = 'input.txt'; ouf = 'output.txt';type treenode = record a, b, Left, Right, cover: longint; end;var tree: array[1..maxn] of treenode; number, tot, c, d: longint;procedure maketree(a, b: longint);var now: longint;begin Inc(tot); now := tot; tree[now].a := a; tree[now].b := b; tree[now].cover := 0; if a + 1 < b then begin tree[now].Left := tot + 1; maketree(a, (a + b) div 2); tree[now].Right := tot + 1; maketree((a + b) div 2, b); end;end;procedure insert(num: longint);begin if (c <= tree[num].a) and (tree[num].b <= d) then tree[num].cover := tree[num].cover + 1 else begin if c < (tree[num].a + tree[num].b) div 2 then insert(tree[num].Left); if d > (tree[num].a + tree[num].b) div 2 then insert(tree[num].Right); end;end;procedure Delete(num: longint);begin if (c <= tree[num].a) and (tree[num].b <= d) then Dec(tree[num].cover) else begin if c < (tree[num].a + tree[num].b) div 2 then Delete(tree[num].Left); if d > (tree[num].a + tree[num].b) div 2 then Delete(tree[num].Right); end;end;procedure Count(num: longint);begin if tree[num].cover > 0 then number := number + (tree[num].b - tree[num].a) else begin if tree[num].Left > 0 then Count(tree[num].Left); if tree[num].Right > 0 then Count(tree[num].Right); end;end;begin Assign(input, inf); Reset(input); Assign(output, ouf); Rewrite(output); Readln(c, d); maketree(c, d); while not EOF do begin Readln(c, d); insert(1); end; Count(1); Writeln(number); Close(output); Close(input);end.