线段树离散化 unique + 二分查找模板（转载）

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；

离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。例如，在建造线段树空间不够的情况下，可以考虑离散化。

数据的离散化

有些数据本身很大，自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性，那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。
例 1：
91054 与 52143的逆序对个数相同。
例 2：
设有4个数： 1234567、123456789、12345678、123456
排序：123456<1234567<12345678<123456789
=>1<2<3<4
那么这4个数可以表示成：2、4、3、1
例 3：
比如给你n个数：98998988,32434234,433234556,32434234,8384733,……
让你统计其中每个数出现的次数，传统的做法有好几种，比如一遍一遍的扫过去，比对叠加，这样算法的效率是O(n2)，效率低下；
再比如先排序，再统计连续的相同的个数，这里的效率已经有所提高了，不过假如上面的数据是一道线段树的题目给出的数据，那么建树需要的空间开销实在是太大了。
再改进一下，采用哈希的方法，开一个大于其中最大数的数组并初始化为零，O(n)扫一下，在该数字对应的下标的元素上+1，如果对于比较小的数字还好说，但是对于上面出现的数字直接采用哈希对空间的开销是十分大的也是没有必要的，所以这里用到了数据的离散化。
首先将数字排序：32434234，32434234，43324556，8384733，98998988
去重后给予其对应的索引： 0,0,1,2,3 （一一映射）
分别对应每个数，就可以简化很多操作，减少了很多不必要的资源开销。
除了对于较大整数需要使用离散化之外，对于一些需要使用整型数据结构，但给出的数据却是小数的也可以使用离散化，将其索引为整数就可以了。

那么可以总结出离散化的步骤：

1、排序

2、去重

3、索引
为了简化代码，我们采用STL算法离散化：

/*

用离散化之前先用 sort（）排序，再用 unique() 进行去重

用 lower_bound() 或者 upper_bound() 进行二分查找位置

*/

int a[n], b[n], sub[n];

// a[n]是即将被离散化的数组，b[n]是a[n]的副本，sub用于排序去重后提供离散化后的值

sort(sub, sub + n);

int size = unique(sub, sub + n) - sub;

for(int i = 0; i < n; i++)

    a[i] = lower_bound(sub, sub + size, a[i]) - sub;

 //即a[i]为b[i]离散化后对应的值

1、unique()函数————返回值是去重之后的长度

unique() 的作用是“去掉”容器中相邻元素的重复元素（不一定要求数组有序），即去重
它会把重复的元素添加到容器末尾（所以数组大小并没有改变），而返回值是去重之后的尾地址
如果要删去重复元素，可以把尾巴删去即可（或者直接定义新的长度！）
例如：

sz=unique(b+1,b+n+1)-(b+1);//减去的（b+1) 及 a  是起始地址

sz=unique(a,a+n)-a;

2、二分查找——lower_bound()、upper_bonud()

/*

upper_bound（i） 返回的是键值为i的元素可以插入的最后一个位置（上界）

lowe_bound（i） 返回的是键值为i的元素可以插入的位置的第一个位置（下界）。

*/

怎么理解呢，举例：
在升序的set里面
set里没有元素i的时候，两个元素的返回值是一样的。
1 2 4 5 这个序列，upp（3）和low（3）都返回位置2（下标）

如果只有一个元素i，low返回那个元素的位置，而upp返回那个元素的位置的后一个位置。
1 2 4 5 这个序列upp（2）返回下标2而low（2）返回下标1

多个元素i，low返回那个元素的位置，upp返回那多个元素中的最后一个的后一个位置。
1 2 2 4 5 这个序列 upp（2）返回下标3的位置，low（2）返回下标1的位置。

！！！！！！！！！！！！！
特别注意：举例在一个升序的容器里，如果所有元素都大于i则，upp和low都返回begin。都小于i则返回end（越界了）。

最后再来一句，看是否好理解一些。

terator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值<=key的最后一个元素的后一个元素。
★降序排列的容器：
iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值<= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值>=key的最后一个元素的后一个元素。
例如：

bool cmp(int a,int b)

{

    return a<b;

}

int main()

{

    int a[10]={2,7,1,4,4,6};

    sort(a,a+6,cmp);        // 去重之前先排序

    int m=unique(a,a+6)-a; // 去重

    cout<<m<<endl;        // 输出去重之后的长度

    for(int i=0;i<m;i++)

        cout<<a[i]<<' '; // 输出去重之后的数

    cout<<endl;

    int tem=upper_bound(a,a+6,4)-a;

    //按从小到大 4 最多能插入数组 a 的哪个位置

    int p=lower_bound(a,a+6,4)-a;

    //按从小到大，4最少能插入数组 a  的哪个位置

    cout<<tem<<endl;

    cout<<p<<endl;

}

输出

5

1 2 4 6 7

3

2

--------------------- 本文来自 __zcy 的CSDN 博客，全文地址请点击：https://blog.csdn.net/zcy19990813/article/details/81141035?utm_source=copy

巴特西

线段树离散化 unique + 二分查找模板（转载）

最新文章

热门文章

巴特西

线段树离散化 unique + 二分查找 模板 （转载）

最新文章

热门文章

线段树离散化 unique + 二分查找模板（转载）