离散化算法

在对于大范围的数组中对小范围的数进行运算时，缩小操作的数组，使用离散化算法可以降低时间复杂度。

离散化算法是使用vector容器记录需要离散化数据的下标，对其下标进行下一步操作

例：令一段数列中的第x个数加上c，执行n次，给出m个[l,r]的范围，求该范围的和

思路：

1.对于求和可以用前缀和的方式求和 即int a[N],s[N]保存数据

2.记录所有操作的下标和操作

3.将需要操作的下标和所有l，r的范围记录到离散化数组中

4.对离散化数组去重（需要对数组中保存的下标先排序再去重）

5.构造a数组，a数组数据的下标为离散化数组对应下标的n+1

6.前缀和求解

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
const int N = 30010;
int a[N];//存的全部的数
int s[N];//前n项和
typedef pair<int, int>PI;
vector<int> alls;//所有需要离散化的下标
vector<PI> adds;//插入操作
vector<PI> query;//每次求和的范围
int find(int x)
{
    int l = 0;
    int r = alls.size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (alls[mid] >= x)r = mid;
        else l = mid+1;
    }
    return r + 1;
}
int main()
{
    int n, m;//n为有多少个数，m为多少个范围
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x, c;//x为下标，c为要加上的数为多少
        cin >> x >> c;
        adds.push_back({ x,c });
        alls.push_back(x);
    }
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> 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 item : adds)
    {
        int x = find(item.first);
        a[x] += item.second;
    }
    for (int i = 1; i <= alls.size(); i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    for (auto item:query)
    {
        int l = find(item.first);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

总结：

离散化就是将在大范围数组中提取进行操作的数据到离散化数组中然后进行操作
 

网址：离散化算法 https://www.yuejiaxmz.com/news/view/9374

相关内容

如何计算距离今天的天数(如何计算距离今日几天)
《怦然心动的人生整理魔法》｜学会断舍离，让人生化繁为简
家居生活智能化已从单品“扩散”至全屋
pe值算法=公式技巧.doc
河南省城市生活垃圾卫生填埋处理 运营成本核算办法
血糖高散步、喝参斛茶 送你十个降糖小方
算一算，不再被忽视的家务劳动到底值多少钱？
整理收纳五步工作法：摊、理、分、算、收 ——抽屉整理收纳
算法小技巧：空间换时间，时间换空间？
1斤香料怎么计算重量：精确计量的小技巧(1斤香料怎么计算重量)

随便看看