关于一类特殊的离散化方式—— RN 离散化

watermouthhang · 2025-10-30 21:24:08 · 算法·理论

前言

在做线段树时，我们有时因为空间限制，要离散化。

但是离散化时，要考虑端点在哪，端点之间的部分归谁管，繁杂且易错。

于是，RN 离散化应运而生。

前置知识

普通离散化（STL实现），即使用元素在序列中的排名（严格的）做为下标。

先回顾普通离散化写法。

1. 排序
2. 去重
3. 压入哈希表（可选）
4. （预处理结束后真正使用时）从哈希表中读取（使用步骤 3）或二分查找（未使用步骤 3）值所对应下标。

我们采用使用步骤 3 的实现。

基础思路

那么，RN 离散化如何解决前言所提的困难呢？

我们让所有出现的点和其之间的区间共用同一个下标体系。

具体地，如：

1 3 2 7 432 25252 3552525 43 565

这组数据，普通离散化会把哈希表搞成：

而 RN 离散化会将端点存入哈希表中：

将端点之间区间存入正常数组中：

实现与使用

整体思路还是沿着普通离散化的思路走。

预处理阶段

Step I 排序

与正常写法一样。

Step II 去重

与正常写法一样。

Step III 存表

我们再额外记录一个计数器，每一个端点让计数器正常加一，作为哈希表的值。当此端点与下一个端点之间有空隙时，计数器额外加一，并将中间空隙加入数组中。

预处理阶段的一个参考模版：

map<ll,int> toi;//用作哈希表存端点
bool is_on[maxn];//用作数组存空隙
pair<ll,ll> rg[maxn];//存此下标是否为端点
ll dd[maxn];//存端点对应值（toi的逆数组）
int N;//最终离散化长度
void lsh()
{
    sort(b+1,b+n1);//I:排序
    int rr=unique(b+1,b+n+1)-(b+1);//II:去重
    //III;存表
    b[rr+1]=b[rr]+1;//控制序列最后一个值不额外加空隙
    int cnt=0;//计数器
    for(int i=1;i<=rr;++i)
    {
        ++cnt;
        toi[b[i]]=cnt;
        is_on[cnt]=1;
        dd[cnt]=b[i];
        if(b[i+1]-b[i]>1)//有空隙
        {
            rg[++cnt]=make_pair(b[i]+1,b[i+1]-1);
        }
    }
    N=cnt;
}

使用阶段

到这个位置，我们不得不拿出具体习题来说明了。

例：P13825 【模板】线段树 1.5。

题目大意：区间加，区间查和，询问次数 10^5，序列长度 10^9，初始时序列值等于其下标。

解：离线处理，存下所有更改与查询的端点，然后 RN 离散化即可。

那么——

Step IV 读取、使用

如何在已经离散化的前提下写线段树呢？我们发现只需要将正常线段树的部分更改两处即可：

1. 建树：分类讨论，判断是端点还是空隙。
2. 调用函数：多加一个读哈希表的操作。

代码：

#include <cstdio>

