区间和 离散化入门与例题· C++

关于离散化，OIWIKI上是这么解释的:

        通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

用再通俗的话来讲，就是用下标替代原数值，解决一些特定问题；

什么样的特定问题呢？

影响结果的只有原数值的相对大小且原数值分布的比较稀疏（或者说差距比较大）

即 相对大小+差距大

比如给出3个坐标，1，100000，1000000000，其中每个坐标上分别对应一个权值a,b,c，其余没提到的坐标上对应的权值均是0；

那么如果我要求坐标区间内[l,r]的和，那么很显然，这是一个很明显的前缀和问题。

容易想到，我们创建一个数组，预处理后作一个前缀和数组，就可以解决问题了；

可是问题在于，当坐标过大的时候，数组没办法开那么大，即开头提到的：

自身无法作为数组的下标。

那么，于是，就有了离散化。

离散化本质上是一种hash

原因在于，我们可以把数值映射成坐标

即用坐标替代数值，数值的相对大小表现为坐标的相对大小；

离散化 *** 作通常需要先排序，然后去重，然后得到正确的映射。

所以，讲到这里，可以把离散化理解为一种映射（只不过需通过一些 *** 作才能获得正确映射）。

以Acwing 802区间和为例，以经典例题的角度展开叙述：

802. 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。​​​​​​​

现在，我们首先进行 n 次 *** 作，每次 *** 作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109
1≤n,m≤105
−109≤l≤r≤109
−10000≤c≤10000

问题分析：

很显然，下标的大小达到了10的9次方，显然无法直接开等大的数组，但是我们可以离散化！

还是前面那句话！离散化就是把数值映射成下标。

        那么可以看到，有n行输入，输入了n个坐标，和与其坐标对应的权值（应该累加的值）；

那么考虑最坏的情况，如果这n个坐标互异，那么我们也仅仅需要开1e5大小的数组；

可以发现空间大幅度减小！

        接下来的m行输入，每一行输入一对(l,r），也就是一对坐标x1,x2。由于我们最终要求[x1,x2]内的元素和，所以我们关心x1和x2上的权值，因而有必要在离散化的时候把x1,x2也进行一个映射。同样的，若这2m个坐标互异，2m<=2*1e5, 那么我们再开2*1e5大小的空间，也足以应付！（使得每个坐标都是一个唯一确定的下标与之对应）

---

因而，我们开一个坐标数组alls,对于每一个坐标，存入alls[i]；

等价于alls[i]这个坐标映射成了下标i！

那么该如何实现这个 *** 作?

很简单，我们先读入所有的坐标,push_back到alls数里面，然后sort一遍

就可以实现 若i坐标的相对大小；

然后我们需要去重，这一步可能比较突然，后面会解释。（其实当前可以这么理解，既然是映射，我们设坐标为x，x通过映射法则映射成f(x)，那么根据数学知识，我们直到一个x仅且对应一个f(x)，而一个f(x)是可以对应多个x）

所以目前，我们就形成了一个映射体系，即坐标和下标的一 一对应关系，用数组alls体现.

当坐标离散化后，由于我们想求的是元素和，那么需要关注权值；

权值仅出现在输入的时候，而我们希望把权值放到对应的坐标上，

换句话说，我们更希望，把权值放到对应的坐标所对应的离散化下标上。

但是，我们无法做到一边读入一边离散化，而我们上述的希望是基于离散化工作完成的基础上，那么，我们需要一个容器，暂时存下输入，vector> add，即 *** 作向量

同样的，我们再准备一个 *** 作向量,vector>query，暂时地把“询问”存起来。

当读入完毕后，我们就需要把权值放上去，因而离不开一个原数组（这里有暗示了，和前缀和相对应），我们创建它。

遍历add,每个元素的第一个位置存的是坐标，第二个元素存的是当前应该累加的值c；

那么该如何把坐标转化成对应的下标？由于alls这个坐标数组是排好序的且是一 一对应(这时候你就知道为什么要去重了)，我们可以二分查找，找到坐标对应的下标i,执行a[i]++c；

那么，遍历完后，a[i]代表某个坐标上的权值（某个坐标：下标i相对应的坐标）；

所以我们到这里就实现了，把权值放到对应的坐标所对应的离散化下标上。

那么接下来，原数组创建好了，下一步就是求终极任务：元素和

在原数组的基础上，我们开一个前缀和数组s（下标从1开始，避免特判)

那么s[i]=a[1]+a[2]+..a[i]（1<2<...i，所对应的下标x1

s[i]可以表述为数轴上x1+x2+..xi的和

因而给定一组(i,j)，我们列：s[i]-s[j-1] = a[j]+a[j+1]...a[i](每个元素都非0)（xj

表述为数轴上[xj，xi]的元素和，（非0的元素和+0的元素和）

这时候利用我们之前开的query数组,读入l,r；

由于l,r是真实的坐标，我们需要将其映射到下标，还是用到二分!

把[l,r]转化为[j,i]，所以求xj+...xi = aj+...ai = s[i] - s[j-1],大功告成！

#include 
#include 
#include 

using namespace std;
const int N = 3e5+10;

int a[N],s[N];
typedef pairPII;
vector add,query;
vectoralls;

int find(int x)
{
    int l = 0,r = alls.size()-1;
    while (l>1;
        if (alls[mid]>=x) r= mid;
        else l = mid+1;
    }
    return r+1;//找到第一个大于等于x的下标
}


int main()
{
    int n,m;
    cin >> n >> m;
    int x,c;
    for (int i = 1;i <= n;i++)
    {
        cin >> x >> c;
        alls.push_back(x);
        add.push_back({x,c});
    }
    int l,r;
    for (int i = 0;i> l >> r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
   for (auto i:add)
   {    
       int j = find(i.first);//使得下标x先映射到下标，再在下标数组中运算
       a[j]+=i.second;
   }
   for (int i = 1;i<=alls.size();i++) s[i] =s[i-1]+a[i];

   for (auto i:query)
   {
       int p = find(i.first),q = find(i.second);
       cout<

 

我是小郑，正在奔赴热爱，奔赴山海，体会数学和算法之美~​​​​​​​

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/1354097.html