。

通常用于处理大范围或者无限可能的输入#xff0c;以便将其转化为有限的、可以有效处理的范围。

离散化的定义…一、离散化discretization在算法和数据结构中指的是将连续的输入数据映射到离散的值或者范围从而使得处理和计算变得更高效。

通常用于处理大范围或者无限可能的输入以便将其转化为有限的、可以有效处理的范围。

离散化的主要目的是将连续的值或大范围的值映射到一个有限的集合中以便进行高效的存储和处理。

这通常通过对连续的数据进行排序、分组、或者映射来实现。

排序和编号对所有唯一的连续值进行排序然后为这些值分配一个唯一的编号。

映射使用一个映射函数将原始数据的每个值转换为新的编号或索引。

应用场景

区间压缩在处理大范围的整数值时通过离散化可以将这些值映射到一个较小的范围。

例如处理1到10000的值时可以将它们映射到1到100的范围内。

数据结构优化在某些数据结构中如树状数组或线段树需要将离散化后的值作为索引来优化查询和更新操作。

机器学习将连续特征转换为离散类别简化模型处理例如将年龄分段成“青年”、“中年”、“老年”。

图像处理将图像数据的连续像素值转换为离散的色彩级别提高处理效率。

数据压缩将连续信号如音频或视频离散化以减少存储需求。

数据库设计将连续数据映射到离散值用于更高效的数据索引和查询。

1区间压缩

3)这样我们将原始的连续坐标转换成离散的坐标对数据结构的处理如二维树状数组将更加高效。

离散化的关键是将原始的、可能是连续或无限范围的数据转化为有限且可处理的编号或索引。

这样不仅优化了存储空间也提高了数据处理的效率。

二、在算法中“映射”是指将一个集合中的每个元素通过某种规则或函数转换为另一个集合中的元素的过程。

这一概念广泛应用于数据处理、函数设计和数据结构中。

以下是映射的详细解释

基本定义

数据结构中的映射在哈希表中映射是通过哈希函数将键key映射到对应的值value。

例如键

name

数据转换在数据处理过程中可以将数据从一种格式转换为另一种格式。

比如映射函数可以将用户输入的字符串转换为对应的内部数据结构。

离散化在离散化过程中映射用于将连续的数据转换为离散的值。

例如将地理坐标映射到一个有限的网格系统中。

复杂映射

映射不仅限于一对一关系还可以是多对一多个输入映射到一个输出或一对多一个输入映射到多个输出。

例如在关系数据库中某一用户ID可能映射到多个订单记录。

单射Injective每个定义域的元素映射到值域中唯一的元素不存在不同的输入映射到相同的输出。

满射Surjective定义域中的每个元素都映射到值域中的某个元素使得值域中的每个元素至少被映射一次。

双射Bijective既是单射又是满射即每个定义域的元素都有唯一的值域元素且值域中的每个元素都有唯一的定义域元素。

映射在算法中扮演着重要角色它使得数据转化、存储和处理变得更加系统化和高效。

了解了什么是离散化和映射接下来直接开始做题用题目实践才是最好的。

题目区间和

PII;/*定义pairint,int类型为PII就相当于取了一个别名就是方便使用的时候不输入那么复杂又长的东西。

*/

const

输入的n个xm个l,r就是n2m个坐标因为n和m都是10的五次方所以就是3乘10的5次方多10是故意开的害怕越界嘛。

*/

int

/*这个就是求的区间和只不过前面还有些步骤所以这个a[N]数组是存储的值不是坐标哈s[N]

vectorPII

/*观察题目得到输入的位置x和插入的值c与后面输入的区间两个边界l,r一样都是一次输入一对

的数进去所以这里定义了一个PII类型的vector来存储要操作的东西。

这里面add是存储插入的位置x和值c而query是查询区间并求出指定区间的和所以query存储的是边界lr的位置*/

vectorint

/*alls是存储所有的位置的不管是刚开始的x还是l,r都存在里面后面会操作的很有用处。

记住vector是c里面的可变数组所以在进行和数组类似的操作时也可以像数组那样使用切记。

*/int

find(int

l0,ralls.size()-1;while(lr){int

midlr1;//这里是整数没有小数所以可以用位运算。

if(alls[mid]x)

rmid;//二分的第一个模板相当于求最小值的那个不用加1。

else

lmid1;}return

r1;//这里你写l1也可以反正最后二分l是约等于r的都可以。

/**注意返回的是r1就是最低是返回1因为我要求前缀和所以就这样。

/

/*这个函数是利用的二分查找来查找x在alls可变数组里面的位置也就是x在alls可变数组的数组下标是多少。

这其实就是离散化了alls数组在之前的操作后已经变得井然有序每一个输入的坐标值x,l,r在alls里面都有对应的位置这就已经将原来范围大数目少且离散不好处理的坐标给放在了alls数组里面所以要注意这个alls数组里面存的是坐标如果要求对应的值的话那么就是例如要想查询x位置上的值的话那么就是1、先找到x这个坐标在alls数组里面的哪个位置对应的是alls数组的哪个下标。

2、找到了以后就能迅速的在alls数组里面找到x坐标所在的位置。

这就是离散化1、vector存输入的位置坐标2、在这个vector里面找到需要的位置坐标。

3、找到以后就可以像之前那样正常操作了想查值就查值想求前缀和就求前缀和。

*/int

main(){int

cinxc;add.push_back({x,c});alls.push_back(x);}

/*输入n,m并且输入xc这x,c是插入所需要的值所以将这两个值存到add这个vector里面。

然后顺便把位置x存入alls这个可变数组里面。

*/for(int

i0;im;i){int

l,r;cinlr;query.push_back({l,r});alls.push_back(l);alls.push_back(r);}

/*输入l,r并将后面查询求前缀和所需要的值l,r给存入到query这个vector里面去同时l,r这两个表示位置的数也全部存到alls这个可变数组内。

*/

sort(alls.begin(),alls.end());//排序alls里面的所有坐标值alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重并调整里面的坐标值。

/*所有输入的关于位置的数也就是所谓的坐标已经排序去重并调整大小了经过了这两步得到的是

有序的且中间没有空位的新的alls可变数组这对于后面的离散化是很重要的。

*/

for(auto

xfind(item.first);//找x这个坐标在alls数组里面的数组下标是多少。

a[x]item.second;//在alls数组里面找到x所在的位置后就直接执行c的插入操作就可以了。

}//插入操作for(int

i1;ialls.size();i)

s[i]s[i-1]a[i];//注意ialls.size()是从下标1开始的不是0.

/*这里还是和求前缀和是一样的在求前缀和之前都要定义一下前缀和的表示在我看来就是定义一种性质嘛注意这里是i从1开始不从0开始是为了避免边界问题。

*/for(auto

item:query){//这个不一定要写成item随便写自己喜欢的单词就好不影响的。

int

lfind(item.first),rfind(item.second);//分别求l,r在alls数组里面的位置。

printf(%d\n,s[r]-s[l-1]);//这就是求前缀和直接用公式就可以这是一维前缀和哦。

}//查询并求前缀和的操作/*这里面的first,second就是键值因为我的add和query的vector都是PII类型的也就是pairint,int类型的就拿这里来说这里query的item.first指的是输入的l而item.second指的是输入的r。

*/return