using namespace std;
typedef unsigned long long ll;
const int maxn=4e5+10;
struct Ques
{
    int op;
    ll l,r,k;
}ques[maxn];
ll n;
int m;
ll b[maxn];
map<ll,int> toi;
bool is_on[maxn];
pair<ll,ll> rg[maxn];
ll dd[maxn];
int N;
void lsh()//RN离散化
{
    sort(b+1,b+2*m+1);
    int rr=unique(b+1,b+2*m+1)-(b+1);
    b[rr+1]=b[rr]+1;
    int cnt=0;
    for(int i=1;i<=rr;++i)
    {
        ++cnt;
        toi[b[i]]=cnt;
        is_on[cnt]=1;
        dd[cnt]=b[i];
        if(b[i+1]-b[i]>1)
        {
            rg[++cnt]=make_pair(b[i]+1,b[i+1]-1);
        }
    }
    N=cnt;
}
struct node
{
    ll dt,ad,len;
}tree[maxn*4];
void push_up(int c)
{
    tree[c].dt=tree[c*2].dt+tree[c*2+1].dt;
}
void push_down(int c)
{
    tree[c*2].ad+=tree[c].ad;
    tree[c*2+1].ad+=tree[c].ad;
    tree[c*2].dt+=tree[c].ad*tree[c*2].len;
    tree[c*2+1].dt+=tree[c].ad*tree[c*2+1].len;
    tree[c].ad=0; 
}
void build(int l,int r,int c)
{
    if(l==r)
    {
        if(is_on[l])
        {
            tree[c].dt=dd[l];
            tree[c].ad=0;
            tree[c].len=1;
        }
        else
        {
            tree[c].dt=(rg[l].first+rg[l].second)*(rg[l].second-rg[l].first+1)/2;//等差数列求和，显然
            tree[c].ad=0;
            tree[c].len=rg[l].second-rg[l].first+1;
        }
        return ;
    }
    int mid=l+(r-l)/2;
    build(l,mid,c*2);
    build(mid+1,r,c*2+1);
    tree[c].len=tree[c*2].len+tree[c*2+1].len;
    push_up(c);
}
void update(int l,int r,int tl,int tr,int c,ll x)
{
    if(l>tr||r<tl)
    {
        return ;
    }
    if(tl<=l&&r<=tr)
    {
        tree[c].dt+=tree[c].len*x;
        tree[c].ad+=x;
        return ;
    }
    int mid=l+(r-l)/2;
    push_down(c);
    update(l,mid,tl,tr,c*2,x);
    update(mid+1,r,tl,tr,c*2+1,x);
    push_up(c);
}
ll getans(int l,int r,int tl,int tr,int c)
{
    if(l>tr||r<tl)
    {
        return 0;
    }
    if(tl<=l&&r<=tr)
    {
        return tree[c].dt;
    }
    int mid=l+(r-l)/2;
    push_down(c);
    return getans(l,mid,tl,tr,c*2)+getans(mid+1,r,tl,tr,c*2+1);
}
int main()
{
    scanf("%llu%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&ques[i].op);
        if(ques[i].op==1)
        {
            scanf("%llu%llu%llu",&ques[i].l,&ques[i].r,&ques[i].k);
        }
        else
        {
            scanf("%llu%llu",&ques[i].l,&ques[i].r);
        }
        b[i*2-1]=ques[i].l;
        b[i*2]=ques[i].r;
    }
    lsh();//离散化函数
    build(1,N,1);
    for(int i=1;i<=m;++i)
    {
        if(ques[i].op==1)
        {
            update(1,N,toi[ques[i].l],toi[ques[i].r],1,ques[i].k);//调用前先用哈希表找对应值
        }
        else
        {
            printf("%llu\n",getans(1,N,toi[ques[i].l],toi[ques[i].r],1));//同上
        }
    }
    return 0;
}

时间复杂度与正确性证明

真的用证吗？显然，得证。

正确性

命题 1

端点、空隙一定在同一下标体系，即两者占用下标集合不重不漏。

证明：使用计数器，每次加一后立即存表，每次给一个新的空隙或端点存表时都先令计数器加一，故一定不重不漏。

命题 2

对于离散化后节点和未离散化时此节点对应节点区间进行的操作等效。

证明：显然，RN 离散化与普通离散化内核相同，而普通离散化可行，故 RN 离散化也可行。

正确性得证！

由命题 1,2，算法正确性得到保障。

时间复杂度

• 预处理（RN 离散化）：
  • 排序（\operatorname{O}(n\log{n})）；
  • 去重（\operatorname{O}(n)）；
  • 找、存对应下标（\operatorname{O}(m\log{n})）。
• 数据结构：线段树 \operatorname{O}(m\log{n})。
• 总时间复杂度 \operatorname{O}((n+m)\log{n})。

综上，证毕。

用处分析

先说本写法优点：好想，好分类讨论，不用在写数据结构时处处分讨（这也是它最好之处，也是我使用这种方式的原因），极其适合离散化新手使用。

那么缺点是什么呢？空间需要开两倍，在建树时稍慢（不过一般就建一边树，影响不大）。

后记

学到扫描线时知道自己终于要直面去年 S 组的过去了（T2 离散化写挂爆零，以至于对 CSP-S2024-T2 和离散化有了 PTSD），故写一篇对过往的释然，对明天的向往。

祝 RP++。

完。