线段树的解决实际问题
发布网友
发布时间：2022-04-24 20:53
共1个回答
热心网友
时间：2023-10-10 20:04
支持以下操作
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){ t[k].l=l;t[k].r=r; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);}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;} 相信对算法设计或者数据结构有一定了解的人对线段树都不会太陌生。它是能够在log(MaxLen）时间内完成线段的添加、删除、查询等操作。但一般的实现都有点复杂而线段树应用中有一种是专门针对点的。（点树？）它的实现却非常简单。
这种数据结构有什么用？我们先来考虑一下下面的需求（全部要求在LogN时间内完成）：如何知道一个点在一个点集里的大小“排名”？很简单，开一个点数组，排个序，再二分查找就行了；如何在一个点集内动态增删点？也很简单，弄个平衡树就行了（本来平衡树比线段树复杂得多，但自从世界上有了STL set这么个好东东，就……^_^）那如果我既要动态增删点，也要随时查询到一个点的排名呢？那对不起，可能就要出动到我们的“点树”了。
其实现原理很简单：每当增加（或删除）一个大小为X的点时，就在树上添加（或删除）一条（X,MaxLen）的线段（不含端点），当要查询一个点的排名时，只要看看其上有多少条线段就可以了。针对这一需求，这里有个非常简单的实现（见以下代码，十多行，够短了吧？）其中clear（）用于清空点集；add（）用于添加一个点；cntLs（）返回小于n的点的个数，也就是n的升序排名，类似地cntGt是降序排名。
这个点树有什么用呢？其中一个应用是在O(NlogN）时间内求出一个排列的逆序数，方法是每读到一个数x，就让逆序数+=cntGt(x）；然后再add(x）。
这个实现还可以进行一些扩展。比如删除del(int n），只要把add(int n）中的++size换成--size，把a[i/2]++改成a[i/2]--即可。另外还可以通过二分查找功能在O(logN）时间内查到排名第n的点的大小。应该也可以三四行内搞定。
补充：杨弋同学在2008年信息学奥赛冬令营上新发明了一种线段树的省空间堆式存储法，具体方法可以见08年冬令营课件.
实现代码及测试程序
#include <cstring>#include <iostream>using namespace std;// 实现代码template <int N> //表示可用区间为[0,N)，其中N必须是2的幂数class PointTree{public: PointTree() { clear(); size = 0; } ~PointTree() {}; void clear() { memset(this, 0, sizeof(*this)); } void add(int n) { int i = N + n; ++size; for (++a[i]; i > 1; i /= 2) if (~i & 1) a[i / 2]++; } int cntLs(int n) { //统计小于 int c = 0; //若统计小于等于则c=a; for (int i = N + n; i>1; i /= 2) if (i & 1) c += a[i / 2]; return c; } int cntGt(int n) { return size - a[N + n] - cntLs(n); } void del(int n) { if (!a[n += N]) return; --size; for (--a[n]; n > 1; n /= 2) if (~n & 1) --a[n / 2]; } /* 解决：求点集中第i小的数（由0数起） * 注意：如果i>=size返回N-1 */ int operator[](int n) //下标从0开始 { int i = 1; while (i < N) { if (n < a[i]) i *= 2; else n -= a[i], i = i * 2 + 1; } return i - N; }private: int a[2 * N]; int size;};PointTree<8192> t;// 测试程序int main(int argc, char const *argv[]){ char c; int n; while(cin >> c) { if(c == 'c') t.clear(); else { cin >> n; if(c == 'a') t.add(n); if(c == 'd') t.del(n); if(c == 'q') cout << t[n] << endl; } } return 0;} 另一种功能上比较类似的数据结构：“树状数组”。它们有不少相似之处：
针对点集的处理（添加、删除、查找）；
相似的时空复杂度（logN时间，2N空间）；
相似的编程复杂度（都比线段树简短得多）；
因此，所有可以用树状数组解决的问题都可以用这个“点树”来解决，另外它还有以下好处：
更直观的转移；
同时支持自下而上和自上而下两种方向的查找和更新，而后者树状数组不支持，所以树状数组不提供某些功能，比如说O(logN）求点集中第k小数。 ZKW线段树由清华大学张昆玮发现，是一种新的用非递归方式实现的线段树，具体请参考张昆玮先生本人的讲稿《统计的力量》 。
