【离散化】802. 区间和

1. 什么是离散化

比如给一组数，我们要把这组数存储起来，
给的数为：1 5 8
我们可以采用创建 元素个数为10的数组
把角标为1 5 8的值都变为1，
那么我们遍历这个数组，值为1，就是所给的数

但是如果所给的数值是 100000，那么我们就要开一个比这个数值大的元素个数的数组，那么就会很浪费空间。

我们就采用离散化，进行存储
方法如下：
比如给了n个数，那么我们就创建n+1个元素的数组
然后就依次存储这些元素
最后直接依次输出数组，便可以得到所给的 数

上难度：
如果，我们给一对数，何如存储呢？
比如，我们给（1,5），（2,8），（3,9）
我们还是可以采用创建 元素个数为10的数组，
然后把角标为1的位置 置成5 角标为2的位置 置成 8 等等
然后其余的角标 置成 -1或者其他数

但是如果所给数对为（max，-min）
那么我们就要创建一个max大小的数组，
并且无法保证顺利遍历数组，因为不知道怎么处理没有放置元素的位置。

那么怎么办呢？
我们可以用 typedef pair PII; 存储数对
然后把这个数对直接依次放入数组中

效果如下：

看到这里，就可以上例题了

2. 例题：802. 区间和

思路：

首先题中给的信息，我们通过离散化存储如下

题中想问的是，1-3，4-6,7-8之间的元素和

我们可以这样处理，我们只需要求我们已知所给的角标1 3 7和题中要求的角标范围的角标 1 3 4 6 7 8这些点的S（S表示区间和，比如S【3】 = a1 + a2 + a3）这样的话，要求1 - 3的区间和，我们只需让 S【3】-S【1】即可

（补充：我们存储区间范围，也需要用数对存储的方法）

综上，我们就得到了如下的情况

（补充：存储区间范围）

再求前缀和Sn

思路完毕，再来看一下代码

#include 
#include 
#include 
using namespace std;

typedef pair<int, int> PII;
const int N = 300010;
int a[N], s[N];
int n, m;
//add 存储 数对 如（1,3）
//alls 存储角标 用于求 Sn
//query 存储 区间范围
vector<int> alls;
vector<PII> add, query;

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}
//unique的返回值是 迭代器
vector<int>:: iterator unique(vector<int> &a)
{
    int j = 0;
    for(int i = 0; i < a.size(); i ++)
        if(!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    return a.begin() + j;
}

int main()
{

    cin >> n >> m;

    for(int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        //add 存储 数对 如（1,3）
        add.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);
    }
	//对 要求S 的角标进行 排序 去重
//1. 为什么要排序？因为所给的数对的 第一个数作为角标，不一定是有序的
//2. 为什么要去重？因为alls中已经有要求的 角标了，如果要求的范围又出现该角标，那么就需要去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls), alls.end());
//unique的作用是返回 去重好的 数组的最后一个指针（迭代器）
// erase的作用是 删除数组的元素

//求Sn（只求所给数对的即可，因为其他的角标也没有数值呀）
    for(auto item : add)
    {
        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), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86