一、基本概念

线段树:线段树基本概念

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

例如:

原数据: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