线段树——区间离散化/压缩

一、基本概念

线段树：线段树基本概念

离散化：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

原数据：{100,200}，{20,50000}，{1,400}；

处理后：{3,4}，{2,6}，{1,5}；

二、算法

思想：

• 记录每个点的左端和右端，全部保存到一个数组a中并排序
• 节点去重
• 如果两个节点间距离大于1，添加一个中间节点
• 再次对a排序
• 在a中二分搜索原来每个点的左右端，将索引值保存在线段树中

C++版本一

        scanf("%d",&n);
        int cnt = 0,len = 1;
        for(i=1;i<=n;i++)//记录头尾
        {
            sf("%d %d",&s1[i],&s2[i]);
            a[++cnt] = s1[i];
            a[++cnt] = s2[i];
        }
        sort(a+1,a+1+cnt);

        for(i=2;i<=cnt;i++)//去重
        {
            if(a[i]!=a[i-1]) a[++len] = a[i];
        }

        for(i=len;i>1;i--)//添加中间值
        {
            if(a[i]-a[i-1]>1) a[++len] = a[i]-1;
        }
        sort(a+1,a+1+len);

        for(i=1;i<=n;i++)
        {
            int l = BSearch(1,len,s1[i]);
            int r = BSearch(1,len,s2[i]);
            update(i,l,r,1,len,1);
        }

三、例题

http://poj.org/problem?id=2528（题解：https://blog.csdn.net/weixin_43272781/article/details/83420707）

http://acm.hdu.edu.cn/showproblem.php?pid=1199（题解：https://blog.csdn.net/weixin_43272781/article/details/83653497）

四、参考文章

https://www.cnblogs.com/qlky/articles/5716796.html